一、哈希常識

1.1、哈希概念

• 在順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個元素時，必須要經(jīng)過關(guān)鍵碼的多次比較。順序查找時間復(fù)雜度為O(N)，平衡樹中為樹的高度，即O(logN)，搜索的效率決于搜索過程中元素的比較次數(shù)。
• 理想的搜索方法：可以不經(jīng)過任何比較，一次直接從表中得到要搜索的元素。 如果構(gòu)造一種存儲結(jié)構(gòu)，通過某種函數(shù)(hashFunc)使元素的存儲位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時通過該函數(shù)可以很快找到該元素。
• 當(dāng)進行如下操作時：
  • 插入元素：根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計算出該元素的存儲位置并按此位置進行存放
  • 搜索元素：對元素的關(guān)鍵碼進行同樣的計算，把求得的函數(shù)值當(dāng)做元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功

該方式即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表(Hash Table)(或者稱散列表)

• 例如：數(shù)據(jù)集合{1，7，6，4，5，9}；哈希函數(shù)設(shè)置為：hash(key) = key % capacity（除留余數(shù)法）; capacity為存儲元素底層空間總的大小。圖示如下：

用該方法進行搜索不必進行多次關(guān)鍵碼的比較，因此搜索的速度比較快 問題：按照上述哈希方式，向集合中插入元素44，會出現(xiàn)什么問題？這就涉及到了哈希沖突

1.2、哈希沖突

對于兩個數(shù)據(jù)元素的關(guān)鍵字 和 (i != j)，有 != ，但也有：Hash(i) == Hash(j)，即：不同關(guān)鍵字通過相同哈希函數(shù)計算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或哈希碰撞。把具有不同關(guān)鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱為“同義詞”。

當(dāng)我們按照上述操作直接建立映射關(guān)系，還會出現(xiàn)如下幾個問題：

1. 數(shù)據(jù)范圍很廣，不集中，導(dǎo)致空間消耗太多怎么辦？
2. key的數(shù)據(jù)不是整數(shù)

發(fā)生哈希沖突該如何處理呢？這里我們首先使用哈希函數(shù)解決數(shù)據(jù)范圍廣，不集中，key的數(shù)據(jù)不是整數(shù)的問題，再來解決哈希沖突。

1.3、哈希函數(shù)（直接定執(zhí) + 除留余數(shù)）

引起哈希沖突的一個原因可能是：哈希函數(shù)設(shè)計不夠合理。 哈希函數(shù)設(shè)計原則：

• 哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間
• 哈希函數(shù)計算出來的地址能均勻分布在整個空間中
• 哈希函數(shù)應(yīng)該比較簡單

常見哈希函數(shù)

1、直接定址法–(常用)

• 取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash（Key）= A*Key + B 優(yōu)點：簡單、均勻 缺點：需要事先知道關(guān)鍵字的分布情況 使用場景：適合查找比較小且連續(xù)的情況 面試題：字符串中第一個只出現(xiàn)一次字符

2、除留余數(shù)法–(常用)

• 設(shè)散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(key) = key% p(p<=m),將關(guān)鍵碼轉(zhuǎn)換成哈希地址

比如我給出的數(shù)據(jù)集合為{5，8，100，9999，20，-10}，如此不集中分布廣的數(shù)據(jù)，就不能用直接定址法，因為分布太廣，會導(dǎo)致空間浪費過多。這就需要用到除留余數(shù)法來解決：

除留余數(shù)法就是先統(tǒng)一將數(shù)字轉(zhuǎn)換為無符號，解決了負數(shù)的問題，再用key%表的大小，隨后映射到哈希表中，圖示：

此時如果插入數(shù)字35的話，那么哈希沖突就會出現(xiàn)了，根據(jù)除留余數(shù)法的規(guī)則，35理應(yīng)映射到下標5的位置，可是該位置已經(jīng)有數(shù)值了，這就需要通過后文的開散列和閉散列的相關(guān)知識點來幫助我們解決哈希沖突。

3、平方取中法–(了解)

• 假設(shè)關(guān)鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希地址； 再比如關(guān)鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希地址 平方取中法比較適合：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況

4、折疊法–(了解)

• 折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分(最后一部分位數(shù)可以短些)，然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。折疊法適合事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)比較多的情況

5、隨機數(shù)法–(了解)

