一、哈希常識(shí)

1.1、哈希概念

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

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

1.2、哈希沖突

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

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

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

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

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

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

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

常見哈希函數(shù)

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

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

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

• 設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于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ù)，就不能用直接定址法，因?yàn)榉植继珡V，會(huì)導(dǎo)致空間浪費(fèi)過多。這就需要用到除留余數(shù)法來解決：

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

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

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

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

4、折疊法–(了解)

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

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

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

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

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

假設(shè)要存儲(chǔ)某家公司員工登記表，如果用手機(jī)號(hào)作為關(guān)鍵字，那么極有可能前7位都是 相同的，那么我們可以選擇后面的四位作為散列地址，如果這樣的抽取工作還容易出現(xiàn) 沖突，還可以對(duì)抽取出來的數(shù)字進(jìn)行反轉(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è)計(jì)的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無法避免哈希沖突。

1.4、哈希沖突解決

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

閉散列（線性探測(cè) + 二次探測(cè)）

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

1、線性探測(cè)

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

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

線性探測(cè)優(yōu)點(diǎn)：實(shí)現(xiàn)非常簡(jiǎn)單，

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

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

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

2、二次探測(cè)

線性探測(cè)的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個(gè)空位置有關(guān)系，因?yàn)檎铱瘴恢玫姆绞骄褪前ぶ笾饌€(gè)去找，因此二次探測(cè)為了避免該問題，找下一個(gè)空位置的方法為：hash(key) + i^2（i = 0 1 2 3……）。以下圖示例：

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

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

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

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

開散列

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

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

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

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

2.1、框架

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

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

接下來依次展開說明。

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

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

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

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

enum State
{EMPTY,EXIST,DELETE
};
//哈希節(jié)點(diǎn)狀態(tài)的類
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//記錄每個(gè)位置的狀態(tài)，默認(rèn)給空
};
//哈希表的類
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)功能的實(shí)現(xiàn)……
private:vector<Data> _tables;size_t _n = 0;//記錄存放的有效數(shù)據(jù)的個(gè)數(shù)
};

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

1、查找50：

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

2、查找60：

• 60%10=0，下標(biāo)0不是，往后++下標(biāo)繼續(xù)查找，找到下標(biāo)4發(fā)現(xiàn)狀態(tài)為EMPTY空，此時(shí)停止查詢，因?yàn)橥缶筒豢赡艹霈F(xiàn)了

3、刪除10，再查找50

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

2.3、哈希表的擴(kuò)容

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

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

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為整型，為默認(rèn)仿函數(shù)的情況

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

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

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

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

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

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

為了能夠讓我們的哈希表能夠自動(dòng)識(shí)別傳入數(shù)據(jù)的類型，不用手動(dòng)聲明，這里我們可以借助特化來解決，仿函數(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碼值累計(jì)加起來}return hash;}
};

2.5、哈希表的插入

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

1. 去除冗余
2. 擴(kuò)容操作
3. 插入操作

下面分開來演示。

1、去除冗余：

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

2、擴(kuò)容操作：

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

3、插入操作：

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

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

2.6、哈希表的查找

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

1. 先去判斷表的大小是否為0，為0直接返回nullptr
2. 按照線性探測(cè) / 二次探測(cè)的方式去遍歷，遍歷的條件是此位置的狀態(tài)不為空EMPTY
3. 如果遍歷到某哈希表中的對(duì)象的值等于要查找的值（前提是此位置的狀態(tài)不為DELETE刪除），返回此對(duì)象的地址
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;//線性探測(cè)/二次探測(cè)while (_tables[hashi]._state != EMPTY)//不為空就繼續(xù){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];//找到了就返回此對(duì)象的地址}hashi = starti + i;//二次探測(cè)改為 +i^2++i;hashi %= _tables.size();//防止hashi超出數(shù)組}return nullptr;
}

2.7、哈希表的刪除

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

1. 復(fù)用Find函數(shù)去幫我們查找刪除的位置是否存在
2. 若存在，把此位置的狀態(tài)置為DELETE即可，此時(shí)表中的有效數(shù)據(jù)個(gè)數(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閉散列模擬實(shí)現(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碼值累計(jì)加起來}return hash;}
};//閉散列哈希表的模擬實(shí)現(xiàn)
enum State
{EMPTY,EXIST,DELETE
};
//哈希節(jié)點(diǎn)狀態(tài)的類
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//記錄每個(gè)位置的狀態(tài)，默認(rèn)給空
};//哈希表的類
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、擴(kuò)容//負(fù)載因子超過0.7，就擴(kuò)容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//擴(kuò)容以后，需要重新建立映射關(guān)系HashTable<K, V, HashFunc> newHT;newHT._tables.resize(newSize);//遍歷舊表，把舊表每個(gè)存在的元素插入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);//取出鍵值對(duì)的key，并且避免了負(fù)數(shù)的情況，借用仿函數(shù)確保是整型數(shù)據(jù)starti %= _tables.size();size_t hashi = starti;size_t i = 1;//線性探測(cè)/二次探測(cè)while (_tables[hashi]._state == EXIST){hashi = starti + i;//二次探測(cè)改為 +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;//線性探測(cè)/二次探測(cè)while (_tables[hashi]._state != EMPTY)//不為空就繼續(xù){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];//找到了就返回此對(duì)象的地址}hashi = starti + i;//二次探測(cè)改為 +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ù)的個(gè)數(shù)
};

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

