C++哈希表

「哈希表 hash table」，又稱「散列表」，其通過建立鍵 ?key? 與值 ?value? 之間的映射，實(shí)現(xiàn)高效的元素查詢。具體而言，我們向哈希表輸入一個(gè)鍵 ?key? ，則可以在 O(1) 時(shí)間內(nèi)獲取對應(yīng)的值 ?value? 。

如圖 6-1 所示，給定 n 個(gè)學(xué)生，每個(gè)學(xué)生都有“姓名”和“學(xué)號”兩項(xiàng)數(shù)據(jù)。假如我們希望實(shí)現(xiàn)“輸入一個(gè)學(xué)號，返回對應(yīng)的姓名”的查詢功能，則可以采用圖 6-1 所示的哈希表來實(shí)現(xiàn)。

圖 6-1   哈希表的抽象表示

除哈希表外，數(shù)組和鏈表也可以實(shí)現(xiàn)查詢功能，它們的效率對比如表 6-1 所示。

• 添加元素：僅需將元素添加至數(shù)組（鏈表）的尾部即可，使用 O(1) 時(shí)間。
• 查詢元素：由于數(shù)組（鏈表）是亂序的，因此需要遍歷其中的所有元素，使用 O(n) 時(shí)間。
• 刪除元素：需要先查詢到元素，再從數(shù)組（鏈表）中刪除，使用 O(n) 時(shí)間。

表 6-1   元素查詢效率對比

觀察發(fā)現(xiàn)，在哈希表中進(jìn)行增刪查改的時(shí)間復(fù)雜度都是 O(1) ，非常高效。

6.1.1   哈希表常用操作

哈希表的常見操作包括：初始化、查詢操作、添加鍵值對和刪除鍵值對等。

hash_map.cpp

/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
// 在哈希表中添加鍵值對 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鴨";

/* 查詢操作 */
// 向哈希表輸入鍵 key ，得到值 value
string name = map[15937];

/* 刪除操作 */
// 在哈希表中刪除鍵值對 (key, value)
map.erase(10583);

哈希表有三種常用遍歷方式：遍歷鍵值對、遍歷鍵和遍歷值。

hash_map.cpp

/* 遍歷哈希表 */
// 遍歷鍵值對 key->value
for (auto kv: map) {
    cout << kv.first << " -> " << kv.second << endl;
}
// 單獨(dú)遍歷鍵 key
for (auto key: map) {
    cout << key.first << endl;
}
// 單獨(dú)遍歷值 value
for (auto val: map) {
    cout << val.second << endl;
}

哈希表簡單實(shí)現(xiàn)

我們先考慮最簡單的情況，僅用一個(gè)數(shù)組來實(shí)現(xiàn)哈希表。在哈希表中，我們將數(shù)組中的每個(gè)空位稱為「桶 bucket」，每個(gè)桶可存儲一個(gè)鍵值對。因此，查詢操作就是找到 key 對應(yīng)的桶，并在桶中獲取 value 。

那么，如何基于 key 來定位對應(yīng)的桶呢？這是通過「哈希函數(shù) hash function」實(shí)現(xiàn)的。哈希函數(shù)的作用是將一個(gè)較大的輸入空間映射到一個(gè)較小的輸出空間。在哈希表中，輸入空間是所有 key ，輸出空間是所有桶（數(shù)組索引）。換句話說，輸入一個(gè) key ，我們可以通過哈希函數(shù)得到該 key 對應(yīng)的鍵值對在數(shù)組中的存儲位置。

輸入一個(gè) key ，哈希函數(shù)的計(jì)算過程分為以下兩步。

1. 通過某種哈希算法 hash() 計(jì)算得到哈希值。
2. 將哈希值對桶數(shù)量（數(shù)組長度）capacity 取模，從而獲取該 key 對應(yīng)的數(shù)組索引 index 。

index = hash(key) % capacity

隨后，我們就可以利用 index 在哈希表中訪問對應(yīng)的桶，從而獲取 value 。

設(shè)數(shù)組長度 ?capacity = 100?、哈希算法 ?hash(key) = key? ，易得哈希函數(shù)為 ?key % 100? 。圖 6-2 以 ?key? 學(xué)號和 ?value? 姓名為例，展示了哈希函數(shù)的工作原理。

圖 6-2   哈希函數(shù)工作原理