• 選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址，即H(key) = random(key),其中random為隨機數(shù)函數(shù)。通常應(yīng)用于關(guān)鍵字長度不等時采用此法

6、數(shù)學(xué)分析法–(了解)

• 設(shè)有n個d位數(shù)，每一位可能有r種不同的符號，這r種不同的符號在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號出現(xiàn)的機會均等，在某些位上分布不均勻只有某幾種符號經(jīng)常出現(xiàn)?？筛鶕?jù)散列表的大小，選擇其中各種符號分布均勻的若干位作為散列地址。例如：

假設(shè)要存儲某家公司員工登記表，如果用手機號作為關(guān)鍵字，那么極有可能前7位都是 相同的，那么我們可以選擇后面的四位作為散列地址，如果這樣的抽取工作還容易出現(xiàn) 沖突，還可以對抽取出來的數(shù)字進行反轉(zhuǎn)(如1234改成4321)、右環(huán)位移(如1234改成4123)、左環(huán)移位、前兩數(shù)與后兩數(shù)疊加(如1234改成12+34=46)等方法。

數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻的情況

**注意：**哈希函數(shù)設(shè)計的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無法避免哈希沖突。

1.4、哈希沖突解決

解決哈希沖突的兩種方法是：閉散列和開散列

閉散列（線性探測 + 二次探測）

閉散列：也叫開放定址法，當(dāng)發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個” 空位置中去。那如何尋找下一個空位置呢？

1、線性探測

線性探測：從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。找下一個空位置的方法為：hash(key)%N + i。拿上圖繼續(xù)演示：

比如我在此基礎(chǔ)上繼續(xù)插入10，30，50。首先，10%10=0，下標0的位置有了20，繼續(xù)往后找，下標1是空的，把10放進去；20%10=0，下標0為20，往后找，下標1是10，往后找，下標2是空的，放進去……。

線性探測優(yōu)點：實現(xiàn)非常簡單，

線性探測缺點：一旦發(fā)生哈希沖突，所有的沖突連在一起，容易產(chǎn)生數(shù)據(jù)“堆積”，即：不同關(guān)鍵碼占據(jù)了可利用的空位置，使得尋找某關(guān)鍵碼的位置需要許多次比較，導(dǎo)致搜索效率降低。

• 當(dāng)再插入數(shù)值21時，21%10=1，可是下標1位置被下標0位置的沖突而被10占了，于是繼續(xù)往后找空位，惡行循環(huán)，導(dǎo)致?lián)矶隆?/li>

為了解決此麻煩，又推出了二次探測。

2、二次探測

線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個空位置有關(guān)系，因為找空位置的方式就是挨著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為：hash(key) + i^2（i = 0 1 2 3……）。以下圖示例：

同樣是插入10，30，50。10%10+0^2 = 0，下標0有值就加1^2 = 1，下標1為空放進去，20%10+2 ^ 2 = 4，下標4為空放進去，50%10+3 ^ 2 = 9，不為空，換成+4 ^ 2 =16，超過數(shù)組的長度，繞回來，數(shù)到16，為下標7為空放進去。

二次探測就是對上述線性探測的優(yōu)化，不那么擁堵。簡而言之，線性探測是依次尋找空位置，必然擁堵，而二次探測跳躍著尋找空位置，就沒那么擁堵。不過這倆方法沒有本質(zhì)的沖突，本質(zhì)都是在占別人的位置，只是一個挨著占，一個分散著占的區(qū)別罷了。

• 研究表明：當(dāng)表的長度為質(zhì)數(shù)且表裝載因子a不超過0.5時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時可以不考慮表裝滿的情況，但在插入時必須確保表的裝載因子a不超過0.5，如果超出必須考慮增容。

因此：閉散列最大的缺陷就是空間利用率比較低，這也是閉散列的缺陷，但是往后又推出一種開散列來解決哈希沖突的問題，此法還是比較優(yōu)的。

開散列

開散列法又叫鏈地址法(開鏈法、哈希桶)，首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結(jié)點存儲在哈希表中

• 簡而言之就是我的數(shù)據(jù)不存在表中，表里面存儲一個鏈表指針，就是把沖突的數(shù)據(jù)通過鏈表的形式掛起來，示例：

從上圖可以看出，開散列中每個桶中放的都是發(fā)生哈希沖突的元素，大大減少了閉散列法沖突的弊端性。后文將會詳細講解閉散列哈希表以及開散列哈希桶的具體模擬實現(xiàn)。

