高階數據結構——哈希表的實現

1.概念引入

2.哈希的概念：

2.1 什么叫映射？

2.2 直接定址法

2.3 哈希沖突（哈希碰撞）

2.4 負載因子

2.5?哈希函數

2.5.1?除法散列法（除留余數法）

2.5.2?乘法散列法（了解）

2.5.3 全域散列法（了解）

2.5.4 處理哈希沖突

2.5.4.1 開放地址法：

2.5.4.1.1 線性探測

2.5.4.1.1.1 基本框架

?2.5.4.1.1.2?插入+線性探測

?2.5.4.1.1.3?查找+線性探測

?2.5.4.1.1.4?刪除+線性探測

?2.5.4.1.1.5?總結：

2.5.4.1.1 二次探測

2.5.4.2 鏈地址法：

?2.5.4.2.1 基本框架：

?2.5.4.2.2?插入+擴容：

??2.5.4.2.3?查找：

???2.5.4.2.4?刪除：

????2.5.4.2.4 析構：

?2.5.4.2.5? 代碼總結：

1.概念引入

咱們一開始看見哈希，之前從來沒見過這個東西，是不是感到很厲害的樣子？相信大家都去過超市吧，當你買了一個商品，你拿到柜臺，人家一輸入這個商品的名稱，機器上面就會顯示這個物品的價格，是不是查找很快速。這其實就是一種哈希表的實現。

2.哈希的概念：

哈希(hash)又稱散列，是?種組織數據的方式。從譯名來看，有散亂排列的意思。本質就是通過哈希函數把關鍵字Key跟存儲位置建立?個映射關系，查找時通過這個哈希函數計算出Key存儲的位置，進行快速查找。

2.1 什么叫映射？

咱們打個比方，比如你上高中的時候，你班里有個人叫做張三，但是他有個外號叫做“雞哥”，那么雞哥就是他，當別人喊雞哥的時候，張三知道喊的就是他，而不是李四，這就是映射。即可以快速的找到那個人。

一般哈希的實現方法有很多種，下面咱們來講一種關鍵字的范圍比較集中的。

2.2 直接定址法

當關鍵字的范圍比較集中時，直接定址法就是非常簡單高效的方法，比如?組關鍵字都在[0,99]之間，那么我們開?個100個數的數組，每個關鍵字的值直接就是存儲位置的下標。再比如?組關鍵字值都在 [a,z]的小寫字母，那么我們開?個26個數的數組，每個關鍵字acsii碼-aascii碼就是存儲位置的下標。也就是說直接定址法本質就是用關鍵字計算出一個絕對位置或者相對位置。

2.3 哈希沖突（哈希碰撞）

已知咱們使用的直接定址法是每個元素有每個元素的空，互相不占用彼此的空間。但是事實上真是如此嘛？并不是，理想狀態上是哈希沖突為0，但也只是理想狀態，咱們只有不斷地減少哈希沖突，不可能消滅哈希沖突。那么哈希沖突（哈希碰撞）就是，我有兩個不同的值，但是占用了同一個位置。那么此時就需要方法去解決這個哈希沖突。

當關鍵字的范圍比較分散時，直接定址法就很浪費內存甚至內存不夠用。

2.4 負載因子

