算法系列：哈希表衝突解決——鏈地址法完整實現與性能分析

核心思想

**鏈地址法** ：將哈希值相同的鍵值對存入同一條鏈表。
哈希表 = 數組 Node* buckets[M]，每個桶是鏈表頭指針。

完整 Java 實現

public class HashST {
    private static class Node {
        Key key;
        Value val;
        Node next;
        Node(Key k, Value v, Node n) { key = k; val = v; next = n; }
    }

    private Node[] table;
    private int M = 97; // 桶數，質數減少衝突
    private int N = 0;  // 鍵值對總數

    public HashST() { table = new Node[M]; }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public Value get(Key key) {
        int i = hash(key);
        for (Node x = table[i]; x != null; x = x.next)
            if (key.equals(x.key)) return x.val;
        return null;
    }

    public void put(Key key, Value val) {
        int i = hash(key);
        for (Node x = table[i]; x != null; x = x.next)
            if (key.equals(x.key)) { x.val = val; return; }
        table[i] = new Node(key, val, table[i]); // 头插法
        if (++N > M * 10) resize(M * 2); // 負載因子 > 10 擴容
    }

    private void resize(int newM) {
        HashST tmp = new HashST<>();
        tmp.M = newM;
        tmp.table = new Node[newM];
        for (int i = 0; i < M; ++i)
            for (Node x = table[i]; x != null; x = x.next)
                tmp.put(x.key, x.val);
        this.M = tmp.M;
        this.table = tmp.table;
    }
}

關鍵設計點

性能分析

• **平均情況**：O(1 + α)，α 為負載因子。良好哈希函數下 α ≈ 1 即近似 O(1)。
• **最壞情況**：所有鍵落入同一桶 → O(N) (退化為鏈表)。
• **空間**：O(M + N)。

優化方向

1. 樹化桶 (Java 8 HashMap)：桶長度 > 8 且 M > 64 時轉為紅黑樹，最壞 O(log N)。
2. 開放定址法：線性探測/二次探測/雙重哈希，無指針開銷，缓存友好。
3. 鴨子哈希 / Cuckoo Hashing：兩張表 + 兩個哈希函數，最壞 O(1) 查找。
4. 並發哈希表：分段鎖 / CAS 無鎖 (ConcurrentHashMap)。

對比：鏈地址法 vs 開放定址法

總結

鏈地址法是 **哈希表最經典、最通用** 的衝突解決方案。
掌握：哈希函數去符號取模 → 頭插法鏈表 → 負載因子觸發擴容 → 重新哈希。
現代工業級實現 (Java 8+, C++ unordered_map) 多採用 **鏈表 + 樹化 + 開放定址混合** 策略，根據數據特性自適應。