二、閉散列哈希表的模擬實現(xiàn)

2.1、框架

在模擬實現(xiàn)之前，要清楚實現(xiàn)哈希表所需的必要成分：

• 哈希節(jié)點狀態(tài)的類
• 哈希表的類

接下來依次展開說明。

2.2、哈希節(jié)點狀態(tài)的類

我們都很清楚數(shù)組里的每一個值無非三種狀態(tài)：

1. 如果某下標沒有值，則代表空EMPTY
2. 如果有值在代表存在EXIST
3. 如果此位置的值被刪掉了，則表示為DELETE

而這三種狀態(tài)我們可以借助enum枚舉來幫助我們表示數(shù)組里每個位置的狀態(tài)。這里我們專門封裝一個類來記錄每個位置的狀態(tài)，以此匯報給后續(xù)的哈希表。

enum State
{EMPTY,EXIST,DELETE
};
//哈希節(jié)點狀態(tài)的類
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//記錄每個位置的狀態(tài)，默認給空
};
//哈希表的類
template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函數(shù)便于把其他類型的數(shù)據(jù)轉(zhuǎn)換為整型數(shù)據(jù)
class HashTable
{typedef HashData<K, V> Data;
public://相關(guān)功能的實現(xiàn)……
private:vector<Data> _tables;size_t _n = 0;//記錄存放的有效數(shù)據(jù)的個數(shù)
};

實現(xiàn)好了哈希節(jié)點的類，就能夠很好的幫助我們后續(xù)的查找，示例：

1、查找50：

• 50%10=0，下標0的值不是50，繼續(xù)++下標往后查找，直至下標3的下標為止。

2、查找60：

• 60%10=0，下標0不是，往后++下標繼續(xù)查找，找到下標4發(fā)現(xiàn)狀態(tài)為EMPTY空，此時停止查詢，因為往后就不可能出現(xiàn)了

3、刪除10，再查找50

• 50%10=0，下標0的值不是，++下標到下標1，發(fā)現(xiàn)狀態(tài)為DELETE刪除，繼續(xù)++下標直至下標3的值為50，找到了。

2.3、哈希表的擴容

• 散列表的載荷因子定義為：α = 填入表中的元素個數(shù) / 散列表的長度
• α是散列表裝滿程度的標志因子。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以α越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大；反之，α越小，表明填入表中的元素越少，產(chǎn)生沖突的可能性就越小。實際上，散列表的平均查找長度是載荷因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。
• 對于開放定址法（閉散列），載荷因子是特別重要因素，應(yīng)嚴格限制在0.7 ~ 0.8以下。超過0.8，查表時的CPU緩存不命中（cache missing）按照質(zhì)數(shù)曲線上升。因此，一些采用開放定址法的hash庫，如Java的系統(tǒng)庫限制了載荷因子為0.75，超過此值將resize散列表。

綜上，我們在后續(xù)的插入操作中，必然要考慮到擴容的情況，我們直接把負載因子控制在0.7，超過了就擴容。具體操作見下文哈希表的插入操作。

2.4、構(gòu)建仿函數(shù)把所有數(shù)據(jù)類型轉(zhuǎn)換為整型并特化

在我們后續(xù)的插入操作中，插入的數(shù)據(jù)類型如果是整數(shù)，那么可以直接建立映射關(guān)系，可若是字符串，就沒那么容易了，因此，我們需要套一層仿函數(shù)，來幫助我們把字符串類型轉(zhuǎn)換成整型的數(shù)據(jù)再建立映射關(guān)系。主要分為以下三類需要寫仿函數(shù)的情況：

1、key為整型，為默認仿函數(shù)的情況

• 此時的數(shù)據(jù)類型為整型，直接強轉(zhuǎn)size_t隨后返回

2、key為字符串，單獨寫個字符串轉(zhuǎn)整型的仿函數(shù)

針對于字符串轉(zhuǎn)整型，我們推出下面兩種方法，不過都是會存在問題的：

1. 只用首字母的ascii碼來映射，此法不合理，因為"abc"和"axy"本是倆不用字符串，經(jīng)過轉(zhuǎn)換，會引發(fā)沖突。
2. 字符串內(nèi)所有字符ASCII碼值之和，此法也會產(chǎn)生沖突，因為"abcd"和"bcad"在此情況就會沖突。