再講能夠實現的方法之前，還得講一個東西，那就是負載因子，這個是用來判斷擴容的時機的。即負載因子到達一定得值就擴容。那么這個負載因子是如何計算的呢？假設哈希表中已經映射存儲了N個值，哈希表的大小為M，那么 N 負載因子?=N/M ，負載因子有些地方?也翻譯為載荷因子/裝載因子等，他的英文為loadfactor。負載因子越大，哈希沖突的概率越高，空間利用率越高；負載因子越小，哈希沖突的概率越低，空間利用率越低；(這個M是size(),不是capacity()）

你想一想，這個負載因子可以想像為就是空間占有率（空間利用率），這個空間利用率高了，那么這個插入的元素就多了，那么相應的哈希沖突的概率是不是就提高了，因為沒有剩余的空間了，所有的空間都有數據，你碰到一個跟你值相同的概率就會增大。

2.5?哈希函數

咱們之前說了，要設計一個方法去解決哈希沖突，那么設計的方法就是哈希函數。?個好的哈希函數應該讓N個關鍵字被等概率的均勻的散列分布到哈希表的M個空間中，但是實際中卻很難做到，但是我們要盡量往這個方向去考量設計。

2.5.1?除法散列法（除留余數法）

1.除法散列法也叫做除留余數法，這個方法用來找到映射的位置。假設哈希表的大小為M，那么通過key除以M的余數作為映射位置的下標，也就是哈希函數為：h(key)=key%M。

插話：咱們知道取模，只能取整數的模，如果key是整數還好，直接模就可以了，那如果說key不是整數呢？比如浮點數，字符串，結構體，那么該怎么辦呢？咱們在這只講字符串的處理方法，叫做BKDR 哈希算法：

由Brian Kernighan 和 Dennis Ritchie 提出

用于將字符串轉換為哈希值。它的核心思想是通過一個質數種子（如31、131等）不斷乘以當前哈希值并加上字符的ASCII碼值，從而生成一個分布均勻的哈希值。

BKDR 算法的核心公式為：
????????hash=(hash×seed)+current_char

seed：預定義的質數（如 31、131、1313 等），作為乘法基數。

current\_char：字符串當前字符的 ASCII 值。

hash：初始值為 0，逐字符迭代計算最終哈希值。

為什么要引入一個種子呢？

假如，有一個字符串是"abc",另外一個字符串是"bca",這倆字符串肯定是不一樣的對嗎，那么如果說咱們只加它們對應的ascii值的話，就會導致它們最后的哈希結果是一樣的，但這不是咱們想要的結果，所以為了避免這種情況的出現，就引入了一個種子，每次加之后，都乘以這個種子，那么就可以避免這種情況的出現了。

計算過程示例（以?seed = 131，字符串?"abc"?為例）：

初始值：hash = 0

處理字符?'a'（ASCII 97）：
hash=0×131+97=97hash=0×131+97=97

處理字符?'b'（ASCII 98）：
hash=97×131+98=12,785hash=97×131+98=12,785

處理字符?'c'（ASCII 99）：
hash=12,785×131+99=1,675,854hash=12,785×131+99=1,675,854

最終哈希值為?1,675,854。

那么這個種子為什么一定要選擇131呢？哈哈，這是兩位大佬進行很多次試驗后得出的，要是真想知道，可以去問兩位大佬。

代碼實現：

//對于可以直接轉換為整形的，直接轉換即可
template<class K>
struct HashFunc
{size_t operator()(const K& key) const{return (size_t)key;}
};// 對于string類型（不可以直接轉換為整形的）需要進行特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key) const{size_t hash = 0;for (auto ch : key){hash += ch;hash *= 131;}return hash;}
};

