概念筆記: Hash Table 雜湊表

為何需要 Hash Table ?

接續上篇 概念筆記: Hash 雜湊函數 (哈希函數)，這次來筆記一下 「雜湊表 (Hash Table)」。

假設有一組資料，每一組資料都有 key 跟 value，key 為 Integer，value 為 String。如果今天我們要找到 key 為 13 的值是多少，那我們要先尋找 key = 13 在哪，然後找到對應的 value 是 dount。若用最笨的方法找，那麼時間複雜度將會是線性的 O(n)，n 為串列長度。

或者聰明一點，可以生成一個新的串列，然後把原始串列的 key 直接作為新串列的 index，這樣也可以用 key 在新串列直接找到對應的 value。但是，如此一來如果 key 之間相差很多，那再生成新串列時會浪費很多空間，空間利用率極低。

好，讓我們切入 Hash Table 怎麼做?

記得上一篇說到雜湊可以把任意長度的原始資料映射到一個有限的集合裡嗎? 我們就是要利用這一點。將原來的 key 經過 Hash Function，再將雜湊值作為新串列的 index，如此一來空間就被有效利用，並且我們還能自己決定新串列的大小。

時間複雜度上為常數的 O(1)，基本上就跟串列的長度沒什麼關連性了。

就是這麼回事，此乃 Hash Table 是也。

雜湊函數

不同的使用狀況可以選擇用不同的雜湊函數，以下是我學習到的兩個簡單的雜湊計算方法。

除法方法 (Division Method)

這是一個簡單到不能再簡單的算法。假設我想像上一張圖一樣，把任何 key 透過雜湊映射到最終 9 個雜湊值(0~8)，那我們只要將所有 key 除以 Hash Table 的長度取餘數就可以了。

h(k) = k % M

k = Key, M = length of hash table

例如 donut 的 key 是 13，那我就把 13 % 9 = 4。把 dount 存到 Hash Table 裡 index=4 的格子裡就行。下次我要再找一次 key 為 13 的字串為何，只要把 key 也做一次 mod，就可以直接以雜湊值作為 index 從 Hash Table 中找到 donut 了!

乘法方法 (Multiplication Method)

另一個方法為乘法法，這個方法能夠提高隨機性，降低碰撞，詳細原理雖然我有研究了一下，但還不是很懂。其中 A 這個常數通常使用 (√5–1)/2，也就是黃金分割率 0.61803398875，可以最大降低碰撞機率。

h(k) = floor (M * (k * A % 1))

M= length of hash table, k = Key, A = a constant value

例子就不舉了，反正各個參數帶入進去算就行。

據說這個方法計算效率也更高，尤其是 M 為 2 的冪次時效率最高，有興趣的可以參考這篇: Hash Functions and list/types of Hash functions。

代碼實作

最後肯定要來實作一下，我採用的是 Multiplication Method。這個例子中我的 key 並非單純的整數，而是字串，所以我決定先將字串的每個字母轉換成 ASCII，相加後再帶入雜湊計算。

import math

class HashTable:

    def __init__(self, size) -> int:
        self.table = [None for i in range(size)]

    # Hash Function
    def MultiplicationHash(self, key) -> str:
        M = len(self.table)
        k = sum([ord(c) for c in key]) # 轉換成 ASCII 相加
        A = 0.6180339887
        return math.floor(M * (k * A % 1))

    # 新增元素
    def Insert(self, key, value) -> str:
        index = self.MultiplicationHash(key)
        self.table[index] = value

    # 尋找元素
    def Sreach(self, key) -> str:
        index = self.MultiplicationHash(key)
        if self.table[index]:
            return self.table[index]
        else:
            return None

    # 獲得雜湊值(hash table 的 index)
    def GetIndexOfHash(self, key) -> str:
        index = self.MultiplicationHash(key)
        return index

if __name__=='__main__':
  
    M = 100
    table = HashTable(M) 
  
    # 加入元素
    table.Insert('student_1', 'apple')
    table.Insert('student_34', 'greenMug')
    table.Insert('student_22', 'happyCat')

    # 尋找 key 為 student_22 的 value
    key = 'student_22'
    value = table.Sreach(key)
    hashInt = table.GetIndexOfHash(key)
    print(f'Key: {key}, Value: {value}, IndexOfHashTable: {hashInt}')
  
    # 尋找 key 為 student_1 的 value
    key = 'student_1'
    value = table.Sreach(key)
    hashInt = table.GetIndexOfHash(key)
    print(f'Key: {key}, Value: {value}, IndexOfHashTable: {hashInt}')

# 輸出結果
Key: student_22, Value: happyCat, IndexOfHashTable: 49
Key: student_1, Value: apple, IndexOfHashTable: 97

以上。