為了避免沖突，幾位大佬推出多種算法思想，下面我取其中一種算法思想來講解：

BKDR哈希算法：
hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..  

為了能夠讓我們的哈希表能夠自動識別傳入數(shù)據(jù)的類型，不用手動聲明，這里我們可以借助特化來解決，仿函數(shù)+特化總代碼如下：

//利用仿函數(shù)將數(shù)據(jù)類型轉(zhuǎn)換為整型
template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii碼值累計加起來}return hash;}
};

2.5、哈希表的插入

哈希表的插入主要是三大步驟：

1. 去除冗余
2. 擴容操作
3. 插入操作

下面分開來演示。

1、去除冗余：

1. 復(fù)用Find查找函數(shù)，去幫助我們查找插入的值是否存在
2. 若存在，直接返回false
3. 不存在，再進行后續(xù)的插入操作

2、擴容操作：

1. 如果哈希表一開始就為空，則要擴容
2. 如果填入表中的元素個數(shù)*10 再 / 表的大小>=7，就擴容（*10是為了避免出現(xiàn)size_t的類型相除不會有小數(shù)的情況）
3. 擴容以后要重新建立映射關(guān)系
4. 創(chuàng)建一個新的哈希對象，擴容到需要的內(nèi)存大小
5. 遍歷舊表，把舊表每個存在的元素依據(jù)該哈希表的規(guī)則（如：除留余數(shù)法）插入到新表，此步驟讓新表自動完成映射關(guān)系，無序手動構(gòu)建
6. 利用swap函數(shù)把新表和舊表中的數(shù)據(jù)進行交換，此時的舊表就是已經(jīng)擴好容且建立好映射關(guān)系的哈希表

3、插入操作：

1. 借助仿函數(shù)把插入的數(shù)據(jù)類型轉(zhuǎn)為整型并定義變量保存插入鍵值對的key
2. 用此變量%=哈希表的size()，因為我們初始化的時候已經(jīng)將哈希表的值全部賦零值了，且對于哈希表，應(yīng)該盡量控制size和capacity一樣大
3. 遍歷進行線性探測 / 二次探測，如果這個位置的狀態(tài)為EXIST存在，說明還要往后遍歷查找
4. 遍歷結(jié)束，說明此位置的狀態(tài)為空EMPTY或刪除DELETE，可以放值
5. 把插入的值放進該位置，更新狀態(tài)為EXIST，有效數(shù)據(jù)個數(shù)++

//插入
bool Insert(const pair<K, V>& kv)
{//1、去除冗余if (Find(kv.first)){//說明此值已經(jīng)有了，直接返回falsereturn false;}//2、擴容//負載因子超過0.7，就擴容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//擴容以后，需要重新建立映射關(guān)系HashTable<K, V, HashFunc> newHT;newHT._tables.resize(newSize);//遍歷舊表，把舊表每個存在的元素插入newHTfor (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射關(guān)系后交換}//3、插入HashFunc hf;size_t starti = hf(kv.first);//取出鍵值對的key，并且避免了負數(shù)的情況，借用仿函數(shù)確保是整型數(shù)據(jù)starti %= _tables.size();size_t hashi = starti;size_t i = 1;//線性探測/二次探測while (_tables[hashi]._state == EXIST){hashi = starti + i;//二次探測改為 +i^2++i;hashi %= _tables.size();//防止hashi超出數(shù)組}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;
}

2.6、哈希表的查找

查找的核心邏輯就是找到key相同，就返回此對象的地址，找到空就返回nullptr，具體細分規(guī)則如下：

1. 先去判斷表的大小是否為0，為0直接返回nullptr
2. 按照線性探測 / 二次探測的方式去遍歷，遍歷的條件是此位置的狀態(tài)不為空EMPTY
3. 如果遍歷到某哈希表中的對象的值等于要查找的值（前提是此位置的狀態(tài)不為DELETE刪除），返回此對象的地址
4. 當(dāng)遍歷結(jié)束后，說明此位置的狀態(tài)為空EMPTY，哈希表沒有我們要查找的值，返回nullptr

