C++哈希沖突

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

哈希沖突會(huì)導(dǎo)致查詢結(jié)果錯(cuò)誤，嚴(yán)重影響哈希表的可用性。為解決該問(wèn)題，我們可以每當(dāng)遇到哈希沖突時(shí)就進(jìn)行哈希表擴(kuò)容，直至沖突消失為止。此方法簡(jiǎn)單粗暴且有效，但效率太低，因?yàn)楣１頂U(kuò)容需要進(jìn)行大量的數(shù)據(jù)搬運(yùn)與哈希值計(jì)算。為了提升效率，我們可以采用以下策略。

1. 改良哈希表數(shù)據(jù)結(jié)構(gòu)，使得哈希表可以在存在哈希沖突時(shí)正常工作。
2. 僅在必要時(shí)，即當(dāng)哈希沖突比較嚴(yán)重時(shí)，才執(zhí)行擴(kuò)容操作。

哈希表的結(jié)構(gòu)改良方法主要包括“鏈?zhǔn)降刂贰焙汀伴_放尋址”。

鏈?zhǔn)降刂?/h2>

在原始哈希表中，每個(gè)桶僅能存儲(chǔ)一個(gè)鍵值對(duì)。「鏈?zhǔn)降刂?separate chaining」將單個(gè)元素轉(zhuǎn)換為鏈表，將鍵值對(duì)作為鏈表節(jié)點(diǎn)，將所有發(fā)生沖突的鍵值對(duì)都存儲(chǔ)在同一鏈表中。圖 6-5 展示了一個(gè)鏈?zhǔn)降刂饭１淼睦印?/p>

圖 6-5   鏈?zhǔn)降刂饭１?br>

哈希表在鏈?zhǔn)降刂废碌牟僮鞣椒òl(fā)生了一些變化。

• 查詢?cè)兀狠斎?nbsp;key ，經(jīng)過(guò)哈希函數(shù)得到數(shù)組索引，即可訪問(wèn)鏈表頭節(jié)點(diǎn)，然后遍歷鏈表并對(duì)比 key 以查找目標(biāo)鍵值對(duì)。
• 添加元素：先通過(guò)哈希函數(shù)訪問(wèn)鏈表頭節(jié)點(diǎn)，然后將節(jié)點(diǎn)（即鍵值對(duì)）添加到鏈表中。
• 刪除元素：根據(jù)哈希函數(shù)的結(jié)果訪問(wèn)鏈表頭部，接著遍歷鏈表以查找目標(biāo)節(jié)點(diǎn)，并將其刪除。

鏈?zhǔn)降刂反嬖谝韵戮窒扌浴?/p>

• 占用空間增大，鏈表包含節(jié)點(diǎn)指針，它相比數(shù)組更加耗費(fèi)內(nèi)存空間。
• 查詢效率降低，因?yàn)樾枰€性遍歷鏈表來(lái)查找對(duì)應(yīng)元素。

以下代碼給出了鏈?zhǔn)降刂饭１淼暮?jiǎn)單實(shí)現(xiàn)，需要注意兩點(diǎn)。

• 使用列表（動(dòng)態(tài)數(shù)組）代替鏈表，從而簡(jiǎn)化代碼。在這種設(shè)定下，哈希表（數(shù)組）包含多個(gè)桶，每個(gè)桶都是一個(gè)列表。
• 以下實(shí)現(xiàn)包含哈希表擴(kuò)容方法。當(dāng)負(fù)載因子超過(guò) 0.75 時(shí)，我們將哈希表擴(kuò)容至 2 倍。

hash_map_chaining.cpp

/* 鏈?zhǔn)降刂饭１?*/
class HashMapChaining {
  private:
    int size;                       // 鍵值對(duì)數(shù)量
    int capacity;                   // 哈希表容量
    double loadThres;               // 觸發(fā)擴(kuò)容的負(fù)載因子閾值
    int extendRatio;                // 擴(kuò)容倍數(shù)
    vector<vector<Pair *>> buckets; // 桶數(shù)組

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

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

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

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

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

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

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

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

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

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

開放尋址

「開放尋址 open addressing」不引入額外的數(shù)據(jù)結(jié)構(gòu)，而是通過(guò)“多次探測(cè)”來(lái)處理哈希沖突，探測(cè)方式主要包括線性探測(cè)、平方探測(cè)、多次哈希等。

1.   線性探測(cè)

線性探測(cè)采用固定步長(zhǎng)的線性搜索來(lái)進(jìn)行探測(cè)，其操作方法與普通哈希表有所不同。

• 插入元素：通過(guò)哈希函數(shù)計(jì)算數(shù)組索引，若發(fā)現(xiàn)桶內(nèi)已有元素，則從沖突位置向后線性遍歷（步長(zhǎng)通常為 1 ），直至找到空位，將元素插入其中。
• 查找元素：若發(fā)現(xiàn)哈希沖突，則使用相同步長(zhǎng)向后線性遍歷，直到找到對(duì)應(yīng)元素，返回 value 即可；如果遇到空位，說(shuō)明目標(biāo)鍵值對(duì)不在哈希表中，返回 None 。

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

圖 6-6   開放尋址和線性探測(cè)

然而，線性探測(cè)存在以下缺陷。

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

以下代碼實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的開放尋址（線性探測(cè)）哈希表。

• 我們使用一個(gè)固定的鍵值對(duì)實(shí)例 removed 來(lái)標(biāo)記已刪除元素。也就是說(shuō)，當(dāng)一個(gè)桶內(nèi)的元素為 None 或 removed 時(shí)，說(shuō)明這個(gè)桶是空的，可用于放置鍵值對(duì)。
• 在線性探測(cè)時(shí)，我們從當(dāng)前索引 index 向后遍歷；而當(dāng)越過(guò)數(shù)組尾部時(shí)，需要回到頭部繼續(xù)遍歷。

hash_map_open_addressing.cpp

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

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

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

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

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

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

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

    /* 擴(kuò)容哈希表 */
    void extend() {
        // 暫存原哈希表
        vector<Pair *> bucketsTmp = buckets;
        // 初始化擴(kuò)容后的新哈希表
        capacity *= extendRatio;
        buckets = vector<Pair *>(capacity, nullptr);
        size = 0;
        // 將鍵值對(duì)從原哈希表搬運(yùn)至新哈希表
        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;
            }
        }
    }
};

多次哈希

顧名思義，多次哈希方法是使用多個(gè)哈希函數(shù) f1(x)、f2(x)、f3(x)、… 進(jìn)行探測(cè)。

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

與線性探測(cè)相比，多次哈希方法不易產(chǎn)生聚集，但多個(gè)哈希函數(shù)會(huì)增加額外的計(jì)算量。

編程語(yǔ)言的選擇

Java 采用鏈?zhǔn)降刂?。?JDK 1.8 以來(lái)，當(dāng) HashMap 內(nèi)數(shù)組長(zhǎng)度達(dá)到 64 且鏈表長(zhǎng)度達(dá)到 8 時(shí)，鏈表會(huì)被轉(zhuǎn)換為紅黑樹以提升查找性能。

Python 采用開放尋址。字典 dict 使用偽隨機(jī)數(shù)進(jìn)行探測(cè)。

Golang 采用鏈?zhǔn)降刂?。Go 規(guī)定每個(gè)桶最多存儲(chǔ) 8 個(gè)鍵值對(duì)，超出容量則連接一個(gè)溢出桶；當(dāng)溢出桶過(guò)多時(shí)，會(huì)執(zhí)行一次特殊的等量擴(kuò)容操作，以確保性能。