哈希表、哈希桶（C++實作）【STL】

1. 哈希

1.1 概念

哈希（hash，中文：散列；音譯：哈希），是一種算法思想，又稱雜湊演算法、哈希函數、散列函數等。哈希函數能指導任何一種資料，構造出一種儲存結構，這種儲存結構能夠通過某種函數使得元素的儲存位置和資料本身的值（一般稱之為key值）能夠建立一種映射關系，這樣在查找資料時就可以通過同一個哈希函數通過key值迅速找到元素的位置。

這種查找思想類似于數組的随機通路，它的時間複雜度為 O ( 1 ) O(1) O(1)。不同于以往，即便是紅黑樹，它的查找時間複雜度也是 O ( l o g 2 N ) ) O(log_2N)) O(log2​N))。原因是不論是順序結構還是平衡樹中，元素的key值和儲存之間沒有映射關系，是以在查找元素時必須以key值進行若幹次比較，而這恰恰增加了時間複雜度。

map和set底層都是用二叉搜尋樹實作的，因而他們都是有序的。而unordered_set和unorder_map中的元素都是無序的，原因是它們底層都使用了哈希思想實作。前者能使用雙向疊代器，後者是單向疊代器。

這樣看，前者更占優勢，但為什麼還有有unordered（無序）。因為後者底層使用了雜湊演算法實作，是以使用這種容器查找資料的效率最高，時間複雜度是 O ( 1 ) O(1) O(1)，雖然後者的插入效率略低，但仍然能夠持平。

在了解unordered_set和unorder_map容器之前，需要對哈希思想有一定了解。

從哈希查找的效率可以知道，哈希專攻的是查找功能。

1.2 例子

生活中也有不少直接或間接使用哈希思想的例子，比如：

• 英語詞典；
• 花名冊，隻要知道你的學号就能快速找到你的個人資訊；
• 各種資料庫中賬号和密碼的映射…

因為有這樣的需求，一種新的資料結構誕生了：散清單。

散清單（hash table）也叫做哈希表，它提供了鍵（key）和值（value）之間的映射關系，隻要給出一個key，就能迅速找到對應的value，時間複雜度接近 O ( 1 ) O(1) O(1)。

在列舉出來的例子中，大多數元素的key值都是以字元串的形式存儲的，那麼如何用一個哈希函數将字元串轉化為一個整型的數組下标值呢？

哈希表的本質就是數組，使用哈希函數算出來的每個元素對應的位置都是數組的下标。這就是哈希函數保證查找元素的時間複雜度如此低的主要原因。

1.3 散清單的基本原理

1.3.1 哈希函數

在不同的語言中，哈希函數的實作都有所差別。最簡單的哈希函數實作方式是按數組長度取模運算：

為了示範友善，key值本身就是整型值，在後文中會介紹将字元串轉化為整型值的哈希函數：

h a s h ( k e y ) = k e y   %   c a p a c i t y hash(key) = key \ \% \ capacity hash(key)=key % capacity

例如，對于集合中元素：{0, 3, 15, 8, 12}，它們存儲在數組長度為10的哈希表中的位置如上。

1.3.2 哈希表的讀寫操作

• 插入：根據元素的key值，用哈希函數計算出它的儲存位置，并将元素存放在對應位置處。

從這樣的表述中大概可以猜到，要想讓查找效率時間複雜度達到 O ( 1 ) O(1) O(1)，就必須使用數組存放資料，才能實作随機通路的效果。

根據key值用哈希函數算出來的存儲位置就是數組的下标，

• 查找：用同一個哈希函數，根據元素的key值計算出元素的儲存位置，這個位置的元素的key值與要查找的key值相等，則取出該元素，查找成功；反之則否。

這種查找和插入的過程是類似的，都是先用（要存放的元素或要查找的元素的）key值計算處它的存儲位置，然後存放或取出該元素。

當查找元素時，隻需要通過key值使用同一個哈希函數即可直接找到元素對應的位置，查找效率堪比數組。

為什麼說「堪比」呢？

• 因為這種按數組長度取模運算的雜湊演算法會出現不同值對應同一個下标的情況，叫做哈希沖突。

1.4 哈希沖突

如上面的例子中，如果集合中多了幾個這樣的元素：