//查找
Data* Find(const K& key)
{//判斷表的size是否為0if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t starti = hf(key);//通過仿函數(shù)把其它類型數(shù)據(jù)轉(zhuǎn)為整型數(shù)據(jù)starti %= _tables.size();size_t hashi = starti;size_t i = 1;//線性探測/二次探測while (_tables[hashi]._state != EMPTY)//不為空就繼續(xù){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];//找到了就返回此對象的地址}hashi = starti + i;//二次探測改為 +i^2++i;hashi %= _tables.size();//防止hashi超出數(shù)組}return nullptr;
}

2.7、哈希表的刪除

刪除的邏輯很簡單，遵循下面的規(guī)則：

1. 復(fù)用Find函數(shù)去幫我們查找刪除的位置是否存在
2. 若存在，把此位置的狀態(tài)置為DELETE即可，此時表中的有效數(shù)據(jù)個數(shù)_n需要減減，最后返回true
3. 若不存在，直接返回false

//刪除
bool Erase(const K& key)
{//復(fù)用Find函數(shù)去幫助我們查找刪除的值是否存在Data* ret = Find(key);if (ret){//若存在，直接把此位置的狀態(tài)置為DELETE即可ret->_state = DELETE;return true;}else{return false;}
}

2.8閉散列模擬實現(xiàn)代碼：

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;//利用仿函數(shù)將數(shù)據(jù)類型轉(zhuǎn)換為整型
template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii碼值累計加起來}return hash;}
};//閉散列哈希表的模擬實現(xiàn)
enum State
{EMPTY,EXIST,DELETE
};
//哈希節(jié)點狀態(tài)的類
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//記錄每個位置的狀態(tài)，默認給空
};//哈希表的類
template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函數(shù)便于把其他類型的數(shù)據(jù)轉(zhuǎn)換為整型數(shù)據(jù)
class HashTable
{
typedef HashData<K, V> Data;
public:
//插入
bool Insert(const pair<K, V>& kv)
{//1、去除冗余if (Find(kv.first)){//說明此值已經(jīng)有了，直接返回falsereturn false;}//2、擴容//負載因子超過0.7，就擴容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//擴容以后，需要重新建立映射關(guān)系HashTable<K, V, HashFunc> newHT;newHT._tables.resize(newSize);//遍歷舊表，把舊表每個存在的元素插入newHTfor (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射關(guān)系后交換}//3、插入HashFunc hf;size_t starti = hf(kv.first);//取出鍵值對的key，并且避免了負數(shù)的情況，借用仿函數(shù)確保是整型數(shù)據(jù)starti %= _tables.size();size_t hashi = starti;size_t i = 1;//線性探測/二次探測while (_tables[hashi]._state == EXIST){hashi = starti + i;//二次探測改為 +i^2++i;hashi %= _tables.size();//防止hashi超出數(shù)組}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;
}
//查找
Data* Find(const K& key)
{//判斷表的size是否為0if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t starti = hf(key);//通過仿函數(shù)把其它類型數(shù)據(jù)轉(zhuǎn)為整型數(shù)據(jù)starti %= _tables.size();size_t hashi = starti;size_t i = 1;//線性探測/二次探測while (_tables[hashi]._state != EMPTY)//不為空就繼續(xù){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];//找到了就返回此對象的地址}hashi = starti + i;//二次探測改為 +i^2++i;hashi %= _tables.size();//防止hashi超出數(shù)組}return nullptr;
}
//刪除
bool Erase(const K& key)
{//復(fù)用Find函數(shù)去幫助我們查找刪除的值是否存在Data* ret = Find(key);if (ret){//若存在，直接把此位置的狀態(tài)置為DELETE即可ret->_state = DELETE;return true;}else{return false;}
}
private:
vector<Data> _tables;
size_t _n = 0;//記錄存放的有效數(shù)據(jù)的個數(shù)
};

三、開散列哈希桶的模擬實現(xiàn)

3.1、框架

根據(jù)我們先前對開散列哈希桶的了解，得知其根本就是一個指針數(shù)組，數(shù)組里每一個位置都是一個鏈表指針，因此我們要單獨封裝一個鏈表結(jié)構(gòu)的類，以此來告知我們哈希表類的每個位置為鏈表指針結(jié)構(gòu)。

  //結(jié)點類
template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;//構(gòu)造函數(shù)HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};//哈希表的類
template<class K, class V, class HashFunc = DefaultHash<K>>
class HashTable
{typedef HashNode<K, V> Node;
public://相關(guān)功能的實現(xiàn)……
private://指針數(shù)組vector<Node*> _tables;size_t _n = 0;//記錄有效數(shù)據(jù)的個數(shù)
};