3.1、框架

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

  //結(jié)點(diǎn)類
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)功能的實(shí)現(xiàn)……
private://指針數(shù)組vector<Node*> _tables;size_t _n = 0;//記錄有效數(shù)據(jù)的個(gè)數(shù)
};

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

此步操作的方法和閉散列哈希表所實(shí)現(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碼值累計(jì)加起來}return hash;}
};

3.3、哈希桶的插入

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

1. 去除冗余
2. 擴(kuò)容操作
3. 頭插操作

下面開始具體展開說明：

1、去除冗余：

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

2、擴(kuò)容操作：

針對(duì)哈希桶的擴(kuò)容，我們有兩種方法進(jìn)行擴(kuò)容，法一和哈希表擴(kuò)容的方法一致

法一：

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

此擴(kuò)容的方法會(huì)存在一個(gè)問題：釋放舊表會(huì)出錯(cuò)！！！

• 當(dāng)我們把舊表的元素映射插入到新表的時(shí)候，最后都要釋放舊表，按照先前哈希表的釋放，我們無需做任何處理，但是現(xiàn)在定義的結(jié)構(gòu)是vector，是自定義類型，會(huì)自動(dòng)調(diào)用析構(gòu)函數(shù)進(jìn)行釋放，vector存儲(chǔ)的數(shù)據(jù)是Node*，Node*是內(nèi)置類型，不會(huì)自動(dòng)釋放，最后會(huì)出現(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;//釋放后置空}
}

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

法二：

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

3、頭插操作：

1. 借助仿函數(shù)找到映射的位置（頭插的位置）
2. 進(jìn)行頭插的操作
3. 更新有效數(shù)據(jù)個(gè)數(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、負(fù)載因子 == 1就擴(kuò)容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;//確認(rèn)映射到新表的位置//頭插cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}newTable.swap(_tables);}//3、頭插//找到對(duì)應(yīng)的映射位置size_t hashi = hf(kv.first);hashi %= _tables.size();//頭插到對(duì)應(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. 在此位置往后的一串鏈表中進(jìn)行遍歷查找，找到了，返回節(jié)點(diǎn)指針
4. 遍歷結(jié)束，說明沒找到，返回nullptr

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

3.5、哈希桶的刪除

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

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

//刪除
bool Erase(const K& key)
{//防止后續(xù)除0錯(cuò)誤if (_tables.size() == 0){return false;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到key所對(duì)應(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;
}

法二：替換法刪除

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

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

這里就不代碼演示了，因?yàn)檎w的成本看還是法一更方便理解些。

3.6開散列模擬實(shí)現(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碼值累計(jì)加起來}return hash;}
};//開散列哈希桶的實(shí)現(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、負(fù)載因子 == 1就擴(kuò)容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;//確認(rèn)映射到新表的位置//頭插cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}newTable.swap(_tables);}//3、頭插//找到對(duì)應(yīng)的映射位置size_t hashi = hf(kv.first);hashi %= _tables.size();//頭插到對(duì)應(yīng)的桶即可Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}//查找Node* Find(const K& key){//防止后續(xù)除0錯(cuò)誤if (_tables.size() == 0){return nullptr;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到對(duì)應(yīng)的映射下標(biāo)位置size_t hashi = hf(key);//size_t hashi = HashFunc()(key);//匿名對(duì)象hashi %= _tables.size();Node* cur = _tables[hashi];//在此位置的鏈表中進(jìn)行遍歷查找while (cur){if (cur->_kv.first == key){//找到了return cur;}cur = cur->_next;}//遍歷結(jié)束，沒有找到，返回nullptrreturn nullptr;}//刪除/*法一*/bool Erase(const K& key){//防止后續(xù)除0錯(cuò)誤if (_tables.size() == 0){return false;}//構(gòu)建仿函數(shù)，把數(shù)據(jù)類型轉(zhuǎn)為整型，便于后續(xù)建立映射關(guān)系HashFunc hf;//找到key所對(duì)應(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ù)的個(gè)數(shù)
};
}

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