2.那么這個M的選擇，也是有講究的。要盡量避免M為某些值，如2的冪，10的冪等。如果是2^x ，那么key%2^x 本質相當于保留key的后X位(這個是保留的二進制的key的后x位），那么后x位相同的值，計算出的哈希值都是?樣的，就沖突了。如： {63 , 31}看起來沒有關聯的值，如果M是16，也就是 2^4，那么計算出的哈希值都是15，因為63的二進制后8位是00111111，31的?進制后8位是00011111。（這里就只比較了二進制的后8位，但咱們知道二進制有32位，這里有個知識點，就是比較的位數越多，哈西沖突的概率就越小。所以這里只比較了8位，肯定不好）如果是 10^x(10進制）?，就更明顯了，保留的都是 10進值的后x位，如：{112,12312}，如果M是100，也就是10^2 ，那么計算出的哈希值都是12。（這里也不是比較的全部的位數）

3.當使用除法散列法時，建議M取不太接近2的整數次冪的?個質數(素數)。（這個其實不用太擔心，因為咱們庫里面會給的，就是素數集合，咱們只要用就可以了）。

2.5.2?乘法散列法（了解）

上面講的是觸發散列法，這個講乘法散列法，下面還會講一個全域散列法，但這倆只是了解，你真正的使用的時候，還是除法散列法使用的最多。可以理解為，除法散列法是講一個大數字，化為需要的哈希值。而乘法散列法是將一個小數字，化為需要的哈希值。?

1.乘法散列法對哈希表大小M沒有要求，他的大思路第?步：用關鍵字K乘上常數A(0<A<1)，并抽取出k*A的小數部分。第二步：后再用M乘以k*A的小數部分，再向下取整。

2.h(key) = floor(M ×((A ×key)%1.0)) ，其中floor表示對表達式進行下取整，A∈(0,1)，這里?最重要的是A的值應該如何設定，Knuth認為 A =( ? 5 1)/2 = 0.6180339887.... (黃金分割點]) 比較好。

3.乘法散列法對哈希表大小M是沒有要求的，假設M為1024，key為1234，A=0.6180339887,A*key = 762.6539420558，取小數部分為0.6539420558, M×((A×key)%1.0)=0.6539420558*1024= 669.6366651392，那么h(1234)=669。

4.適用于常規數據場景，無需對抗攻擊，且需快速哈希計算的場景（如內部數據結構）。

2.5.3 全域散列法（了解）

1.如果存在?個惡意的對手，他針對我們提供的散列函數，特意構造出?個發?嚴重沖突的數據集，比如，讓所有關鍵字全部落入同?個位置中。這種情況是可以存在的，只要散列函數是公開且確定的，就可以實現此攻擊。解決方法自然是見招拆招，給散列函數增加隨機性，攻擊者就方法找出確定可以導致最壞情況的數據。這種方法叫做全域散列。

2. h ab (key) = ((a ×key +b)%P)%M ，P需要選?個足夠大的質數，a可以隨機選[1,P-1]之間的 h (8) = 任意整數，b可以隨機選[0,P-1]之間的任意整數，這些函數構成了?個P*(P-1)組全域散列函數組。假設P=17，M=6，a=3，b=4,則 h 34 (8)= ((3 ×8+4)%17)%6 = 5 。

3.需要注意的是每次初始化哈希表時，隨機選取全域散列函數組中的?個散列函數使用，后續增刪查改都固定使用這個散列函數，否則每次哈希都是隨機選?個散列函數，那么插入是?個散列函數，查找又是另?個散列函數，就會導致找不到插入的key了。

4.適用于安全敏感場景（如網絡服務處理用戶輸入），防止惡意攻擊導致哈希性能退化。

2.5.4 處理哈希沖突

咱們一般還是選擇除法散列法來處理哈希沖突。當然哈希表無論選擇什么哈希函數也避免不了沖突，那么插?數據時，如何解決沖突呢？主要有兩種兩種方法，開放定址法和鏈地址法。

2.5.4.1 開放地址法：

在開放定址法中所有的元素都放到哈希表里，當?個關鍵字key用哈希函數計算出的位置沖突了，則按照某種規則找到?個沒有存儲數據的位置進行存儲，開放定址法中負載因子一定是小于的。這?的規則有三種：線性探測、二次探測、雙重探測。

2.5.4.1.1 線性探測

1.從發生沖突的位置開始，依次線性向后探測，直到尋找到下一個沒有存儲數據的位置為止，如果走?到哈希表尾，則回繞到哈希表頭的位置。

2.h(key) = hash0 = key % M ?i = {1,2,3,...,M ?1} , hash0位置沖突了，則線性探測公式為：hc(key,i) = hashi = (hash0+i)?%?M ， ?i?=?{1,2,3,...,M ?1}，（就是從當前位置開始往后找，遇到表尾，直接%M，就可以回到表頭了，所以%M的作用是為了回到表頭。直到找到空位置去存放這個key）因為負載因子小于1，則最多探測M-1次，?定能找到?個存儲key的位置。（由于負載因子是小于1的，所以整個空間總有空位置，所以總有位置給我存儲key的值）。

3.下?演示{19,30,5,36,13,20,21,12}等這一組值映射到M=11的表中。

h(19) = 8 ， h(30) = 8 ， h(5) = 5 ， h(36) = 3 ， h(13) = 2 ， h(20) = 9 ， h(21) = 10 ， h(12) = 1

?在看代碼之前，我還是想說一下，就是對于開放地址法，咱們要創建一整個表，那么表中的元素，需要存儲鍵值對，以及元素此時的狀態（這里不光存儲鍵值對，存儲key也可以，只不過這里咱們用鍵值對來實現）。

2.5.4.1.1.1 基本框架

//根據當前容量 n，返回一個預定義的素數表中大于等于 n 的最小素數，用于哈希表擴容。
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.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};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;// >=const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}
enum State
{EXIST,EMPTY,DELETE
};
//開放尋址法需要一個連續存儲的數組，每個位置不僅要存儲數據，
//還需要記錄該位置的狀態（是否被占用、已刪除等），因此每個元素是HashData結構體，所以是vector<HashData<K, V>> _tables;
//直接存儲鍵值對和狀態
//那么既然每個元素是HashData結構體，那么自然_table[i],訪問的是元素
//自然這個也是可以調用HashData這個結構體里的成員變量的
//例如_table[i]._kv,_table[i].__state
//那么由于_table是vector類型的，只不過_table中的元素是HashData結構體
//所以說_table是可以調用vector中的任意成員函數的。//每個元素的類型
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};//在C++中，模板類或函數可以指定默認模板參數。這意味著當用戶不顯式提供某個模板參數時，
//編譯器會使用默認值。在這里，`class Hash = HashFunc<K>` 表示如果用戶沒有為第三個模板參數
// （即 `Hash`）提供具體類型，編譯器將默認使用 `HashFunc<K > ` 作為該參數的類型
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable(size_t n = __stl_next_prime(0)):_tables(n), _n(0){}
private:vector<HashData<K, V>> _tables;size_t _n;   // 實際存儲的數據個數
};

