閱讀(688) 書簽贊(0) 我要糾錯

C++哈希沖突

2023-09-20 09:18 更新

上節(jié)提到，通常情況下哈希函數的輸入空間遠大于輸出空間，因此理論上哈希沖突是不可避免的。比如，輸入空間為全體整數，輸出空間為數組容量大小，則必然有多個整數映射至同一數組索引。

哈希沖突會導致查詢結果錯誤，嚴重影響哈希表的可用性。為解決該問題，我們可以每當遇到哈希沖突時就進行哈希表擴容，直至沖突消失為止。此方法簡單粗暴且有效，但效率太低，因為哈希表擴容需要進行大量的數據搬運與哈希值計算。為了提升效率，我們可以采用以下策略。

改良哈希表數據結構，使得哈希表可以在存在哈希沖突時正常工作。
僅在必要時，即當哈希沖突比較嚴重時，才執(zhí)行擴容操作。

哈希表的結構改良方法主要包括“鏈式地址”和“開放尋址”。

鏈式地址

在原始哈希表中，每個桶僅能存儲一個鍵值對?！告準降刂?separate chaining」將單個元素轉換為鏈表，將鍵值對作為鏈表節(jié)點，將所有發(fā)生沖突的鍵值對都存儲在同一鏈表中。圖 6-5 展示了一個鏈式地址哈希表的例子。

鏈式地址哈希表

圖 6-5 鏈式地址哈希表

哈希表在鏈式地址下的操作方法發(fā)生了一些變化。

查詢元素：輸入 key ，經過哈希函數得到數組索引，即可訪問鏈表頭節(jié)點，然后遍歷鏈表并對比 key 以查找目標鍵值對。
添加元素：先通過哈希函數訪問鏈表頭節(jié)點，然后將節(jié)點（即鍵值對）添加到鏈表中。
刪除元素：根據哈希函數的結果訪問鏈表頭部，接著遍歷鏈表以查找目標節(jié)點，并將其刪除。

鏈式地址存在以下局限性。

占用空間增大，鏈表包含節(jié)點指針，它相比數組更加耗費內存空間。
查詢效率降低，因為需要線性遍歷鏈表來查找對應元素。

以下代碼給出了鏈式地址哈希表的簡單實現，需要注意兩點。

使用列表（動態(tài)數組）代替鏈表，從而簡化代碼。在這種設定下，哈希表（數組）包含多個桶，每個桶都是一個列表。
以下實現包含哈希表擴容方法。當負載因子超過 0.75 時，我們將哈希表擴容至 2 倍。

hash_map_chaining.cpp

/* 鏈式地址哈希表 */
class HashMapChaining {
  private:
    int size;                       // 鍵值對數量
    int capacity;                   // 哈希表容量
    double loadThres;               // 觸發(fā)擴容的負載因子閾值
    int extendRatio;                // 擴容倍數
    vector<vector<Pair *>> buckets; // 桶數組

  public:
    /* 構造方法 */
    HashMapChaining() : size(0), capacity(4), loadThres(2.0 / 3), extendRatio(2) {
        buckets.resize(capacity);
    }

    /* 析構方法 */
    ~HashMapChaining() {
        for (auto &bucket : buckets) {
            for (Pair *pair : bucket) {
                // 釋放內存
                delete pair;
            }
        }
    }

    /* 哈希函數 */
    int hashFunc(int key) {
        return key % capacity;
    }

    /* 負載因子 */
    double loadFactor() {
        return (double)size / (double)capacity;
    }

    /* 查詢操作 */
    string get(int key) {
        int index = hashFunc(key);
        // 遍歷桶，若找到 key 則返回對應 val
        for (Pair *pair : buckets[index]) {
            if (pair->key == key) {
                return pair->val;
            }
        }
        // 若未找到 key 則返回 nullptr
        return nullptr;
    }

    /* 添加操作 */
    void put(int key, string val) {
        // 當負載因子超過閾值時，執(zhí)行擴容
        if (loadFactor() > loadThres) {
            extend();
        }
        int index = hashFunc(key);
        // 遍歷桶，若遇到指定 key ，則更新對應 val 并返回
        for (Pair *pair : buckets[index]) {
            if (pair->key == key) {
                pair->val = val;
                return;
            }
        }
        // 若無該 key ，則將鍵值對添加至尾部
        buckets[index].push_back(new Pair(key, val));
        size++;
    }

