哈希思想深度解析：從基礎原理到工程級開鏈表實現與衝突處理藝術

哈希表本質：數組 O(1) 訪問 + 鏈表 O(1) 插入

散列表將鍵通過哈希函數映射為數組下標，衝突鍵掛在該下標的鏈表上（開鏈法）。核心優勢：

• 查找：O(1) 定位桶 + O(链长) 遍歷
• 插入/刪除：同理，鏈表操作 O(1)
• 空間：O(n + 桶數)

哈希函數設計藝術

黃金法則：好的哈希函數讓桶分佈盡可能均勻，負載因子 α = n/桶數 控制在 0.7~1.0，必要時 rehash 擴容。

開鏈表完整工程級實現（C++ 模板）

template<class T, class Hash = std::hash<T>, class Eq = std::equal_to<T>>
class HashTable {
    struct Node {
        T key; Node* next;
        Node(const T& k, Node* n) : key(k), next(n) {}
    };
    vector<Node*> buckets;
    Hash hasher; Eq eq;
    size_t sz = 0;
    static constexpr float MAX_LOAD = 0.75;

    size_t idx(const T& k) const { return hasher(k) % buckets.size(); }

    void rehash() {
        vector<Node*> old = buckets;
        buckets.assign(buckets.size() * 2, nullptr);
        sz = 0;
        for (auto head : old)
            for (Node* p = head; p; p = p->next)
                insert(p->key);
    }

public:
    HashTable(size_t n = 101) : buckets(n, nullptr) {}  // 質數起始

    bool insert(const T& key) {
        if (find(key)) return false;
        size_t i = idx(key);
        buckets[i] = new Node(key, buckets[i]);
        if (++sz > buckets.size() * MAX_LOAD) rehash();
        return true;
    }

    bool find(const T& key) const {
        for (Node* p = buckets[idx(key)]; p; p = p->next)
            if (eq(p->key, key)) return true;
        return false;
    }

    bool erase(const T& key) {
        size_t i = idx(key);
        Node **pp = &buckets[i];
        while (*pp) {
            if (eq((*pp)->key, key)) {
                Node* del = *pp;
                *pp = del->next;
                delete del;
                --sz;
                return true;
            }
            pp = &(*pp)->next;
        }
        return false;
    }

    ~HashTable() {
        for (auto head : buckets)
            while (head) { Node* t = head; head = head->next; delete t; }
    }
};

為什麼堅決不推薦閉散列（開放定址法）？

1. 聚集效應：線性探測導致主聚集，二次探測導致次聚集，雙重哈希雖緩解但複雜
2. 刪除困難：需引入「墓碑」標記，增加實現複雜度
3. 負載因子敏感：α 超 0.7 性能劇降，而開鏈法 α>1 仍可工作
4. 不適合大對象：數組存對象副本，移動開銷大；開鏈法存指針
5. 擴容代價高：需重新探測所有鍵，開鏈法只需重掛鏈表

除非極度追求緩存局部性且鍵值極小（如 int->int），否則開鏈法是工程首選。

哈希思想的泛化應用

• 布隆過濾器：多哈希函數 + 位數組，空間極省的近似去重
• 一致性哈希：環狀哈希空間 + 虛擬節點，分佈式路由核心
• 字符串匹配：Rabin-Karp 滾動哈希，O(n+m) 多模式匹配
• 數據完整性：MD5/SHA 系列密碼學哈希，防篡改
• 負載均衡：哈希 IP/Session 到後端，保證會話親和性

總結

哈希表是時空權衡的經典範例：用額外空間（桶數組）換取極速查找。掌握哈希函數選擇、衝突解決策略、動態擴容機制、負載因子控制四大核心，即可靈活應對從嵌入式去重到分佈式路由的各種場景。記住：開鏈法通用、質數取模基礎、rehash 必備、閉散列慎用。