?2.5.4.1.1.2?插入+線性探測

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;//找不到才插入，找到了插入干啥// 擴容，負載因子==0.7就擴容if ((double)_n / (double)_tables.size() >= 0.7){HashTable<K, V, Hash> newht(__stl_next_prime(_tables.size() + 1));// 遍歷舊表，將舊表的數據全部重新映射到新表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newht.Insert(_tables[i]._kv);}}_tables.swap(newht._tables);}Hash hs;size_t hash0 = hs(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;// 線性探測， (hash0+i) % Mwhile (_tables[hashi]._state == EXIST){hashi = hash0 + i;i++;hashi %= _tables.size();}//因為你是插入元素，所以說那個結構體里的成員變量都需要修改_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}

大家看插入代碼，邏輯其實很簡單，主要就是求出哈希值，求出哈希值之后，就去找為空的位置進行插入。插入完了之后別忘了更新元素中的成員變量的狀態。（這里的插入，是以hash0作為一開始的值，i是不斷增加的，從而實現了不斷向后尋找空狀態的代碼）并且更新實際存儲的元素數量_n。?

再看擴容代碼，當負載因子為0.7的時候進行擴容，別忘了強轉，因為兩個整數相除得不到浮點數。之后創建一個哈希表，表中的元素位置的數量，看上面的素數表。注意，這里的表的類型是HashTable<K, V, Hash>，那是因為這里咱們只創建了一個表，但是等到了下面（待會講的哈希桶），表的類型是vector<Node*>，里面的每個元素是 Node* 類型（指向哈希節點的指針）。之后判斷原表中的元素存不存在，若存在，就使用遞歸插入到新表中（復用插入那部分的代碼）。插入完了之后，別忘了交換兩個表的指針。因為你定義的新表是臨時變量（在函數中定義的），出了作用域就銷毀了，而咱們不要舊表，要新表，所以將他倆交換一下（交換指針即可）。從而，舊表出了作用域就銷毀了。非常nice。

這里還需要強調的一點是，代碼中的Hash hs，其實是實例化了一個仿函數。目的就是將key轉換為可以模的整形數。?

?2.5.4.1.1.3?查找+線性探測

//這個僅僅只是為了尋找元素，所以返回類型是HashData<K,V>（元素類型）,而沒有第三個模板參數
HashData<K, V>* Find(const K& key)
{Hash hs;size_t hash0 = hs(key) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 線性探測，(hash0+i) % Mhashi = hash0 + i;i++;hashi %= _tables.size();}return nullptr;
}

這里的查找你只能到元素狀態不為空的地方去查找吧。并且你如果查找到了那個值，那個值的狀態還得是存在（這個后面刪除的部分會講為什么），這樣才可以返回這個元素的地址。否則就是往后線性探測，直到找到位置。如果最后還沒有找到，那么就返回nullptr即可。

?2.5.4.1.1.4?刪除+線性探測

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}
}

這個刪除沒什么好說的，只是用到了一個偽刪除。將要被刪除的元素的狀態置為刪除狀態即可。那么這樣的話，如果查找元素的時候，如果不加個元素的狀態判斷語句，很可能就將已經刪除的元素也給查找上去，所以這就是為什么查找要加一個判斷狀態必須存在，接下來才是查找的元素與表中的元素相不相等。?

?2.5.4.1.1.5?總結：

完整代碼：