3.2、構(gòu)建仿函數(shù)把字符類型轉(zhuǎn)為整型并特化

此步操作的方法和閉散列哈希表所實現(xiàn)的步驟一致，目的都是為了能夠讓后續(xù)操作中傳入的所有數(shù)據(jù)類型轉(zhuǎn)換為整型數(shù)據(jù)，以此方便后續(xù)建立映射關(guān)系，直接看代碼：

//利用仿函數(shù)將數(shù)據(jù)類型轉(zhuǎn)換為整型
template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii碼值累計加起來}return hash;}
};

3.3、哈希桶的插入

哈希桶的插入主要分為這幾大步驟

1. 去除冗余
2. 擴容操作
3. 頭插操作

下面開始具體展開說明：

1、去除冗余：

1. 復(fù)用Find查找函數(shù)，去幫助我們查找插入的值是否存在
2. 若存在，直接返回false
3. 不存在，再進行后續(xù)的插入操作

2、擴容操作：

針對哈希桶的擴容，我們有兩種方法進行擴容，法一和哈希表擴容的方法一致

法一：

1. 當(dāng)負載因子==1時擴容
2. 擴容后重新建立映射關(guān)系
3. 創(chuàng)建一個新的哈希桶對象，擴容到newSize的大小
4. 遍歷舊表，把舊表每個存在的元素插入到新表，此步驟讓新表自動完成映射關(guān)系，無序手動構(gòu)建
5. 利用swap函數(shù)把新表和舊表交換，此時的舊表就是已經(jīng)擴好容且建立號映射關(guān)系的哈希表

此擴容的方法會存在一個問題：釋放舊表會出錯！！！

• 當(dāng)我們把舊表的元素映射插入到新表的時候，最后都要釋放舊表，按照先前哈希表的釋放，我們無需做任何處理，但是現(xiàn)在定義的結(jié)構(gòu)是vector，是自定義類型，會自動調(diào)用析構(gòu)函數(shù)進行釋放，vector存儲的數(shù)據(jù)是Node*，Node*是內(nèi)置類型，不會自動釋放，最后會出現(xiàn)表我們釋放了，但是鏈表結(jié)構(gòu)的數(shù)據(jù)還沒釋放，因此，我們還需借助手寫析構(gòu)函數(shù)來幫助我們釋放。

//析構(gòu)函數(shù)
~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;//釋放后置空}
}

此擴容的方法可以進行優(yōu)化，見法二。

法二：

• 這里我們沒必要再創(chuàng)建新的節(jié)點，相反把擴容前的節(jié)點拿過來重新映射到新表中，大體邏輯和前面差不太多，只是這里不需要再創(chuàng)建新節(jié)點。直接利用原鏈表里的節(jié)點。

3、頭插操作：

1. 借助仿函數(shù)找到映射的位置（頭插的位置）
2. 進行頭插的操作
3. 更新有效數(shù)據(jù)個數(shù)