    /* 刪除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        auto &bucket = buckets[index];
        // 遍歷桶，從中刪除鍵值對
        for (int i = 0; i < bucket.size(); i++) {
            if (bucket[i]->key == key) {
                Pair *tmp = bucket[i];
                bucket.erase(bucket.begin() + i); // 從中刪除鍵值對
                delete tmp;                       // 釋放內存
                size--;
                return;
            }
        }
    }

    /* 擴容哈希表 */
    void extend() {
        // 暫存原哈希表
        vector<vector<Pair *>> bucketsTmp = buckets;
        // 初始化擴容后的新哈希表
        capacity *= extendRatio;
        buckets.clear();
        buckets.resize(capacity);
        size = 0;
        // 將鍵值對從原哈希表搬運至新哈希表
        for (auto &bucket : bucketsTmp) {
            for (Pair *pair : bucket) {
                put(pair->key, pair->val);
                // 釋放內存
                delete pair;
            }
        }
    }

    /* 打印哈希表 */
    void print() {
        for (auto &bucket : buckets) {
            cout << "[";
            for (Pair *pair : bucket) {
                cout << pair->key << " -> " << pair->val << ", ";
            }
            cout << "]\n";
        }
    }
};

值得注意的是，當鏈表很長時，查詢效率 O $(n)$ 很差。此時可以將鏈表轉換為“AVL 樹”或“紅黑樹”，從而將查詢操作的時間復雜度優(yōu)化至 $O (\log ? n)$ 。

開放尋址

「開放尋址 open addressing」不引入額外的數據結構，而是通過“多次探測”來處理哈希沖突，探測方式主要包括線性探測、平方探測、多次哈希等。

1. 線性探測

線性探測采用固定步長的線性搜索來進行探測，其操作方法與普通哈希表有所不同。

插入元素：通過哈希函數計算數組索引，若發(fā)現桶內已有元素，則從沖突位置向后線性遍歷（步長通常為 1 ），直至找到空位，將元素插入其中。
查找元素：若發(fā)現哈希沖突，則使用相同步長向后線性遍歷，直到找到對應元素，返回 value 即可；如果遇到空位，說明目標鍵值對不在哈希表中，返回 None 。

圖 6-6 展示了一個在開放尋址（線性探測）下工作的哈希表。

開放尋址和線性探測

圖 6-6 開放尋址和線性探測

然而，線性探測存在以下缺陷。

不能直接刪除元素。刪除元素會在數組內產生一個空位，當查找該空位之后的元素時，該空位可能導致程序誤判元素不存在。為此，通常需要借助一個標志位來標記已刪除元素。
容易產生聚集。數組內連續(xù)被占用位置越長，這些連續(xù)位置發(fā)生哈希沖突的可能性越大，進一步促使這一位置的聚堆生長，形成惡性循環(huán)，最終導致增刪查改操作效率劣化。

以下代碼實現了一個簡單的開放尋址（線性探測）哈希表。

我們使用一個固定的鍵值對實例 removed 來標記已刪除元素。也就是說，當一個桶內的元素為 None 或 removed 時，說明這個桶是空的，可用于放置鍵值對。
在線性探測時，我們從當前索引 index 向后遍歷；而當越過數組尾部時，需要回到頭部繼續(xù)遍歷。

hash_map_open_addressing.cpp

/* 開放尋址哈希表 */
class HashMapOpenAddressing {
  private:
    int size;               // 鍵值對數量
    int capacity;           // 哈希表容量
    double loadThres;       // 觸發(fā)擴容的負載因子閾值
    int extendRatio;        // 擴容倍數
    vector<Pair *> buckets; // 桶數組
    Pair *removed;          // 刪除標記

  public:
    /* 構造方法 */
    HashMapOpenAddressing() {
        // 構造方法
        size = 0;
        capacity = 4;
        loadThres = 2.0 / 3.0;
        extendRatio = 2;
        buckets = vector<Pair *>(capacity, nullptr);
        removed = new Pair(-1, "-1");
    }