//根據當前容量 n，返回一個預定義的素數表中大于等于 n 的最小素數，用于哈希表擴容。
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.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};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;// >=const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}//對于可以直接轉換為整形的，直接轉換即可
template<class K>
struct HashFunc
{size_t operator()(const K& key) const{return (size_t)key;}
};// 對于string類型（不可以直接轉換為整形的）需要進行特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key) const{size_t hash = 0;for (auto ch : key){hash += ch;hash *= 131;}return hash;}
};namespace open_adrress
{enum State{EXIST,EMPTY,DELETE};//開放尋址法需要一個連續存儲的數組，每個位置不僅要存儲數據，//還需要記錄該位置的狀態（是否被占用、已刪除等），因此每個元素是HashData結構體，所以是vector<HashData<K, V>> _tables;//直接存儲鍵值對和狀態//那么既然每個元素是HashData結構體，那么自然_table[i],訪問的是元素//自然這個也是可以調用HashData這個結構體里的成員變量的//例如_table[i]._kv,_table[i].__state//那么由于_table是vector類型的，只不過_table中的元素是HashData結構體//所以說_table是可以調用vector中的任意成員函數的。//每個元素的類型template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};//在C++中，模板類或函數可以指定默認模板參數。這意味著當用戶不顯式提供某個模板參數時，//編譯器會使用默認值。在這里，`class Hash = HashFunc<K>` 表示如果用戶沒有為第三個模板參數// （即 `Hash`）提供具體類型，編譯器將默認使用 `HashFunc<K > ` 作為該參數的類型template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(size_t n = __stl_next_prime(0)):_tables(n), _n(0){}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//找不到才插入，找到了插入干啥// 擴容，負載因子==0.7就擴容if ((double)_n / (double)_tables.size() >= 0.7){HashTable<K, V, Hash> newht(__stl_next_prime(_tables.size() + 1));// 遍歷舊表，將舊表的數據全部重新映射到新表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newht.Insert(_tables[i]._kv);}}_tables.swap(newht._tables);}Hash hs;size_t hash0 = hs(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;// 線性探測， (hash0+i) % Mwhile (_tables[hashi]._state == EXIST){hashi = hash0 + i;i++;hashi %= _tables.size();}//因為你是插入元素，所以說那個結構體里的成員變量都需要修改_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}//這個僅僅只是為了尋找元素，所以返回類型是HashData<K,V>（元素類型）,而沒有第三個模板參數HashData<K, V>* Find(const K& key){Hash hs;size_t hash0 = hs(key) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 線性探測，(hash0+i) % Mhashi = hash0 + i;i++;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n;   // 實際存儲的數據個數};

線性探測的比較簡單且容易實現，線性探測的問題假設，hash0位置連續沖突，hash0，hash1， hash2位置已經存儲數據了，后續映射到hash0，hash1，hash2，hash3的值都會爭奪hash3位置，這種現象叫做群集/堆積。下面的二次探測可以?定程度改善這個問題。

2.5.4.1.1 二次探測

1.從發生沖突的位置開始，依次左右按二次方跳躍式探測，直到尋找到下?個沒有存儲數據的位置為止，如果往右走到哈希表尾，則回繞到哈希表頭的位置；如果往左走到哈希表頭，則回繞到哈希表尾的位置；

2.h(key) = hash0 = key % M , hash0位置沖突了，則二次探測公式為： ? hc(key,i) = hashi = (hash0±i ) % M ， i = {1,2,3,..., M/2}

3.?次探測當hashi = (hash0?i )%M時，當hashi<0時，需要hashi+=M.

4.下面演示{19,30,52,63,11,22}等這?組值映射到M=11的表中

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0?

其實就是講填的每個元素的間隔增大了，從而減少沖突，但是這個本質上解決不了問題，所以?引入了另外一種方法：

2.5.4.1.1 雙重散列（了解）

1.第?個哈希函數計算出的值發生沖突，使用第?個哈希函數計算出?個跟key相關的偏移量值，不斷往后探測，直到尋找到下一個沒有存儲數據的位置為止。

?2.?h 1 (key) = hash0 = key % M , hash0位置沖突了，則雙重探測公式為： hc(key,i) = hashi = (hash0+ i?h(key)) % M，?i?={1,2,3,..., M}。

3.要求h2(key)<M且h2(key)和M互為質數，有兩種簡單的取值方法:1、當M為2整數冪時，
h2(key)從[0，M-1]任選一個奇數;2、當M為質數時，h2(key)=key%(M-1)+ 1。

4.保證h2(key)與M互質是因為根據固定的偏移量所尋址的所有位置將形成一個群，若最大公約數
p=gcd(M,hi(key))>1，那么所能尋址的位置的個數為M/P<M，使得對于一個關鍵字來
說無法充分利用整個散列表。舉例來說，若初始探查位置為1，偏移量為3，整個散列表大小為12，那么所能尋址的位置為[1，4,7,10}，尋址個數為12/gcd(12，3)=4。

5.下面演示{19,30,52,74}，等這?組值映射到M=11的表中，設 h(key)?= 2? key%10+1。

2.5.4.2 鏈地址法：

解決沖突的思路：

開放定址法中所有的元素都放到哈希表里，鏈地址法中所有的數據不再直接存儲在哈希表中，哈希表中存儲?個指針，沒有數據映射這個位置時，這個指針為空，有多個數據映射到這個位置時，我們把這些沖突的數據鏈接成?個鏈表，掛在哈希表這個位置下面，鏈地址法也叫做拉鏈法或者哈希桶。

下面演示{19,30,5,36,13,20,21,12,24,96}等這?組值映射到M=11的表中。

h(19) = 8 ， h(30) = 8 ， h(5) = 5 ， h(36) = 3 ， h(13) = 2 ， h(20) = 9 ， h(21) = 10 ， h(12) = 1,h(24) = 2,h(96) = 88?

需要注意的是上面的0，1，2，3，4.........這些才是同，而桶下面掛的不是桶，而是鏈表，鏈表存儲元素。

?2.5.4.2.1 基本框架：

//而鏈地址法的每個桶是一個鏈表，因此_tables的每個元素是一個指向鏈表頭節點的指針，所以是vector<Node*> _tables;
// 即vector里存的是每個元素，又因為每個元素是指針，所以存的是Node*
// 在下一個類中，進行了typedef HashNode<K, V> Node;
// 所以說，表中的每個元素也是可以使用HashNode的成員變量的。
//鏈表節點（Node）包含實際的鍵值對和指向下一個節點的指針。
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){}
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{typedef HashNode<K, V> Node;
public:HashTable(size_t n = __stl_next_prime(0)):_tables(n, nullptr)//創建一個大小為n的數組，每個桶初始化為空指針//這個是整個大的外殼是_table，是要初始化為n個元素，每個桶初始化為空指針//而上面寫的HashNode的初始化是針對于每個元素的初始化，可以看成是外殼里面的小部分, _n(0){}
private:vector<Node*> _tables;//每個元素是一個鏈表的頭指針，表示哈希桶中的一個桶size_t _n;				// 實際存儲有效數據個數
};