現在，新增的元素經過同一個哈希函數得到的數組下标值都已經被占有了，像這種不同的值映射到同一位置的情況，就叫做哈希沖突。

造成哈希沖突的原因之一是：哈希函數的設計不合理。

哈希函數的設計原則：

• 哈希函數的定義域必須包含需要儲存的全部key值，如果哈希表允許含有m個元素，那麼哈希函數的值域必須在[0, m-1]（數組下标從0開始）。
• 哈希函數計算出來的位址能較均勻地分散在這個哈希表中。
• 哈希函數應該比較簡單。

哈希沖突是無法避免的，解決哈希沖突的方法主要有兩種，一種是開放尋址法，一種是連結清單法。

1.4.1 開放尋址法

閉散列，也叫開放定址法，當發生哈希沖突時，可以将元素放在被占的元素的下一個不為空的位置，以此類推，直到放滿哈希表為止。

開放尋址法根據“開放”的程度不同，分為兩種：

• 線性探測
• 二次探測

線性探測

• 當發生線性沖突時，從發生沖突的位置開始，依次向後探測，直到遇到空位置為止。

H i = ( H 0   +   i )   %   c a p   , ( i = 1 , 2 , 3 , . . . ) H_i = (H_0 \ + \ i)\ \% \ cap \ ,(i = 1, 2, 3,...) Hi​=(H0​ + i) % cap ,(i=1,2,3,...)

其中：

• H 0 H_0 H0​：根據元素的key值通過哈希函數得到的數組下标值；
• H i H_i Hi​：造成沖突的元素（下标被占用的元素）通過線性探測以後得到的空位置；
• i i i：第i次沖突；
• c a p cap cap：表的長度。

同樣，以上面的例子而言：

優點

思路簡單，容易實作。

缺陷

像這樣按數組長度取模運算的哈希函數，我們把它叫做除留餘數法（下文還會介紹若幹常見哈希函數）。随着哈希表中資料的增多，發生哈希沖突的次數也會增加，且不限于key值相同與否，上圖中的示例中兩個key值僅沖突了一次。如果再插入key值=20的元素，就要發生6次哈希沖突。

随着元素個數的增多，插入元素發生哈希沖突的可能性越大，查找的效率也會随之變低。

從宏觀看，發生線性沖突的主要原因就是因為插入元素的分布不均勻，根據key值通過哈希函數算出來的下标值總是集中在某些區域。那麼線性探測就像“違章建築”，各自侵占别的哈希值的位置。

分布不均造成的“違章建築”，從數組的容量使用率來看，就是插入的元素太“滿”了才會把别的元素擠到其他地方，進而産生鍊式反應。是以可以限制插入元素的個數，減少不同的集中區域之間交叉的可能性。

負載因子

負 載 因 子   =   有 效 數 據 個 數   /   數 組 長 度 負載因子\ = \ 有效資料個數\ / \ 數組長度 負載因子 = 有效資料個數 / 數組長度

改變負載因子有兩方面，有效資料個數（分子）和數組長度（分母），由于資料個數無法限制，那麼我們可以通過改變數組長度進而改變負載因子。

• 負載因子越大，發生哈希沖突的機率越高，操作的效率越低。
• 負載因子越小，發生哈希沖突的機率越低，操作的效率越高。

同樣地，将上面例子中數組的大小增加到20：

當增加數組長度時，上面的同一組資料中，不論是未發生還是發生沖突的，都更均勻地分散在數組中。

負載因子的表達式說明負載因子其實就是空間使用率，負載因子越小，空間使用率越低。

一般而言，對于開放定址法，負載因子一般控制在[0.7, 0.8]，超過0.8就會導緻在查找時的效率呈指數級下降。

原因是CPU緩存不命中率(cache missing)會呈指數級上升。

連結：淺談 Cache

簡言之，根據局部性原理，CPU下次通路的資料很可能在上次通路的資料的周圍。

是以，使用數組實作線性探測時，控制擴容與否的主要因素已經不再是它是否已滿，而是負載因子是否超出範圍。負載因子的存在，會讓哈希表永遠不會滿。

二次探測

線性探測的缺點就是容易因為哈希值過于密集而出現“違章建築”，出現鍊式反應，一堆影響另一堆。雖提供了可行的方案，使用負載因子控制容量，但是它的應用場景也是有限的。

