雜湊表（Hash Table）教學：原理、程式碼與時間複雜度

雜湊表解決什麼問題

假設你存了一百萬筆使用者資料，需要用電子郵件找出其中一筆。掃描串列是 O(n)；把串列排序後可以用二分搜尋做到 O(log n)，但插入就變慢了。雜湊表平均只要 O(1) 就能找到資料，不論有多少筆，插入與刪除也一樣快。

這就是雜湊表隨處可見的原因：程式語言的字典與集合、資料庫的雜湊索引、快取、編譯器的符號表，以及去除重複資料。

用白話理解

想像一間有 100 個編號掛鉤的衣帽間。服務員不會逐一檢查每個掛鉤來找你的外套，而是依你的名字算出一個掛鉤編號，直接走過去。計算編號的函式就是雜湊函式。好的雜湊函式要夠快，同一個鍵永遠得到同一個數字，並且能把不同的鍵平均分散到各個掛鉤上。

1. 計算 h = hash(key)。
2. 選出桶：index = h % capacity。
3. 只在那個桶裡尋找這個鍵。

實例演練：用鏈結法處理碰撞

取一個有 4 個桶的表，以及一個玩具雜湊函式：把字母的位置加總（a = 1，b = 2，……）。

act 和 bee 都與 cat 碰撞。現在要查找 bee，就得檢查 bucket 0 裡的三個項目。如果雜湊函式不好（字母加總會忽略順序）或桶太少，鏈就會變長，雜湊表也隨之變慢。真正的雜湊函式會混合鍵的所有位元，真正的雜湊表在太滿時也會擴容。

以 Python 實作鏈結法雜湊表

每個桶都是一個由 [key, value] 組成的串列。當項目數量超過桶數量的 0.75 倍（負載因子）時，雜湊表會把容量加倍，並重新插入所有項目。

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

碰撞處理策略比較

CPython 的 dict 使用開放定址法，搭配擾動過的探測序列，並且從 Python 3.7 起保證迭代順序與插入順序一致。Java 的 HashMap 使用鏈結法，並把過長的鏈轉換成平衡樹。

時間與空間複雜度

平均 O(1) 取決於良好的雜湊函式和有上限的負載因子。Python 會讓每個行程的字串雜湊值隨機化（雜湊種子），這樣攻擊者就無法輕易送出大量互相碰撞的鍵，把伺服器每個請求拖慢到 O(n)。

常見錯誤

• 使用可變物件當鍵，或在類別上定義了 __eq__ 卻沒有對應的 __hash__。相等的物件必須有相等的雜湊值。
• 期待有排序。雜湊表提供快速查找，而不是順序；需要範圍查詢或最小鍵時，請用排序過的串列或平衡樹（二元搜尋樹）。
• 依賴不同次執行之間的 hash() 值：除非固定 PYTHONHASHSEED，否則字串的雜湊值在不同 Python 行程之間會不同。需要穩定雜湊值時請用 hashlib。
• 把雜湊表當成安全機制。雜湊表使用的是快速的非密碼學雜湊；密碼需要專用的密碼雜湊函式。

何時使用，以及常見的面試應用

只要你需要快速回答「我看過這個嗎？」或「這個鍵對應的值是什麼？」，就用雜湊表。如果還需要順序、範圍或最接近的鍵，請用二元搜尋樹或排序陣列。

經典題目：兩數之和（儲存每個數字的索引，查找 target - x）、計算頻率（collections.Counter）、依排序後的字母把字母異位詞分組、偵測重複元素，以及在動態規劃中記憶化結果。

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)