以下代碼實(shí)現(xiàn)了一個(gè)簡單哈希表。其中，我們將 ?key? 和 ?value? 封裝成一個(gè)類 ?Pair? ，以表示鍵值對。

array_hash_map.cpp

/* 鍵值對 */
struct Pair {
  public:
    int key;
    string val;
    Pair(int key, string val) {
        this->key = key;
        this->val = val;
    }
};

/* 基于數(shù)組簡易實(shí)現(xiàn)的哈希表 */
class ArrayHashMap {
  private:
    vector<Pair *> buckets;

  public:
    ArrayHashMap() {
        // 初始化數(shù)組，包含 100 個(gè)桶
        buckets = vector<Pair *>(100);
    }

    ~ArrayHashMap() {
        // 釋放內(nèi)存
        for (const auto &bucket : buckets) {
            delete bucket;
        }
        buckets.clear();
    }

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

    /* 查詢操作 */
    string get(int key) {
        int index = hashFunc(key);
        Pair *pair = buckets[index];
        if (pair == nullptr)
            return nullptr;
        return pair->val;
    }

    /* 添加操作 */
    void put(int key, string val) {
        Pair *pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets[index] = pair;
    }

    /* 刪除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        // 釋放內(nèi)存并置為 nullptr
        delete buckets[index];
        buckets[index] = nullptr;
    }

    /* 獲取所有鍵值對 */
    vector<Pair *> pairSet() {
        vector<Pair *> pairSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                pairSet.push_back(pair);
            }
        }
        return pairSet;
    }

    /* 獲取所有鍵 */
    vector<int> keySet() {
        vector<int> keySet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                keySet.push_back(pair->key);
            }
        }
        return keySet;
    }

    /* 獲取所有值 */
    vector<string> valueSet() {
        vector<string> valueSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                valueSet.push_back(pair->val);
            }
        }
        return valueSet;
    }

    /* 打印哈希表 */
    void print() {
        for (Pair *kv : pairSet()) {
            cout << kv->key << " -> " << kv->val << endl;
        }
    }
};

哈希沖突與擴(kuò)容

本質(zhì)上看，哈希函數(shù)的作用是將所有 key 構(gòu)成的輸入空間映射到數(shù)組所有索引構(gòu)成的輸出空間，而輸入空間往往遠(yuǎn)大于輸出空間。因此，理論上一定存在“多個(gè)輸入對應(yīng)相同輸出”的情況。

對于上述示例中的哈希函數(shù)，當(dāng)輸入的 ?key? 后兩位相同時(shí)，哈希函數(shù)的輸出結(jié)果也相同。例如，查詢學(xué)號為 12836 和 20336 的兩個(gè)學(xué)生時(shí)，我們得到：

12836 % 100 = 36
20336 % 100 = 36

如圖 6-3 所示，兩個(gè)學(xué)號指向了同一個(gè)姓名，這顯然是不對的。我們將這種多個(gè)輸入對應(yīng)同一輸出的情況稱為「哈希沖突 hash collision」。

圖 6-3   哈希沖突示例

容易想到，哈希表容量 n 越大，多個(gè) ?key? 被分配到同一個(gè)桶中的概率就越低，沖突就越少。因此，我們可以通過擴(kuò)容哈希表來減少哈希沖突。

如圖 6-4 所示，擴(kuò)容前鍵值對 (136, A) 和 (236, D) 發(fā)生沖突，擴(kuò)容后沖突消失。

圖 6-4   哈希表擴(kuò)容

類似于數(shù)組擴(kuò)容，哈希表擴(kuò)容需將所有鍵值對從原哈希表遷移至新哈希表，非常耗時(shí)。并且由于哈希表容量 capacity 改變，我們需要通過哈希函數(shù)來重新計(jì)算所有鍵值對的存儲位置，這進(jìn)一步提高了擴(kuò)容過程的計(jì)算開銷。為此，編程語言通常會預(yù)留足夠大的哈希表容量，防止頻繁擴(kuò)容。

「負(fù)載因子 load factor」是哈希表的一個(gè)重要概念，其定義為哈希表的元素?cái)?shù)量除以桶數(shù)量，用于衡量哈希沖突的嚴(yán)重程度，也常被作為哈希表擴(kuò)容的觸發(fā)條件。例如在 Java 中，當(dāng)負(fù)載因子超過 0.75 時(shí)，系統(tǒng)會將哈希表容量擴(kuò)展為原先的 2 倍。