演算法圖鑑
Array & Hashing · 03 / 05

Hash Table雜湊表

雜湊函數、碰撞處理、負載因子。

用在：快取、Session、資料庫索引、去重

時間複雜度平均 O(1)
空間複雜度O(n)
難度入門
前置知識Array & Dynamic Array、Amortized Analysis

01為什麼需要它

使用者一登入，伺服器怎麼在一百萬個 session 裡找到他

每個請求都帶一個 session ID，伺服器要立刻知道這是誰。用陣列一個一個比對，一百萬筆要比一百萬次，每個請求都這樣做，服務就掛了。

為什麼用它雜湊表把 ID 經過雜湊函數直接算出「該放在哪一格」，查詢不用比對其他任何人。Redis、Memcached 的核心就是一個大雜湊表。

資料庫的雜湊索引與 JOIN

兩張表要用 user_id 對起來。沒有索引的話，每一筆都要掃另一張表，O(n·m)。

為什麼用它先把一張表建成雜湊表（hash join），另一張表每筆只要一次查詢。O(n + m)。

編譯器與直譯器的變數查找

程式碼裡出現一個變數名，直譯器要找到它的值。程式裡可能有幾千個名字，每一行都要查。

為什麼用它符號表就是雜湊表：字串經雜湊變成數字索引。Python 的每個物件屬性、每個模組命名空間，底層都是 dict。

看到這些關鍵字就想到它：用鍵找值、去重、判斷看過沒有、快取、O(1) 查詢、鍵不是連續整數。

02核心概念

陣列靠位置存取，但真實世界的鍵是字串、ID、座標，不是 0 到 n−1 的整數。雜湊表用一個雜湊函數把任意鍵變成一個整數，再對容量取餘數，得到它該放的桶（bucket）編號。這樣查詢就變成：算一次雜湊、直接跳到那個桶。平均 O(1)。

兩個不同的鍵可能算出同一個桶，這叫碰撞。最常見的處理是鏈結法：每個桶掛一條小串列，碰撞的鍵串在一起，查的時候沿著鏈比對。另一種是開放定址：碰撞就往後找下一個空格（Python 的 dict 用這種）。兩者都要求鏈或探測長度保持很短。

控制長度的關鍵是負載因子 = 元素數 ÷ 桶數。超過門檻（通常 0.75）就把桶數加倍、所有元素重新放一次，這叫 rehash。它是 O(n)，但發生頻率隨 n 加倍而減半，攤銷後每次插入仍是 O(1)。這和動態陣列擴容是同一個道理。 最壞情況（所有鍵都撞在同一桶）是 O(n)，所以說「平均 O(1)」而非「一定 O(1)」；好的雜湊函數讓最壞情況幾乎不會發生。

代價是雜湊表沒有順序：不能問「比 k 大的最小鍵」或「依序走訪」。需要順序時用平衡樹（C++ 的 map），那是樹那一章的事。

03演算法步驟

  1. 1算 h = hash(key)，桶編號 b = h % capacity。
  2. 2查詢：沿著桶 b 的鏈逐一比對 key，找到就回傳值，走到底就是不存在。鏈平均長度 = 負載因子，所以是 O(1)。
  3. 3插入：先照步驟 2 找，存在就覆蓋；不存在就串到鏈尾，元素數加一。
  4. 4插入後檢查負載因子：超過門檻就把容量加倍，每個既有的 key 重新算 hash % 新容量 放進新桶。
  5. 5刪除：找到後從鏈中移除。開放定址法的刪除要留「墓碑」標記，鏈結法不用，這是鏈結法比較好教的原因。

04互動示範

從 4 個桶開始插入 key，看碰撞怎麼串成鏈；負載因子超過 0.75 時桶數會加倍、所有 key 重新分配，鏈又變短。

元素數 n
0
容量（桶數）
4
負載因子 n / 容量
0.00
最長的鏈
0
桶（bucket）與鏈
[0]空
[1]空
[2]空
[3]空
比對 0 次4 個空桶。插入的 key 用 key % 容量 決定放哪個桶；同一桶的 key 串成鏈。

05程式碼

手寫一個鏈結法雜湊表，把 get / put / remove / rehash 走一遍；最後是實務上該直接用的內建容器。

class HashMap:
    """鏈結法（separate chaining）：每個桶是一個 list，存 (key, value)。"""

    MAX_LOAD = 0.75

    def __init__(self, capacity=4):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        return hash(key) % self.capacity        # 雜湊函數 → 桶編號

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:   # 只看這一桶
            if k == key:
                return v
        return default

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                            # 已存在：覆蓋
                bucket[i] = (key, value)
                return
        bucket.append((key, value))                 # 不存在：串到鏈尾
        self.size += 1
        if self.size / self.capacity > self.MAX_LOAD:
            self._rehash()

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _rehash(self):
        # 容量加倍，每個 key 重新算桶。O(n)，但攤銷後每次 put 仍是 O(1)
        old = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        for bucket in old:
            for k, v in bucket:
                self.buckets[self._index(k)].append((k, v))


# 實際使用時直接用內建的 dict / set，它們就是雜湊表
m = {}
m["alice"] = 30          # 平均 O(1)
m.get("bob", 0)          # 平均 O(1)
"alice" in m             # 平均 O(1)
del m["alice"]           # 平均 O(1)

06練習題

  • LeetCode 705Design HashSetEasy
  • LeetCode 706Design HashMapEasy
  • LeetCode 217Contains DuplicateEasy
  • LeetCode 380Insert Delete GetRandom O(1)（雜湊表 + 陣列）Medium
  • LeetCode 146LRU Cache（雜湊表 + 雙向鏈結串列）Medium
上一篇Prefix Sum下一篇Hash Set / Map Patterns