而二次探測是線上性探測的基礎上而言的：

H i = ( H 0   +   i 2 )    %   c a p ,   ( i = 1 , 2 , 3 , . . . ) H_i= (H_0\ +\ i ^2) \ \ \% \ cap ,\ (i = 1,2,3,...) Hi​=(H0​ + i2)  % cap, (i=1,2,3,...)

其中：

• H 0 H_0 H0​：根據元素的key值通過哈希函數得到的數組下标值；
• H i H_i Hi​：造成沖突的元素（下标被占用的元素）通過線性探測以後得到的空位置；
• i：第i次沖突；
• c a p cap cap：表的長度。

如果 j = i 2 j = i^2 j=i2即

H i = ( H 0   +   j )    %   c a p ,   ( j = 1 , 4 , 9 , . . . ) H_i= (H_0\ +\ j) \ \ \% \ cap ,\ (j = 1,4,9,...) Hi​=(H0​ + j)  % cap, (j=1,4,9,...)

用一個例子了解：

了解二次探測的過程，最重要的是了解i的含義，遇到幾次沖突，i就是幾。

優點

二次探測是對線性探測的優化，它對元素的分散程度大于線性探測中控制負載因子帶來的效果更好，畢竟是平方運算，當沖突次數越多，存放的位置也會離第一個沖突的位置越遠，也就越分散。

缺陷

由于二次探測是線性探測的優化，是以它也需要用負載因子控制哈希表的容量。

總地來說，開放尋址法（閉散列）最大的缺陷就是空間使用率較低，這同時也是哈希的缺陷，即使不采用上述優化，這種處理方式也會浪費一些空間。

1.4.2 連結清單法

閉散列，也叫連結清單法、鍊位址法、拉鍊法。将同一個哈希值對應的不同的key值視為一個集合，用一個連結清單儲存起來，把它叫做哈希桶。即每個哈希桶存放的都是哈希值相同的不同key值，每個哈希桶（連結清單）的首位址會被儲存在哈希表（數組）中，下标對應的就是哈希桶的哈希值。

插入元素時，隻需要根據key值通過哈希函數得出的下标找到對應的連結清單（哈希桶），依次往後連結即可。

用例子了解哈希桶組成的哈希表：

将數組橫着放，連結清單豎着放，這樣就能了解為什麼把這個存儲相同哈希值的不同key值的連結清單叫做哈希桶了。

一個題外話：

學到這裡突然明白了為什麼要有連結清單的存在，因為它能解決像這樣的哈希沖突問題，非常巧妙。

這也是資料結構存在的意義，Data Structure，就是用來存取資料的結構。例如在Linux作業系統中，一切皆檔案，要對檔案管理就必須先描述它們之間的關系，然後用統一的方法組織，這樣才能對檔案管理。

優點

不會産生資料之間的鍊式反應，不同哈希值對應的key值不會互相侵占位置。是以負載因子的存在隻會降低空間使用率，是以開散列的負載因子可以超過1，一般控制在1以下。

• 哈希桶實作的哈希表空間使用率高；
• 哈希桶在極端條件下還可以用紅黑樹解決。

缺點

極端情況：

全部元素的key值對應的哈希值都相同，它們都發生哈希沖突，全部都連結到同一個哈希桶中：

這樣查找的效率退化為 O ( N ) O(N) O(N)，在此之前，我們學過的最高效的查找結構就是紅黑樹，可以将連結清單換成紅黑樹。時間複雜度就提升到 O ( l o g 2 N ) O(log_2N) O(log2​N)。

在Java常用的HashMap中，當一個桶中元素個數超過8時，就會将連結清單換成紅黑樹。當少于8時，依然會使用連結清單存儲資料。但這不是必須的，因為有的時候哈希表中負載因子也會增大，最終會使哈希表擴容，哈希沖突次數減少，一個桶中元素的個數也會減少。

2. 實作閉散列哈希表

實作閉散列哈希表，其實就是控制數組下标對元素進行增删查改操作。

2.1 哈希表存儲結構

閉散列的查找有個坑，如果出現這種情況：

是以可以用枚舉常量規定每個位置的狀态：