這里的表中的元素需要存儲的不同于開放地址法，這個表中元素需要存儲的是鍵值對以及指向下一個元素的指針！?

?2.5.4.2.2?插入+擴容：

咱們先來看插入：

插入一般選擇頭插，而頭插入的話，分為桶中有元素以及桶中沒有元素。這兩種方法都是同一種代碼：

// 頭插
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];// 將當前節點的 next 指向新表的當前桶頭節點
_tables[hashi] = newnode;// 更新新表的當前桶頭節點為當前節點
//這種插入方法既適用于桶中有節點的，也適用于桶中沒有節點的，即當前節點是最新節點
//如果新表的桶 `hashi` 已經有節點A，那么插入節點B后，B的 `_next` 指向A，
// 新表的頭節點變為B，形成 `B->A` 的結構。
++_n;

那么擴容，有兩種方法。

方法一：

HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1));// 遍歷舊表，將舊表的數據全部重新映射到新表
// 為每個節點創建新的`Node`對象（因為`newht.Insert`會創建新節點）。
for (size_t i = 0; i < _tables.size(); i++)
{Node* cur = _tables[i];while (cur){newht.Insert(cur->_kv);cur = cur->_next;}
}
_tables.swap(newht._tables);
/*特點遞歸插入：遍歷舊表的每個節點，調用 newht.Insert 將數據插入新表。這會觸發完整的插入邏輯（計算哈希、處理沖突）。內存開銷：每個節點會重新創建新的 Node 對象，舊節點隨后被釋放（舊表析構時）。潛在問題：重復計算哈希：每次插入都要重新計算哈希值。內存分配頻繁：為每個節點分配新內存，效率較低。*/

這種寫法得遞歸復用插入的那部分代碼，并且還得重新創建節點，還得釋放舊表中的節點，很浪費空間，效率還不高。

