雜湊表(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'}]
# ]