// 枚舉常量表示位置狀态
enum State
{
    EMPTY,
    EXIST,
    DELETE
};
           

用枚舉常量辨別狀态時可行的，原因是如果按照原來的思路，通常會将未存放的位置的值置為-1等，但假如要放入的元素key值本來就為-1呢？

每個位置有三種情況，即已被占有（EXIST）、已被删除（DELETE）、未被占有（EMPTY）。之是以要設定為DELETE，就是為了避免上面的坑。

機關存儲結構

那麼，哈希表中每個位置都應該包含位置的狀态和資料：

// 哈希表中每個位置的存儲結構
template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;
};
           

由于哈希是由key值計算的數組下标，存的是元素的value值，是以每個元素存儲的是一個鍵值對，可以用pair結構體儲存。

當建立出一個位置時，它的預設狀态是空，是以給_state以預設值EMPTY。

哈希表

對于整個哈希表(HashTable)而言，其本質是一個數組，因為閉散列的優化中會使用負載因子控制數組長度，是以需要一個動态長度的數組，在此，我們直接使用STL中的vector容器，它的每個元素的類型都是HashData。

template<class K, class V>
class HashTable
{
public:
    // ...
private:
    vector<HashData<K, V>> _table; // 哈希表
    size_t _n = 0;                 // 負載因子
};
           

注意，數組元素的類型隻是每個位置的類型，因為每個位置要包含狀态和資料，是以它不僅僅是一個下标指定的位置。

key值轉整型

在本文開頭介紹哈希函數時，說到key值是要轉為整型才能對數組長度取模運算的，上文中都是以整型的key值為例，是以并未提到key值轉整型的例子。由于現實中key值還可能是字元串等類型，是以可以使用仿函數+模闆特化的方式來比對不同類型的key值轉化為整型值。

直接轉整型

當key值本身是整型時，隻需要傳回強轉為

size_t

後的值即可。

size_t 類型定義在cstddef頭檔案中，該檔案是C标準庫的頭檔案stddef.h的C++版。 它是一個與機器相關的unsigned類型，其大小足以保證存儲記憶體中對象的大小。 --來源于網絡

至于為什麼要轉化成unsigned類型，是因為當%取模運算操作符的右邊為負數時，本身就會發生隐式類型轉換，将負數轉換為正數。

如：

-17 % 10 = -7

17 % -10 = 7

-17 % -10 = -7

// 仿函數
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};
           

同時，哈希表的類中也要增加一個模闆參數，以将key值轉化為整型值：

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
    // ...
}
           

将key值轉化函數的預設值設定為HashFunc。

字元串轉整型

許多場景中，key值都是字元串類型的，将字元串轉化為整型值有很多辦法，比如首字元ASCII值，但是這樣哈希沖突的機率太大了。字元串作為一種經常被使用的類型，有許多大佬都對字元串轉整型的哈希函數有自己的見解，其主流思想是：

• 将字元串的每個字元的ASCII值累加得到整型的哈希值；

BKDRHash算法：

這是是Kernighan和Dennis在《The C programming language》中提出的，它對每次累加後的結果再乘以素數131。

至于為什麼是素數131，這是個數學問題，衆所周知計算機科學家都是數學家。

因為我們之前已經實作了整型本身轉整型的仿函數，是以如果想要讓别的類型轉化為整型，需要用到模闆的特化：

// BKDRHash算法
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t ret = 0;
        for(auto& e : key)
        {
            ret *= 131;
            ret += e;
        }
        return ret;
    }
};
           

2.2 閉散列哈希表的查找

1. 判斷哈希表長度是否為0，是0則查找失敗；
2. 根據key值通過哈希函數得到下标值；
3. 從得到的下标值開始，在哈希表中向後線性探測，遇到DELETE繼續；遇到EMPTY結束，查找失敗；遇到key值相等的元素則查找成功。

// 查找函數
HashData<K, V>* Find(const K& key)
{
    if (_table.size() == 0)
    {
        return nullptr;
    }

    Hash hash;
    size_t size = _table.size();
    size_t start = hash(key) % size;    // 根據key值通過哈希函數得到下标值
    size_t hashi = start;

    while (_table[hashi]._state != EMPTY)
    {
        if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
        {
            return &_table[hashi];
        }
        hashi++;
        hashi %= size;

        if (hashi == start)
        {
            break;
        }
    }
    return nullptr;
}
           