方法二：

	// 擴容vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);//表示創建一個大小為 __stl_next_prime(_tables.size() + 1) 的數組，// 每個桶初始化為空指針。// 遍歷舊表，將舊表的數據全部重新映射到新表//復用舊節點，僅調整指針，不創建新節點。for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// cur頭插到新表size_t hashi = hs(cur->_kv.first) % newtables.size();cur->_next = newtables[hashi];// 將當前節點的 next 指向新表的當前桶頭節點newtables[hashi] = cur;// 更新新表的當前桶頭節點為當前節點cur = next;}_tables[i] = nullptr;//遍歷舊表的每個桶后，將舊表的桶指針設為`nullptr`。//這是因為節點已經被轉移到新表中，舊表不再擁有這些節點的所有權，// 避免重復釋放或訪問已轉移的節點}_tables.swap(newtables);
}
/*特點節點復用：直接復用舊表的 Node 節點，僅調整指針指向，不創建新對象。高效內存管理：無需分配新內存，避免頻繁的 new / delete 操作。哈希計算優化：每個節點只需計算一次哈希值（舊表節點直接插入新表對應桶）*/。

第二種方法就很好了，直接拿著節點過去，也不用擔心創建，銷毀節點的問題了。效率自然也是高了不少，那么還有一些其他的注意事項，我都寫在了代碼中，大家自行閱讀。所以更推薦大家使用第二種擴容方式。

總代碼：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;Hash hs;// 負載因子到1擴容，if (_n == _tables.size()){//HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1));遍歷舊表，將舊表的數據全部重新映射到新表// 為每個節點創建新的`Node`對象（因為`newht.Insert`會創建新節點）。//for (size_t i = 0; i < _tables.size(); i++)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables);/*特點遞歸插入：遍歷舊表的每個節點，調用 newht.Insert 將數據插入新表。這會觸發完整的插入邏輯（計算哈希、處理沖突）。內存開銷：每個節點會重新創建新的 Node 對象，舊節點隨后被釋放（舊表析構時）。潛在問題：重復計算哈希：每次插入都要重新計算哈希值。內存分配頻繁：為每個節點分配新內存，效率較低。*/// 擴容vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);//表示創建一個大小為 __stl_next_prime(_tables.size() + 1) 的數組，// 每個桶初始化為空指針。// 遍歷舊表，將舊表的數據全部重新映射到新表//復用舊節點，僅調整指針，不創建新節點。for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// cur頭插到新表size_t hashi = hs(cur->_kv.first) % newtables.size();cur->_next = newtables[hashi];// 將當前節點的 next 指向新表的當前桶頭節點newtables[hashi] = cur;// 更新新表的當前桶頭節點為當前節點cur = next;}_tables[i] = nullptr;//遍歷舊表的每個桶后，將舊表的桶指針設為`nullptr`。//這是因為節點已經被轉移到新表中，舊表不再擁有這些節點的所有權，// 避免重復釋放或訪問已轉移的節點}_tables.swap(newtables);}/*特點節點復用：直接復用舊表的 Node 節點，僅調整指針指向，不創建新對象。高效內存管理：無需分配新內存，避免頻繁的 new / delete 操作。哈希計算優化：每個節點只需計算一次哈希值（舊表節點直接插入新表對應桶）*/。//方法二直接復用舊節點，通過指針調整高效轉移，避免了重復內存分配，//因此效率顯著優于方法一。//方法一由于創建新節點和額外的插入操作，效率較低，尤其在數據量大時更為明顯。//其實二者顯著的差別就是，第一種是得創建新節點，因為它只傳遞了桶節點中的值//第二種是可以直接將那個桶節點直接搬運到新的哈希表中的，這個是不需要創建新節點的size_t hashi = hs(kv.first) % _tables.size();// 頭插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];// 將當前節點的 next 指向新表的當前桶頭節點_tables[hashi] = newnode;// 更新新表的當前桶頭節點為當前節點//這種插入方法既適用于桶中有節點的，也適用于桶中沒有節點的，即當前節點是最新節點//如果新表的桶 `hashi` 已經有節點A，那么插入節點B后，B的 `_next` 指向A，// 新表的頭節點變為B，形成 `B->A` 的結構。++_n;return true;
}

??2.5.4.2.3?查找：

Node* Find(const K& key)
{Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;
}

查找沒什么好說的，就是找到了就返回，沒找到就繼續尋找。

???2.5.4.2.4?刪除：

bool Erase(const K& key)
{Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}--_n;delete cur;return true;}prev = cur;cur = cur->_next;}return false;
}

