[Data Structure] 雜湊表

雜湊表 (Hash Table) 是以「鍵 (Key)」直接定位「值 (Value)」的資料結構——給個 key，透過雜湊函式 (Hash Function) 直接算出該 key 所在的陣列位置（index），平均時間複雜度達 $O(1)$，是實務上最常見的查詢結構。後面會用到的符號：$n$（已放入的元素數）、$m$（表的總 slot 數）、$\alpha = n/m$（load factor，載入率）。

典型應用：字典、集合、資料庫索引、快取、編譯器符號表。

核心觀念

• 底層是一個固定大小的陣列（桶 Bucket 或槽 Slot）
• 透過 index = hash(key) % table_size 決定資料該放哪個 slot
• 讀、寫、刪除都只要一次 hash 運算 + 一次陣列存取，所以平均是 $O(1)$

雜湊函式 (Hash Function)

把任意 key 轉成固定範圍整數的函式，好的 hash 函式要滿足：

• 確定性：同一個 key 每次算出的 hash 值要相同
• 快速：計算成本要低（通常要求 $O(1)$）
• 均勻分布：不同 key 應盡量分散，避免大量碰撞

最常見的簡化做法是「除法 hash」：

其中 $m$ 是表的大小，通常取質數以分散 key。

碰撞 (Collision)

不同的 key 經過 hash 函式後對應到同一個 index，稱為碰撞。

• 鴿籠原理 (Pigeonhole Principle) 保證：只要 key 的數量超過 slot 數，碰撞一定發生
• 即使未超過，hash 函式分布不均也可能提前產生碰撞

解法分兩大陣營：鏈結法 (Chaining) 與 開放定址法 (Open Addressing)。

鏈結法 (Chaining)

每個 slot 指向一個串列（或其他容器），碰撞到的 key 都掛在同一個 slot 的串列上。

以 $m = 7$、$h(k) = k \bmod 7$，依序插入 [15, 22, 8, 36, 29]（這組 key 全部 hash 到 1，是最壞情況的示範）：

最終表：

以下互動圖解重現上面這五筆 key 依序掛入 slot 1 的過程，點「下一步」可逐筆觀察串列如何越掛越長：

查詢時先算 hash 找到 slot，再在串列內逐一比對 key。以上表找 36：

1. 算 hash(36) = 36 mod 7 = 1，進 slot 1
2. 串列 [15, 22, 8, 36, 29] 逐一比對：15 ≠、22 ≠、8 ≠、36 ✓ 命中（第 4 次比對）

找不存在的 10：hash(10) = 3，slot 3 為空 → 直接回報不存在。

import java.util.LinkedList;

public class HashTableChaining {
    private LinkedList<Entry>[] table;
    private int size;

    public HashTableChaining(int size) {
        this.size = size;
        this.table = new LinkedList[size];
        for (int i = 0; i < size; i++) table[i] = new LinkedList<>();
    }

    private int hash(int key) {
        return key % size;
    }

    public void put(int key, String value) {
        int idx = hash(key);
        for (Entry e : table[idx]) {
            if (e.key == key) { e.value = value; return; }
        }
        table[idx].add(new Entry(key, value));
    }

    public String get(int key) {
        for (Entry e : table[hash(key)]) {
            if (e.key == key) return e.value;
        }
        return null;
    }

    static class Entry {
        int key;
        String value;
        Entry(int k, String v) { key = k; value = v; }
    }
}

開放定址法 (Open Addressing)

碰撞時不另外開串列，直接在表內找下一個可用的 slot。探測策略有三種主流做法。

以下互動圖解用同一組 key [15, 22, 8, 36, 29]（全都 hash 到 slot 1）示範三種探測法的落點差異——點按鈕切換策略，琥珀色編號代表每次探測的順序：

線性探測 (Linear Probing)

碰撞後一次跳一格：$h(k, i) = (h(k) + i) \bmod m$。

同樣以 $m = 7$、$h(k) = k \bmod 7$，依序插入 [15, 22, 8, 36, 29]：

最終表：

平方探測 (Quadratic Probing)

每次跳的距離變成平方：$h(k, i) = (h(k) + i^2) \bmod m$。

變數 $i$ 是探測次數，從 $0$ 開始；每次探測到的 slot 已被占用就 $i \mathrel{+}= 1$ 再試下一個，直到找到空 slot 為止。$i = 0$ 代表第一次探測（即 $h(k)$ 本身）。

同 key、同表：

雙雜湊 (Double Hashing)

跳步長度由第二個 hash 函式決定：$h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m$。

設 $h_1(k) = k \bmod 7$、$h_2(k) = 1 + (k \bmod 5)$（$h_2$ 不能為 0，否則會退化成線性探測）：

最終表：

三種探測法的比較

時間複雜度

• 平均情況假設 hash 均勻分布、load factor 控制得宜
• 最差情況出現在所有 key 都 hash 到同一個 slot（鏈結法退化為鏈結串列、開放定址退化為線性搜尋）

負載因子與 Rehash

負載因子 (Load Factor) $\alpha = n/m$（已放入元素數 ÷ 總 slot 數），衡量表有多擠：

• $\alpha$ 越大 → 碰撞越頻繁 → 效能越差
• 開放定址法通常要求 $\alpha \le 0.75$
• 鏈結法允許 $\alpha > 1$（串列可無限長），但超過後效能會快速下滑

當 $\alpha$ 超過門檻時觸發 Rehash：

1. 建立更大的新表（通常是原本的 2 倍，且保持質數）
2. 逐一把舊表的每個 entry 重新 hash 到新表
3. 釋放舊表

Rehash 單次成本是 $O(n)$，但因為每插入 $n$ 個元素才會重建一次（等比擴張），插入操作的均攤時間複雜度 (Amortized Time) 仍是 $O(1)$。

常見考法

複雜度推導

• 平均查詢 $O(1)$（鏈結法）：$\alpha = n/m$ → 串列平均長度 $\alpha$ → 掃 $\alpha$ 個元素 = $O(1 + \alpha) = O(1)$（$\alpha$ 為常數）
• 平均查詢 $O(1)$（線性探測）：失敗平均探測數 $\approx \frac{1}{2}(1 + \frac{1}{(1-\alpha)^2})$；$\alpha = 0.5$ 時約 2.5 次
• 均攤插入 $O(1)$：$n$ 次插入總成本 $= n + (1 + 2 + 4 + \cdots + n) = O(n)$ → 每次均攤 $O(1)$

實務：JavaScript 的 Object / Map / Set

JS 內建三個 hash-table 類型，底層皆是 hash 表：

常見差異：

const o = {}
o[1] = 'a'
o['1'] = 'b'
console.log(o)           // \{ '1': 'b' \}  — 數字 key 被轉成字串，後面會覆蓋前面

const m = new Map()
m.set(1, 'a')
m.set('1', 'b')
console.log(m.size)      // 2 — key 型別嚴格區分

const s = new Set([1, 1, 2, '2'])
console.log(s.size)      // 3 — 數字 2 與字串 '2' 不同

Map 與 Set 的查詢、插入、刪除皆為 $O(1)$ 平均，且保留插入順序；Object 雖然也是 hash 表，但多了原型鏈與字串轉換等附帶邏輯，純 key-value 場景優先用 Map。