2.3 閉散列哈希表的插入

插入步驟

1. 若哈希表中已存在key值對應的元素，插入失敗；
2. 以負載因子為名額判斷是否要對哈希表擴容；
3. 插入元素；
4. 有效元素計數器+1。

擴容步驟

1. 若哈希表最初的大小為0，則設定哈希表大小為10；
2. 若哈希表的負載因子大于0.7，則需要建立一個大小是原大小兩倍的新數組。然後周遊原數組，将所有元素插入到新數組；
3. 将新的數組的位址更新到哈希表中。

因為擴容改變了數組的長度，哈希函數也随之變化，每個元素的位置都有可能改變。

更新哈希表的步驟

1. 根據元素的key值通過新的哈希函數得到下标值；
2. 若産生哈希沖突，則從哈希沖突的位置開始，向後線性探測，直到遇到狀态為EMPTY或DELETE的位置；
3. 插入元素，将位置的狀态更新為EXIST。

bool Insert(const pair<K, V> kv)
{
    if (Find(kv.first) != nullptr)            // 哈希表中已存在相同key值的元素
    {
        return false;
    }

    // 擴容操作
    if (_table.size() == 0 || _size * 10 / _table.size() >= 7) // 擴容
    {
        size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;

        HashTable<K, V, Hash> newHashTable;  // 建立新哈希表
        newHashTable._table.resize(newSize); // 擴容
        for (auto& e : _table) // 周遊原哈希表
        {
            if (e._state == EXIST)
            {
                newHashTable.Insert(e._kv); // 映射到新哈希表
            }
        }
        _table.swap(newHashTable._table);
    }

    // 插入操作
    Hash hash;
    size_t size = _table.size();
    size_t hashi = hash(kv.first) % size;   // 得到key值對應的哈希值
    while (_table[hashi]._state == EXIST)   // 線性探測
    {
        int i = 0;
        i++;
        hashi = (hashi + i) % size;
    }

    // 探測到空位置，下标是hashi
    _table[hashi]._kv = kv;                 // 插入元素，更新位置上的kv值
    _table[hashi]._state = EXIST;           // 更新位置的狀态
    ++_size;                                // 更新有效元素個數

    return true;
}
           

2.4 閉散列哈希表的删除

删除一個元素隻需要将該位置的狀态改成DELETE即可。

// 删除函數
bool Erase(const K& key)
{
    HashData<K, V>* find = Find(key);
    if(find != nullptr)
    {
        find->_state = DELETE;
        _size--;
        return true;
    }
    return false;
}
           

3. 實作開散列哈希表

3.1 哈希表結構

開頭介紹的連結清單法，哈希表（數組）的每一個位置存儲的都是一個連結清單的頭結點位址。每個哈希桶存儲的資料都是一個結點類型，這個結點類就是連結清單中的結點。

結點類

template<class K, class V>
struct HashNode
{
    pair<K, V> _kv;         // 鍵值對
    HashNode<K, V>* _next;  // 後繼指針
    // 結點構造函數
    HashNode(const pair<K, V> kv)
        :_kv(kv)
        , _next(nullptr)
    {}
};
           

由于模闆參數和命名的繁雜，為了代碼的可讀性，可以将結點類typedef為Node：

哈希表

哈希表底層一個動态長度的數組，同樣地，使用STL的vector做為哈希表。數組中的每個元素類型都是Node*。

template<class K, class V>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    // ... 
private:
    vector<Node*> _table;
    size_t _size = 0;
};
           

3.2 開散列哈希表的查找

1. 判斷哈希表長度是否為0，是0則查找失敗；
2. 根據key值通過哈希函數得到下标值；
3. 找到下标值對應的哈希桶，周遊單連結清單。