刪除分為刪除桶中的第一個元素以及刪除中間的元素。中間的if(prev==nullptr)，就是為了刪除桶中的第一個元素而準備的。其實跟鏈表的刪除差不了多少。

????2.5.4.2.4 析構：

~HashTable()
{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}
}

析構函數的話，類似于鏈表的析構，遍歷析構，最后別忘了將桶置為空。因為桶中的元素都沒有了，那么這個桶就沒有存在的必要了。?

?2.5.4.2.5? 代碼總結：

namespace hash_bucket
{//而鏈地址法的每個桶是一個鏈表，因此_tables的每個元素是一個指向鏈表頭節點的指針，所以是vector<Node*> _tables;// 即vector里存的是每個元素，又因為每個元素是指針，所以存的是Node*// 在下一個類中，進行了typedef HashNode<K, V> Node;// 所以說，表中的每個元素也是可以使用HashNode的成員變量的。//鏈表節點（Node）包含實際的鍵值對和指向下一個節點的指針。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){}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(size_t n = __stl_next_prime(0)):_tables(n, nullptr)//創建一個大小為n的數組，每個桶初始化為空指針//這個是整個大的外殼是_table，是要初始化為n個元素，每個桶初始化為空指針//而上面寫的HashNode的初始化是針對于每個元素的初始化，可以看成是外殼里面的小部分, _n(0){}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;Hash hs;// 負載因子到1擴容，if (_n == _tables.size()){//HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1));遍歷舊表，將舊表的數據全部重新映射到新表// 為每個節點創建新的`Node`對象（因為`newht.Insert`會創建新節點）。//for (size_t i = 0; i < _tables.size(); i++)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables);/*特點遞歸插入：遍歷舊表的每個節點，調用 newht.Insert 將數據插入新表。這會觸發完整的插入邏輯（計算哈希、處理沖突）。內存開銷：每個節點會重新創建新的 Node 對象，舊節點隨后被釋放（舊表析構時）。潛在問題：重復計算哈希：每次插入都要重新計算哈希值。內存分配頻繁：為每個節點分配新內存，效率較低。*/// 擴容vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);//表示創建一個大小為 __stl_next_prime(_tables.size() + 1) 的數組，// 每個桶初始化為空指針。// 遍歷舊表，將舊表的數據全部重新映射到新表//復用舊節點，僅調整指針，不創建新節點。for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// cur頭插到新表size_t hashi = hs(cur->_kv.first) % newtables.size();cur->_next = newtables[hashi];// 將當前節點的 next 指向新表的當前桶頭節點newtables[hashi] = cur;// 更新新表的當前桶頭節點為當前節點cur = next;}_tables[i] = nullptr;//遍歷舊表的每個桶后，將舊表的桶指針設為`nullptr`。//這是因為節點已經被轉移到新表中，舊表不再擁有這些節點的所有權，// 避免重復釋放或訪問已轉移的節點}_tables.swap(newtables);}/*特點節點復用：直接復用舊表的 Node 節點，僅調整指針指向，不創建新對象。高效內存管理：無需分配新內存，避免頻繁的 new / delete 操作。哈希計算優化：每個節點只需計算一次哈希值（舊表節點直接插入新表對應桶）*/。//方法二直接復用舊節點，通過指針調整高效轉移，避免了重復內存分配，//因此效率顯著優于方法一。//方法一由于創建新節點和額外的插入操作，效率較低，尤其在數據量大時更為明顯。//其實二者顯著的差別就是，第一種是得創建新節點，因為它只傳遞了桶節點中的值//第二種是可以直接將那個桶節點直接搬運到新的哈希表中的，這個是不需要創建新節點的size_t hashi = hs(kv.first) % _tables.size();// 頭插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];// 將當前節點的 next 指向新表的當前桶頭節點_tables[hashi] = newnode;// 更新新表的當前桶頭節點為當前節點//這種插入方法既適用于桶中有節點的，也適用于桶中沒有節點的，即當前節點是最新節點//如果新表的桶 `hashi` 已經有節點A，那么插入節點B后，B的 `_next` 指向A，// 新表的頭節點變為B，形成 `B->A` 的結構。++_n;return true;}Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}--_n;delete cur;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;//每個元素是一個鏈表的頭指針，表示哈希桶中的一個桶size_t _n;				// 實際存儲有效數據個數};

?OK，今天的文章到底結束。

...............