    /* 哈希函數 */
    int hashFunc(int key) {
        return key % capacity;
    }

    /* 負載因子 */
    double loadFactor() {
        return static_cast<double>(size) / capacity;
    }

    /* 查詢操作 */
    string get(int key) {
        int index = hashFunc(key);
        // 線性探測，從 index 開始向后遍歷
        for (int i = 0; i < capacity; i++) {
            // 計算桶索引，越過尾部返回頭部
            int j = (index + i) % capacity;
            // 若遇到空桶，說明無此 key ，則返回 nullptr
            if (buckets[j] == nullptr)
                return nullptr;
            // 若遇到指定 key ，則返回對應 val
            if (buckets[j]->key == key && buckets[j] != removed)
                return buckets[j]->val;
        }
        return nullptr;
    }

    /* 添加操作 */
    void put(int key, string val) {
        // 當負載因子超過閾值時，執(zhí)行擴容
        if (loadFactor() > loadThres)
            extend();
        int index = hashFunc(key);
        // 線性探測，從 index 開始向后遍歷
        for (int i = 0; i < capacity; i++) {
            // 計算桶索引，越過尾部返回頭部
            int j = (index + i) % capacity;
            // 若遇到空桶、或帶有刪除標記的桶，則將鍵值對放入該桶
            if (buckets[j] == nullptr || buckets[j] == removed) {
                buckets[j] = new Pair(key, val);
                size += 1;
                return;
            }
            // 若遇到指定 key ，則更新對應 val
            if (buckets[j]->key == key) {
                buckets[j]->val = val;
                return;
            }
        }
    }

    /* 刪除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        // 線性探測，從 index 開始向后遍歷
        for (int i = 0; i < capacity; i++) {
            // 計算桶索引，越過尾部返回頭部
            int j = (index + i) % capacity;
            // 若遇到空桶，說明無此 key ，則直接返回
            if (buckets[j] == nullptr)
                return;
            // 若遇到指定 key ，則標記刪除并返回
            if (buckets[j]->key == key) {
                delete buckets[j]; // 釋放內存
                buckets[j] = removed;
                size -= 1;
                return;
            }
        }
    }

    /* 擴容哈希表 */
    void extend() {
        // 暫存原哈希表
        vector<Pair *> bucketsTmp = buckets;
        // 初始化擴容后的新哈希表
        capacity *= extendRatio;
        buckets = vector<Pair *>(capacity, nullptr);
        size = 0;
        // 將鍵值對從原哈希表搬運至新哈希表
        for (Pair *pair : bucketsTmp) {
            if (pair != nullptr && pair != removed) {
                put(pair->key, pair->val);
            }
        }
    }

    /* 打印哈希表 */
    void print() {
        for (auto &pair : buckets) {
            if (pair != nullptr) {
                cout << pair->key << " -> " << pair->val << endl;
            } else {
                cout << "nullptr" << endl;
            }
        }
    }
};

多次哈希

顧名思義，多次哈希方法是使用多個哈希函數 f1(x)、f2(x)、f3(x)、… 進行探測。

插入元素：若哈希函數 f1(x) 出現沖突，則嘗試 f2(x) ，以此類推，直到找到空位后插入元素。
查找元素：在相同的哈希函數順序下進行查找，直到找到目標元素時返回；或遇到空位或已嘗試所有哈希函數，說明哈希表中不存在該元素，則返回 None 。

與線性探測相比，多次哈希方法不易產生聚集，但多個哈希函數會增加額外的計算量。

編程語言的選擇

Java 采用鏈式地址。自 JDK 1.8 以來，當 HashMap 內數組長度達到 64 且鏈表長度達到 8 時，鏈表會被轉換為紅黑樹以提升查找性能。

Python 采用開放尋址。字典 dict 使用偽隨機數進行探測。

Golang 采用鏈式地址。Go 規(guī)定每個桶最多存儲 8 個鍵值對，超出容量則連接一個溢出桶；當溢出桶過多時，會執(zhí)行一次特殊的等量擴容操作，以確保性能。

以上內容是否對您有幫助：

← C++哈希表

C++哈希算法 →

寫筆記

我要補充