【Day10】[资料结构]-杂凑表Hash Table-实作

杂凑表(Hash Table)建立的方法

• hash: 杂凑函式
• add: 新增资料
• search: 搜寻资料
• remove: 删除资料

本实作使用

• 使用除法杂凑函式将每个字元转换成unicode码加总 / Bucket数量，再取余数。
• 使用Chaining方式来处理碰撞(Collision)。

杂凑表的介绍可以参考此篇。

JavaScript

// 杂凑函式
function hash(key, size) {
  let hashCode = 0;
  for (let index in key) {
    hashCode += key.charCodeAt(index);
  }
  return hashCode % size;
}

// 链结串列节点
class Node {
  constructor(key, value) {
    this[key] = value;
    this.next = null;
  }
}

// 链结串列
class LinkedList {
  constructor(node) {
    this.head = node;
    this.count = 0;
  }
}

// 杂凑表
class HashTable {
  constructor() {
    this.size = 5;
    this.values = new Array(this.size).fill(null);
    this.length = 0;
  }
  // 新增资料
  add(key, value) {
    const hashIndex = hash(key, this.size);
    const node = new Node(key, value);
    if (!this.values[hashIndex]) {
      this.values[hashIndex] = new LinkedList(node);
    } else {
      let current = this.values[hashIndex].head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.values[hashIndex].count++;
    this.length++;
  }
  // 查询资料
  search(key) {
    const index = hash(key, this.size);
    const slot = this.values[index];
    let current = slot.head;
    if (current.hasOwnProperty(key)) {
      return current[key];
    }
    while (current.next) {
      if (current.next.hasOwnProperty(key)) {
        return current.next[key];
      } else {
        current = current.next;
      }
    }
    return "Data not found";
  }
  // 删除资料
  remove(key) {
    const index = hash(key, this.size);
    const slot = this.values[index];
    let current = slot.head;
    if (current.hasOwnProperty(key)) {
      slot.head = current.next;
      slot.count--;
      this.length--;
      return "Data was deleted successfully";
    }
    while (current.next) {
      if (current.next.hasOwnProperty(key)) {
        current.next = current.next.next;
        slot.count--;
        this.length--;
        return "Data was deleted successfully";
      } else {
        current = current.next;
      }
    }
    return "Data is not exhausting";
  }
}

const ht = new HashTable();

ht.add("John", "111-111-111");
ht.add("Taylor", "222-222");
ht.add("Krish", "333-333");
ht.add("Mack", "444-444");
ht.add("Den", "555-555");
ht.add("Mike", "666-666");
ht.add("John", "77-77");
ht.add("Jack", "88-88-88");
ht.add("Jimmy", "99-99");
ht.add("Harry", "121-121");
ht.add("Meet", "232-232");
ht.add("Miraj", "454-454");
ht.add("Milan", "567-567");
console.log(ht.search("Den"));//555-555
console.log(ht.search("Miraj"));//454-454
console.log(ht.search("Drupel"));//Data not found
console.log(ht.remove("Krish"));//Data was deleted successfully
console.log(ht.remove("Mack"));//Data was deleted successfully
console.log(ht.remove("Meet"));//Data was deleted successfully
console.log(ht.remove("Taylor"));//Data was deleted successfully
console.log(ht.remove("JsMount"));//Data is not exhausting
console.log(ht.values);
/* [
    {
        "head": {
            "Mike": "666-666",
            "next": null
        },
        "count": 1
    },
    null,
    {
        "head": {
            "Jack": "88-88-88",
            "next": {
                "Milan": "567-567",
                "next": null
            }
        },
        "count": 2
    },
    {
        "head": {
            "Jimmy": "99-99",
            "next": {
                "Harry": "121-121",
                "next": null
            }
        },
        "count": 2
    },
    {
        "head": {
            "John": "111-111-111",
            "next": {
                "Den": "555-555",
                "next": {
                    "Miraj": "454-454",
                    "next": null
                }
            }
        },
        "count": 3
    }
] */

Python

#Hash Table
class Node:
    def __init__(self, key=None, data=None):
        self.value = {}
        self.value[key] = data
        self.next = None

    def __repr__(self):
        return str(self.data)

class LinkedList:
    def __init__(self, head=None):
        self.head = head
        self.next = None
        self.count = 0

    def __str__(self):
        str_list = []
        current = self.head
        while current:
            str_list.append(str(current.value))
            current = current.next
        return "[" + "->".join(str_list) + "]"

    def __repr__(self):
        return str(self)

class HashTable:
    def __init__(self, size):
        self.size = size
        self.values = [None] * size
        self.length = 0
        
    def hash(self, key, size):
        hashCode = 0
        for i in range(len(key)):
            hashCode += ord(key[i])
        return hashCode % size

    def add(self, key, value):
        hashIndex = self.hash(key, self.size)
        node = Node(key, value)
        if not self.values[hashIndex]:
            self.values[hashIndex] = LinkedList(node)
        else:
            current = self.values[hashIndex].head
            while current.next:
                current = current.next
            current.next = node
        self.values[hashIndex].count +=1
        self.length +=1

    def search(self, key):
        hashIndex = self.hash(key, self.size)
        slot = self.values[hashIndex]
        current = slot.head
        if key in current.value:
            return current.value
        while current.next:
            if key in current.next.value:
                return current.next.value
            else:
                current = current.next
        return "Data not found"

    def remove(self, key):
        hashIndex = self.hash(key, self.size)
        slot = self.values[hashIndex]
        current = slot.head
        if key in current.value:
            current = current.next
            slot.count -=1
            self.length -=1
            return "Data was deleted successfully"
        while current.next:
            if key in current.next.value:
                current.next = current.next.next
                slot.count -=1
                self.length -=1
                return "Data was deleted successfully"
            else:
                current = current.next
        return "Data is not exhausting"

    def __repr__(self):
        return str(self.values)

ht = HashTable(5)
ht.add("John", "111-111-111")
ht.add("Taylor", "222-222")
ht.add("Krish", "333-333")
ht.add("Mack", "444-444")
ht.add("Den", "555-555")
ht.add("Mike", "666-666")
ht.add("Jack", "88-88-88")
ht.add("Jimmy", "99-99")
ht.add("Harry", "121-121")
ht.add("Meet", "232-232")
ht.add("Miraj", "454-454")
ht.add("Milan", "567-567")
print(ht)
#[
# [{'Taylor': '222-222'}->{'Mack': '444-444'}->{'Mike': '666-666'}->{'Meet': '232-232'}], 
# None, 
# [{'Jack': '88-88-88'}->{'Milan': '567-567'}], 
# [{'Krish': '333-333'}->{'Jimmy': '99-99'}->{'Harry': '121-121'}], 
# [{'John': '111-111-111'}->{'Den': '555-555'}->{'Miraj': '454-454'}]
# ]
print(ht.search('Den'))#{'Den': '555-555'}
print(ht.search('Jimmy'))#{'Jimmy': '99-99'}
print(ht.remove('Den'))#Data was deleted successfully
print(ht.search('Den'))#Data not found

print(ht)
#[
# [{'Taylor': '222-222'}->{'Mack': '444-444'}->{'Mike': '666-666'}->{'Meet': '232-232'}], 
# None, 
# [{'Jack': '88-88-88'}->{'Milan': '567-567'}], 
# [{'Krish': '333-333'}->{'Jimmy': '99-99'}->{'Harry': '121-121'}], 
# [{'John': '111-111-111'}->{'Miraj': '454-454'}]
# ]