// 查找函數
HashNode<K, V>* Find(const K& key)
{
    if(_table.size() == 0)
    {
        return nullptr;
    }

    size_t pos = key % _table.size(); // 得到下标值
    HashNode<K, V>* cur = _table[pos];  // 找到哈希桶首位址
    while (cur)                         // 周遊連結清單
    {
        if (cur->_kv.first == key)
        {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}
           

3.3 開散列哈希表的插入

步驟和閉散列哈希表的插入是類似的，不同的是開散列的負載因子是到1才會擴容。

插入步驟

1. 若哈希表中已存在key值對應的元素，插入失敗；
2. 以負載因子為名額判斷是否要對哈希表擴容；
3. 插入元素；
4. 有效元素計數器+1。

擴容步驟

1. 若哈希表最初的大小為0，則設定哈希表大小為10；
2. 若哈希表的負載因子等于1，則需要建立一個大小是原大小兩倍的新數組。然後周遊原數組，将所有元素插入到新數組；
3. 将新的數組的位址更新到哈希表中。

因為擴容改變了數組的長度，哈希函數也随之變化，每個元素的位置都有可能改變。

更新哈希表的步驟

1. 根據元素的key值通過新的哈希函數得到下标值；
2. 若産生哈希沖突，直接頭插到下标位置的單連結清單即可；

注意

當擴容需要将舊哈希表資料遷移到新哈希表中時，直接在周遊的同時通過新的哈希函數計算出的下标值連結到對應的哈希桶（連結清單）即可。不複用Insert函數的原因是Insert函數會在其内部new一個Node然後再插入，像這樣遷移資料的動作不斷new和delete（函數結束會自動delete釋放資源）的操作會帶來不必要的開銷。

哈希桶可以用任意連結清單實作，單雙連結清單皆可。但是在此為了代碼上的簡單，使用了單連結清單，因為此節重點是學習哈希思想，連結清單應該在之前就已經掌握了。其次，對單連結清單的操作是頭插和頭删。原因是不管是什麼類型的連結清單，它的插入和查找的時間複雜度都是 O ( N ) O(N) O(N)，這麼做的目的是提高插入（主要）和删除的效率。

// 插入函數
bool Insert(const pair<K, V>& kv)
{
    if(Find(kv.first) != nullptr) // 元素已經存在
    {
        return false;
    }

    // 擴容操作
    if(_size == _table.size())
    {
        size_t oldSize = _table.size();
        size_t newSize = oldSize == 0 ? 10 : 2 * oldSize;
        vector<Node*> newTable;                         // 建立新表
        newTable.resize(newSize);                       // 擴容
        for(size_t i = 0; i < oldSize; i++)             // 轉移資料
        {
            Node* cur = _table[i];                      // 下标i對應的連結清單的首位址
            while(cur)
            {
                Node* next = cur->_next;

                size_t hashi = cur->_kv.first % newSize;// 新下标值
                cur->_next = newTable[hashi];           // 重新連結
                newTable[hashi] = cur;

                cur = next;                             // 連結清單向後疊代
            }
            _table[i] = nullptr;
        }
        _table.swap(newTable);                          // 替換新哈希表
    }

    // 頭插元素
    size_t hashi = kv.first % _table.size();
    Node* newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    _size++;

    return true;
}
           

3.4 開散列哈希表的删除

1. 根據元素的key值通過哈希函數得到哈希桶的标号；
2. 周遊哈希桶，找到待删除結點；
3. 找到則删除結點并釋放結點資源；
4. 更新哈希表中元素個數計數器。

注意

由于哈希桶是由連結清單實作的，是以即使先用Find找到key值對應的結點，删除時依然要周遊連結清單，因為單連結清單的删除需要知道它上一個結點的位址。

// 删除函數
bool Erase(const K& key)
{
    size_t pos = key % _table.size();       // 得到key值對應的哈希桶下标
    Node* prev = nullptr;
    Node* cur = _table[pos];
    while (cur)
    {
        if(cur->_kv.first == key)           // 找到和key值對應的結點
        {
            if (prev == nullptr)            // 找到的結點在連結清單首部
            {
                _table[pos] = cur->_next;   // 直接将頭部往後移動一個機關
            }
            else                            // 找到的結點不在連結清單首部
            {
                prev->_next = cur->_next;   // 直接跳過它即可
            }

            delete cur;                     // 釋放結點資源
            _size--;                        // 更新計數器
            return true;
        }
        prev = cur;                         // 疊代
        cur = cur->_next;
    }
    return false;
}
           

4. 補充

4.1 哈希表的大小為何是素數

在本文的開頭介紹了一個哈希函數BKDRHash算法，它對每次累加後的結果再乘以素數131。我想原理都是類似的，對于哈希思想，要想發揮它的優勢，即查找，就必須揚長避短，避免哈希沖突。

這裡有一篇文章和一個讨論詳細介紹了哈希表的大小是素數能減少哈希沖突的原因：哈希表的大小為何是素數、Why is it best to use a prime number as a mod in a hashing function?

文中一開始例子中的數列，因子是數列元素之間的間隔。

總地來說，這是由模運算這種運算方式決定的：

A   %   B A \ \% \ B A % B

其中：

• A：被模數，通常是key值；
• B：模數，通常是哈希表長度。

由于 A % B A\%B A%B的結果是 A / B A/B A/B的餘數，這個餘數就是哈希表的下标，也是判斷哈希沖突的依據。當A和B之間存在非1的公共因子時，它們會出現多次結果相同的情況（這就是産生哈希沖突的情況），假設其中一個相同的結果是C。

原因：

A總是能通過B乘以一個非負整數再加上C來表示，例如：A是4的倍數，B是8：

A%B	結果
4%8	4
8%8
12%8	4
16%8
20%8	4

對于A和B，用結果表示A：

A	=	B	*	非負整數	+	結果
4	=	8	*	+	4
8	=	8	*	1	+
12	=	8	*	1	+	4
16	=	8	*	2	+
20	=	8	*	2	+	4

這個表格也是計算A%B的原理，出現相同的結果的原因就是A和B之間存在若幹非1公共因子。想降低發生哈希沖突的機率，就是減少出現相同哈希值的次數，是以就要減少A和B的公共因子個數，由于每個數都有一個因子是1，是以使哈希表的長度為素數。

在stl_hashtable.h中，專門有一個數組儲存了素數，相鄰素數之間相差一倍，每當需要擴容時，都從這個數組中找下一個素數作為新哈希表的長度。

static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457, 
  1610612741, 3221225473, 4294967291
};
           

是以上面的擴容操作中可以用這個素數數組優化。

// 擷取新哈希表素數長度
size_t GetNextPrime(size_t prime)
{
	const int PRIMECOUNT = 28;
	size_t i = 0;
	for (i = 0; i < PRIMECOUNT; i++)
	{
		if (MyPrimeList[i] > prime)
			return MyPrimeList[i];
	}
	return MyPrimeList[i];
}
           

4.2 哈希函數

哈希函數除了上面常用的直接定址法和除留餘數法以外，還有下面幾種常見的哈希函數：

平方取中法

假設關鍵字為 1234，對它平方就是 1522756，抽取中間的 3 位 227 作為哈希位址。使用場景：不知道關鍵字的分布，而位數又不是很大的情況。

折疊法

折疊法是将關鍵字從左到右分割成位數相等的幾部分（最後一部分位數可以短些），然後将這幾部分疊加求和，并按哈希表表長，取後幾位作為哈希位址。

使用場景：折疊法适合事先不需要知道關鍵字的分布，或關鍵字位數比較多的情況。

随機數法

選擇一個随機函數，取關鍵字的随機函數值為它的哈希位址，即

H a s h ( K e y ) = r a n d o m ( K e y ) Hash(Key)=random(Key) Hash(Key)=random(Key)

其中：

• random為随機數函數。

使用場景：通常應用于關鍵字長度不等時。

數字分析法

設有N個M位數，每一位可能有X種不同的符号，這X中不同的符号在各位上出現的頻率不一定相同，可能在某些位上分布比較均勻，每種符号出現的機會均等，而在某些位上分布不均勻，隻有幾種符号經常出現。此時，我們可根據哈希表的大小，選擇其中各種符号分布均勻的若幹位作為哈希位址。

假設要存儲某家公司員工登記表，如果用手機号作為關鍵字，那麼極有可能前7位都是相同的，那麼我們可以選擇後面的四位作為哈希位址。

如果這樣的抽取方式還容易出現沖突，還可以對抽取出來的數字進行反轉（如1234改成4321）、右環位移（如1234改成4123）、左環位移（如1234改成2341）、前兩數與後兩數疊加（如1234改成12+34=46）等操作。

數字分析法通常适合處理關鍵字位數比較大的情況，或事先知道關鍵字的分布且關鍵字的若幹位分布較均勻的情況。