//插入
bool Insert(const pair<K, V>& kv)
{//1、去除冗余if (Find(kv.first)){return false;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//2、負載因子 == 1就擴容if (_tables.size() == _n){/*法一size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newHT;//newHT._tables.resize(newSize, nullptr);//遍歷舊表，把舊表的數(shù)據(jù)重新映射到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur)//如果cur不為空，就插入{newHT.Insert(cur->_kv);cur = cur->_next;}}newHT._tables.swap(_tables);*///法二：size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newTable;newTable.resize(newSize, nullptr);for (size_t i = 0; i < _tables.size(); i++)//遍歷舊表{Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newSize;//確認映射到新表的位置//頭插cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}newTable.swap(_tables);}//3、頭插//找到對應(yīng)的映射位置size_t hashi = hf(kv.first);hashi %= _tables.size();//頭插到對應(yīng)的桶即可Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

3.4、哈希桶的查找

遵循下列規(guī)則：

1. 先去判斷表的大小是否為0，為0直接返回nullptr
2. 利用仿函數(shù)去找到映射的位置
3. 在此位置往后的一串鏈表中進行遍歷查找，找到了，返回節(jié)點指針
4. 遍歷結(jié)束，說明沒找到，返回nullptr

//查找
Node* Find(const K& key)
{//防止后續(xù)除0錯誤if (_tables.size() == 0){return nullptr;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到對應(yīng)的映射下標位置size_t hashi = hf(key);//size_t hashi = HashFunc()(key);//匿名對象hashi %= _tables.size();Node* cur = _tables[hashi];//在此位置的鏈表中進行遍歷查找while (cur){if (cur->_kv.first == key){//找到了return cur;}cur = cur->_next;}//遍歷結(jié)束，沒有找到，返回nullptrreturn nullptr;
}

3.5、哈希桶的刪除

哈希桶的刪除遵循這兩大思路：

1. 找到刪除的值對應(yīng)哈希桶的下標映射位置
2. 按照單鏈表刪除節(jié)點的方法對該值進行刪除

//刪除
bool Erase(const K& key)
{//防止后續(xù)除0錯誤if (_tables.size() == 0){return false;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到key所對應(yīng)的哈希桶的位置size_t hashi = hf(key);hashi %= _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;//刪除while (cur){if (cur->_kv.first == key){if (prev == nullptr)//頭刪{_tables[hashi] = cur->_next;}else//非頭刪{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;
}

法二：替換法刪除

• 上述的刪除是實打?qū)嵉膭h除，建立prev作為cur的前指針，以此利用prev和cur->next來建立關(guān)系從而刪除cur節(jié)點，但是我們可以不用借助prev指針，就利用先前二叉搜索樹的替換法刪除的思想來解決。圖示：

1. 當(dāng)我要刪除88時，把節(jié)點88的下一個節(jié)點的值78替換掉88，隨后刪除節(jié)點78，再建立鏈表的關(guān)系即可。
2. 當(dāng)刪除的是尾節(jié)點98時，直接和頭節(jié)點進行交換，刪除頭節(jié)點，并建立鏈表關(guān)系。

這里就不代碼演示了，因為整體的成本看還是法一更方便理解些。

3.6開散列模擬實現(xiàn)代碼：

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;//利用仿函數(shù)將數(shù)據(jù)類型轉(zhuǎn)換為整型
template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii碼值累計加起來}return hash;}
};//開散列哈希桶的實現(xiàn)
namespace Bucket
{
template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;//構(gòu)造函數(shù)HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};
template<class K, class V, class HashFunc = DefaultHash<K>>
class HashTable
{typedef HashNode<K, V> Node;
public://析構(gòu)函數(shù)~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){//1、去除冗余if (Find(kv.first)){return false;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//2、負載因子 == 1就擴容if (_tables.size() == _n){/*法一size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newHT;//newHT._tables.resize(newSize, nullptr);//遍歷舊表，把舊表的數(shù)據(jù)重新映射到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur)//如果cur不為空，就插入{newHT.Insert(cur->_kv);cur = cur->_next;}}newHT._tables.swap(_tables);*///法二：size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newTable;newTable.resize(newSize, nullptr);for (size_t i = 0; i < _tables.size(); i++)//遍歷舊表{Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newSize;//確認映射到新表的位置//頭插cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}newTable.swap(_tables);}//3、頭插//找到對應(yīng)的映射位置size_t hashi = hf(kv.first);hashi %= _tables.size();//頭插到對應(yīng)的桶即可Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}//查找Node* Find(const K& key){//防止后續(xù)除0錯誤if (_tables.size() == 0){return nullptr;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到對應(yīng)的映射下標位置size_t hashi = hf(key);//size_t hashi = HashFunc()(key);//匿名對象hashi %= _tables.size();Node* cur = _tables[hashi];//在此位置的鏈表中進行遍歷查找while (cur){if (cur->_kv.first == key){//找到了return cur;}cur = cur->_next;}//遍歷結(jié)束，沒有找到，返回nullptrreturn nullptr;}//刪除/*法一*/bool Erase(const K& key){//防止后續(xù)除0錯誤if (_tables.size() == 0){return false;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到key所對應(yīng)的哈希桶的位置size_t hashi = hf(key);hashi %= _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;//刪除while (cur){if (cur->_kv.first == key){if (prev == nullptr)//頭刪{_tables[hashi] = cur->_next;}else//非頭刪{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}/*法二替換法……*/private://指針數(shù)組vector<Node*> _tables;size_t _n = 0;//記錄有效數(shù)據(jù)的個數(shù)
};
}

分享就到這里了，有錯誤的地方還望指出，886！！！