柚子快報(bào)激活碼778899分享：c++ 通俗易懂-＞哈希表詳解
柚子快報(bào)激活碼778899分享：c++ 通俗易懂-＞哈希表詳解
目錄
一、什么是哈希表？
1.1哈希表長(zhǎng)什么樣？
1.2為什么會(huì)有哈希表？
1.3哈希表的特點(diǎn)
1.3.1 取余法、線性探測(cè)
1.3.2?映射
1.3.3負(fù)載因子
1.4哈希桶
1.5閑散列與開(kāi)散列
1.6總結(jié)
二、設(shè)計(jì)hash表
1、哈希表的設(shè)計(jì)
??1）插入
??2）查找
?3）刪除
4）字符串哈希算法
2、封裝map和set
1、完成對(duì)hash表的基礎(chǔ)功能
2、完成封裝
3、對(duì)應(yīng)的迭代器
4、【】方括號(hào)重載
三、設(shè)計(jì)原碼
1、HashTable
2、unordered_map
3、unordered_set
4、test
一、什么是哈希表？
什么是哈希表？
哈希表，顧名思義，就是一個(gè)表。
可是為什么叫哈希表？
因?yàn)檫@是從老美哪里音譯過(guò)來(lái)的
叫做->Hash Table
翻譯過(guò)來(lái)就是->哈希表
既然是表，那么
第一，這個(gè)哈希表長(zhǎng)什么樣子？
第二，為什么會(huì)有這個(gè)哈希表？
第三，這個(gè)哈希表用來(lái)做什么？
第三，這個(gè)哈希表的特點(diǎn)是什么？
第四，什么是取余法？
第五，什么是映射？
第六，什么是線性探測(cè)？
第七，什么是哈希桶？
一些常見(jiàn)的概念，是什么？要怎么理解？
下面一一我來(lái)解析。
1.1哈希表長(zhǎng)什么樣？
一般哈希表有兩種形式（先別問(wèn)為什么，先看，后面解釋）
1.2為什么會(huì)有哈希表？
假設(shè)你有一個(gè)數(shù)組或者鏈表，
傳統(tǒng)的數(shù)組訪問(wèn)某一個(gè)數(shù)據(jù)，或者鏈表訪問(wèn)某一個(gè)數(shù)據(jù)，必須遍歷，也只有遍歷。
假如你的數(shù)組長(zhǎng)度為100萬(wàn)，你現(xiàn)在要取某個(gè)值，而你知道這個(gè)值在就在數(shù)組的中間。
怎么辦？
此時(shí)，無(wú)論從前往后，還是從后往前遍歷，都繞不過(guò)50萬(wàn)個(gè)值。
蛋不蛋疼？蛋疼。
難受不難受？難受。
如果數(shù)據(jù)規(guī)模更大，例如100億，那更難受。
所以，有困難，有麻煩，就會(huì)引發(fā)思考：我能不能不用遍歷，咔的一下，馬上就找到這個(gè)值？
而傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)顯然無(wú)法突破這個(gè)難題。
既然舊的不行，干脆，那就搞一個(gè)新的。
于是，天空一聲巨響，哈希表閃亮登場(chǎng)！
所以，哈希表就是為了解決查找必須遍歷的問(wèn)題而生。
1.3哈希表的特點(diǎn)
如何做到不遍歷直接訪問(wèn)到數(shù)據(jù)？
很簡(jiǎn)單，非常簡(jiǎn)單，簡(jiǎn)單到不能再簡(jiǎn)單。
舉個(gè)例子，你有5個(gè)值：1， 2， 3， 4 ，10001
我在創(chuàng)建數(shù)組的時(shí)候，我直接申請(qǐng)10001個(gè)空間！
然后所有的數(shù)據(jù)直接存儲(chǔ)在對(duì)應(yīng)的下標(biāo)位置。
(啊？？？)
現(xiàn)在你給我一個(gè)值，例如說(shuō)10001。
要我去表里找，此時(shí)我不去遍歷。
我直接就到數(shù)組下標(biāo)為10001的位置取數(shù)據(jù)。
因?yàn)閿?shù)組是支持隨機(jī)訪問(wèn)的。
我直接初始位置+10001，直接就拿到數(shù)據(jù)了。
有毛病沒(méi)有？沒(méi)有。
有問(wèn)題沒(méi)有？沒(méi)有。
你會(huì)說(shuō)，是不是太浪費(fèi)空間了？
是的，非常浪費(fèi)。
但是，你就說(shuō)我遍歷了沒(méi)有？沒(méi)有。
你就說(shuō)找到了沒(méi)有？找到了。
你就說(shuō)快不快？非?？欤琌(1)。
所以，解決我們?cè)瓉?lái)要遍歷的困擾沒(méi)有？解決了。
但是，你會(huì)發(fā)現(xiàn)不對(duì)勁，空間太浪費(fèi)了啊。
假設(shè)我有只有2個(gè)數(shù)據(jù)，一個(gè)是1，另一個(gè)是1000000000000000。
(嗯......?!)
難道我要建立那么大的空間，就為了存這倆貨？
不行，很不行，非常不行。
那么，怎么辦？
于是，取余法就來(lái)了。
1.3.1 取余法、線性探測(cè)
現(xiàn)在，我們回到文章開(kāi)始的地方，哈希表的模樣，其中一種是這樣的：
為什么是這樣的？
下面我們來(lái)解釋：
假如，我們有以上數(shù)據(jù)：2，18，22，89，1000000000001
按照原來(lái)的辦法，我們需要開(kāi)辟10000000000001個(gè)空間，才能構(gòu)成哈希表
即數(shù)據(jù)存儲(chǔ)在對(duì)應(yīng)位置
但是，這種方式不行，太浪費(fèi)空間。
怎么辦？取余法。
什么是取余法？
很簡(jiǎn)單，就是取余數(shù)。
例如，我們現(xiàn)在有5個(gè)數(shù)據(jù)，那么我們就開(kāi)10個(gè)空間
然后，讓這每一個(gè)數(shù)據(jù)%10，得到結(jié)果
再將這個(gè)結(jié)果放到對(duì)應(yīng)的位置。
什么意思？
很簡(jiǎn)單，現(xiàn)在有6個(gè)數(shù)據(jù)：2，18，22，23，89，1000000000001
2%10 = 2，所以2存放在下標(biāo)為2的位置
18%10 = 8，所以2存放在下標(biāo)為8的位置
22%10 = 2，所以存放在下標(biāo)為2的位置
但是，現(xiàn)在下標(biāo)為2的位置已經(jīng)有了一個(gè)值
而這個(gè)，就是所謂的哈希沖突！非常簡(jiǎn)單，非常好理解對(duì)不對(duì)？
是的，就是這么簡(jiǎn)單。不要被一些看似很牛b的概念給困住了。
所有的概念都只不過(guò)是為了更好的概括和綜合某個(gè)現(xiàn)象，方便于你理解，僅此而已。
學(xué)習(xí)新事物，也是如此。
好的，那么，這個(gè)位置沖突了，怎么辦？
那就放到后面沒(méi)有沖突的位置。
下標(biāo)為3的位置沒(méi)有沖突，所以，放到3
23%10 = 3，所以23存放在下標(biāo)為3的位置
但是，同樣的，下標(biāo)為3的位置已經(jīng)有數(shù)據(jù)了。
即所謂哈希沖突了。
怎么辦？
很簡(jiǎn)單，同樣的道理，往后挪
挪到?jīng)]有沖突的位置。
所以，往后下標(biāo)4的位置沒(méi)有數(shù)據(jù)，所以23存在下標(biāo)為4的位置
89%10 = 9，所以89存放在下標(biāo)為9的位置
1000000000001%10 = 1，所以1000000000001存放在下標(biāo)為1的位置
于是，這6個(gè)數(shù)據(jù)，即使有數(shù)據(jù)為1000000000001那么大的值，
我們也僅僅用了10個(gè)空間就存儲(chǔ)下來(lái)了。
那么，如何取出數(shù)據(jù)呢？
同樣的，很簡(jiǎn)單，例如取18，將18%10=8，然后到下標(biāo)為8的位置取即可。
但是，22呢？22%10=2，但是22卻不在下標(biāo)為2的位置。
怎么辦呢？
往后找。
23呢？也不在下標(biāo)為3的位置。
怎么辦呢？
往后找。
如果當(dāng)前位置找不到值，就往后挨個(gè)查找，直到找到。
往后找，就像是探測(cè)，而且是一個(gè)一個(gè)探測(cè)，是線性的查找。
這就是所謂線性探測(cè)！
所以，我們把這個(gè)表，就叫做線性探測(cè)表
非常簡(jiǎn)單。
1.3.2?映射
同時(shí)，你會(huì)發(fā)現(xiàn)：
22并不是存在下標(biāo)為22的位置，而是存在下標(biāo)為2的位置
1000000001也不是存在下標(biāo)為1000000001的位置，而是存在下標(biāo)為1的位置
這就是所謂映射！
即，值與值之間的關(guān)聯(lián)，一種關(guān)系。
22和下標(biāo)為2的位置的映射關(guān)系。
1000000001和下標(biāo)為1的位置的映射關(guān)系。
還可以這么理解：
你名字叫做張三，你的發(fā)小叫做李四。
別人叫張三，叫的是你，而不是你發(fā)小。
這就是映射，張三映射你，李四映射你發(fā)小。
這就是一對(duì)一映射。
同時(shí)，還會(huì)有這一種情況：
你遇到了一個(gè)人，她名字也叫做張三！
現(xiàn)在，有人叫張三的名字，但是張三有兩個(gè)人。
所以，張三映射對(duì)應(yīng)兩個(gè)人。
甚至，張三有很多很多，例如說(shuō)張偉這個(gè)名字。
這就是一對(duì)多的映射。
1.3.3負(fù)載因子
取余法，解決數(shù)據(jù)存放空間太大的問(wèn)題
好了，現(xiàn)在我們已經(jīng)解決了空間太大的問(wèn)題。
但是，問(wèn)題又來(lái)了。
什么問(wèn)題？
例如，假設(shè)我們的數(shù)據(jù)老是沖突，怎么辦？
這個(gè)時(shí)候的訪問(wèn)，就會(huì)偏離我們初始的目的，即不遍歷
因?yàn)樵L問(wèn)一個(gè)數(shù)據(jù)，老是要往后遍歷，很麻煩
隨著數(shù)據(jù)的增多，沖突的概率增加，查找的成本越來(lái)越高。
也就是說(shuō)，問(wèn)題源于數(shù)據(jù)太多，而空間不夠
怎么辦？
很簡(jiǎn)單，擴(kuò)容。
那么，我們應(yīng)該什么時(shí)候擴(kuò)容呢？
很簡(jiǎn)單，用負(fù)載因子判斷。
好，什么是負(fù)載因子？
負(fù)載因子就是數(shù)據(jù)個(gè)數(shù)所占整個(gè)空間的比率。
例如
10個(gè)空間，有2個(gè)數(shù)據(jù)
負(fù)載因子就是0.2
10個(gè)空間，有7個(gè)數(shù)據(jù)
負(fù)載因子就是0.7
所以，每插入一個(gè)位置，我們就讓負(fù)載因子+1
而一般來(lái)說(shuō)，負(fù)載因子達(dá)到0.7就要進(jìn)行擴(kuò)容。
1.4哈希桶
回到文章開(kāi)始，我們說(shuō)哈希表一般有兩種形式，
一個(gè)叫做線性探測(cè)表，前面已經(jīng)解釋清楚。
另一個(gè)，叫做哈希桶。
長(zhǎng)這個(gè)樣子：
我們已經(jīng)知道哈希桶長(zhǎng)什么樣子，下面我們來(lái)解釋：
為什么要有哈希桶？
假如我有一組數(shù)據(jù)。
這一組數(shù)據(jù)是：2，22，222，2222，22222，222222，2222222，22222222........
好的，數(shù)據(jù)我給你了。
你存吧。
你想要怎么存？
如果按照線性探測(cè)表的方式進(jìn)行存儲(chǔ)：
好家伙，你一看數(shù)據(jù)，你發(fā)現(xiàn)
取余數(shù)，結(jié)果全是2
存一個(gè)沖突一個(gè)
存兩個(gè)沖突兩個(gè)
存三個(gè)沖突三個(gè)
.....
從頭沖突到尾，沒(méi)完沒(méi)了。
怎么辦？
很明顯，線性探測(cè)形式的哈希表有著致命的弱點(diǎn)
即無(wú)法對(duì)余數(shù)相同的數(shù)據(jù)進(jìn)行處理
沖突了，只有往后放
我的位置沖突了，我就去放別人的位置，讓別人沖突
（沒(méi)錯(cuò)，就是這么強(qiáng)大，你打我?。?/p>
如此一來(lái)，當(dāng)數(shù)據(jù)越來(lái)越多時(shí)，哈希沖突的概率將會(huì)越來(lái)越大
哈希沖突多了，就會(huì)導(dǎo)致查找的成本越來(lái)越高
哈希表的優(yōu)勢(shì)也會(huì)越來(lái)越微弱
怎么辦？
于是，哈希桶來(lái)了。
我這么存：
我現(xiàn)在無(wú)論是存12，22，32，42，52還是222222222222
還會(huì)和其他位置沖突嗎？
不會(huì)。
哈希桶將沖突的值，放到同一個(gè)位置下，用單鏈表管理起來(lái)
哈希桶的結(jié)構(gòu)，極大的優(yōu)化了線性探測(cè)表無(wú)法處理哈希沖突的缺點(diǎn)
同時(shí)，單鏈表的訪問(wèn)，其時(shí)間復(fù)雜度也控制在O(n)的量級(jí)。
非常棒。
哈希桶也存在負(fù)載因子的問(wèn)題，
和線性探測(cè)負(fù)載因子是一樣的邏輯
同樣，也是大于0.7就進(jìn)行擴(kuò)容
擴(kuò)容是對(duì)數(shù)組的擴(kuò)容
而擴(kuò)容之后，單鏈表的長(zhǎng)度也會(huì)變短
為什么？
例如空間從10變?yōu)?00
原來(lái)2，12，22，32，42，52，62，72，82，92等值都只能掛在下標(biāo)2的位置
但是當(dāng)空間變?yōu)?00
瞬間，所有的值都有了自己對(duì)應(yīng)的下標(biāo)位置
原本長(zhǎng)度為10的哈希桶，直接變?yōu)?
優(yōu)化效果相當(dāng)棒
這，就是哈希桶
1.5閑散列與開(kāi)散列
1、閑散列：開(kāi)放定址法（線性探測(cè)/二次探測(cè)）
二次檢測(cè)：當(dāng)數(shù)據(jù)比較集中的時(shí)候，查找會(huì)比較慢，
為了更快的查找，下一個(gè)位置查找偏移量不為1，可以為2次方
思路：我的位置被別人占了，我就去占別人得位置
沖突越多，效率越低
因此，有人提出了開(kāi)散列
2、開(kāi)散列：哈希桶/拉鏈法
1.6總結(jié)
綜上，我們來(lái)總結(jié)一下：
1、值很分散，因此哈希表也叫做散列表
2、有些值不好映射，比如string，結(jié)構(gòu)體等
3、開(kāi)空間問(wèn)題，即哈希沖突
4、哈希表是用哈希思想實(shí)現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)
hash更多的來(lái)說(shuō)，是一種思想
例如編碼表也是一種哈希編碼的運(yùn)用
例如經(jīng)典的ASCII碼表
同時(shí)，有時(shí)候你會(huì)發(fā)現(xiàn)你打開(kāi)某些文件，會(huì)出現(xiàn)亂碼
為什么？
因?yàn)榇a表對(duì)錯(cuò)了，原本這個(gè)文件要拿表A來(lái)映射
結(jié)果拿成表B來(lái)映射了
所以結(jié)果就是亂碼
亂碼的本質(zhì)是編碼表對(duì)亂了
以上就是關(guān)于哈希表的基礎(chǔ)概念和知識(shí)。
下面博主要帶大家設(shè)計(jì)出一個(gè)簡(jiǎn)易版哈希表
即unordered_set和unordered_map
使用c++實(shí)現(xiàn)，總體還是比較難的
涉及模板、多層嵌套封裝、泛型編程、內(nèi)外部類、友元等
需要有一定的c++基礎(chǔ)。
其實(shí)簡(jiǎn)單理解就夠了，不必跟著我寫(xiě)出一個(gè)。
二、設(shè)計(jì)hash表
1、哈希表的設(shè)計(jì)
??1）插入
如果位置不被占，插入；如果位置被占，遇到空才插入??????
插入邏輯：
先是數(shù)據(jù)%size，為什么是size而不是capacity呢？
因?yàn)閏apacity后面的的值是沒(méi)法訪問(wèn)的，end位置是size前一個(gè)位置
然后找到空/被刪除的位置，插入，n++
n是記錄哈希表個(gè)數(shù)的值，為什么不用size呢？
因?yàn)閔ash表是離散的表
如果hash表數(shù)值很多，就有很大的概論發(fā)生沖突
怎么辦？
設(shè)置一個(gè)負(fù)載因子，用來(lái)記錄hash表內(nèi)的數(shù)據(jù)個(gè)數(shù)的占比
一般是0.7~0.8
如果hash表滿了呢？在找空/被刪除位置時(shí)，就會(huì)出現(xiàn)死循環(huán)的問(wèn)題
滿了就擴(kuò)容
擴(kuò)容之后，原有的值不能拷貝，需要重新映射，新的hash表的size是原有空間的2倍
處理數(shù)據(jù)冗余：插入前利用find
??2）查找
遇到空才停止，但是如果中間位置有空位置，就查不到后面的位置，如何解決？
設(shè)置一個(gè)位置狀態(tài)：EMPTY、DELETE，EXIST
?3）刪除
刪除的值不必抹除，而是將狀態(tài)設(shè)置為DELETE。
如果抹除，設(shè)置為什么值都不合適
因此，刪除是一個(gè)偽刪除，查找值時(shí)依舊能找到
在Find函數(shù)需要特殊判斷，即存在才查找
如果數(shù)據(jù)不能取%怎么辦？
例如string數(shù)據(jù)類型
用仿函數(shù)進(jìn)行解決
對(duì)于整型、浮點(diǎn)型、指針都進(jìn)行size_t強(qiáng)轉(zhuǎn)為整型，就可以取%
但是string不可以轉(zhuǎn)化為整型
怎么辦？
單獨(dú)寫(xiě)一個(gè)為string轉(zhuǎn)換的仿函數(shù)
這個(gè)仿函數(shù)返回string【0】
4）字符串哈希算法
把字符串轉(zhuǎn)型為整型
將每一個(gè)字符的ASCII值*某個(gè)數(shù)值，累計(jì)加
最后每一個(gè)字符串的結(jié)果一般都不會(huì)重復(fù)，但是依舊會(huì)重復(fù)
string很常見(jiàn)，那可以對(duì)仿函數(shù)使用特化
什么是特化？就是對(duì)某些類進(jìn)行特殊化處理
就是不適用模板推廣，而是直接使用
2、封裝map和set
1、完成對(duì)hash表的基礎(chǔ)功能
一個(gè)哈希表要有的功能：
插入、刪除、遍歷（迭代器）
2、完成封裝
插入、刪除、查找的接口封裝
3、對(duì)應(yīng)的迭代器
????????1）首先是一個(gè)迭代器對(duì)象，完成對(duì)象的簡(jiǎn)單框架
????????哈希表的迭代器，需要哈希表本身，以及哈希表對(duì)應(yīng)位置的節(jié)點(diǎn)
????????其內(nèi)部的哈希表，需要外部調(diào)用對(duì)象哈希表來(lái)初始化
????????2）++重載
????????????????1、先算出當(dāng)前所在位置
????????????????2、當(dāng)前位置的下一個(gè)位置不為空，那就是有直接返回
????????????????3、當(dāng)前位置為空，要繼續(xù)找后面的位置
4、【】方括號(hào)重載
返回值是一個(gè)pair，第一個(gè)參數(shù)是迭代器，第二個(gè)參數(shù)是bool，判斷是否添加成功
如果已經(jīng)存在，返回已存在節(jié)點(diǎn)的迭代器，以及false
如果節(jié)點(diǎn)不存在，返回新插入節(jié)點(diǎn)的迭代器，以及true
需要修改insert的返回值
以及find的返回值
這樣就可以直接對(duì)find和insert進(jìn)行復(fù)用
方括號(hào)重載返回值為value
三、設(shè)計(jì)原碼
1、HashTable
#pragma once
#include
#include
using namespace std;
//設(shè)計(jì)一個(gè)hash表
//哈希表是一個(gè)vector數(shù)組
//節(jié)點(diǎn)存儲(chǔ)的是一個(gè)pair節(jié)點(diǎn)
//使用模板編程
//如果插入的是string,就不能取%
//怎么辦？字符串哈希算法
//使用仿函數(shù)
enum State
{
EXIST,
DELETE,
EMPTY
};
template
struct hashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct hashFunc
{
size_t operator()(const string& key)
{
size_t ret = 0;
for (auto ch : key)
{
ret *= 131;
ret += ch;
}
return ret;
}
};
namespace hash
{
//哈希表節(jié)點(diǎn)
template
struct HashData
{
pair
State _state = EMPTY;
};
//定義哈希表
template
class HashTable
{
public:
typedef HashData
HashTable()
{
_tables.resize(10);
}
//插入
bool Insert(const pair
{
if (Find(kv.first))
{
return false;
}
//檢查擴(kuò)容
if (_n / _tables.size() >= 0.7)
{
size_t newSize = _tables.size() * 2;
HashTable
newHashTable._tables.resize(newSize);
//重新插入新空間
for (size_t i = 0; i < _tables.size(); ++i)
{
newHashTable.Insert(_tables[i]._kv);
}
}
//1、找到插入的位置，取%
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
++hashi;
}
//3、插入,更新負(fù)載因子
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
_n++;
return true;
}
//查找
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST &&
_tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}
size_t size()
{
return _n;
}
//刪除
bool Erase(const K& key)
{
Node* cur = Find(key);
if (cur)
{
cur->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector
size_t _n = 0;
};
void HashTest()
{
HashTable
ht.Insert({ 1,1 });
ht.Insert({ 2,2 });
ht.Insert({ 3,3 });
ht.Insert({ 4,4 });
ht.Insert({ 3,3 });
ht.Insert({ 3,3 });
cout << ht.Find(1) << endl;
cout << ht.Find(2) << endl;
cout << ht.Find(3) << endl;
cout << ht.Find(4) << endl;
cout << ht.size() << endl;
ht.Erase(1);
ht.Erase(2);
cout << ht.size() << endl;
}
void HashTest1()
{
HashTable
ht.Insert({ "abcd",1});
ht.Insert({ "edasdfas",2});
ht.Insert({ "kahkahdk",3});
ht.Insert({ "ohjahsflhasf",4});
cout << ht.size() << endl;
size_t ret = hashFunc
size_t ret1 = hashFunc
cout << ret << endl;
cout << ret1 << endl;
}
}
//哈希桶實(shí)現(xiàn)
namespace hash_bucket
{
//哈希節(jié)點(diǎn)，是一個(gè)鏈表
template
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
前置聲明
//template
//class HashTable;
實(shí)現(xiàn)迭代器
//template
//struct __HSIterator//這個(gè)是給hash表底層使用的迭代器對(duì)象
//{
// typedef HashNode
// typedef HashTable
// HashTable
// Node* _node;
// __HSIterator(const Node* node, const HashTable
// :_pht(pht)
// ,_node(node)
// {
// }
// //++
// Self& operator++()//返回結(jié)構(gòu)體對(duì)象
// {
// KeyOfT kot;
// Hash hs;
// size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
// Node* cur = _pht->_tables[hashi];
//
// if (_node->_next)
// {
// _node = _node->_next;
// }
// else//該節(jié)點(diǎn)為空
// {
// while (hashi < _pht->_tables.size())
// {
// if (cur == nullptr)
// {
// ++hashi;
// }
// else
// {
// break;
// }
// }
// if (hashi == _pht->_tables.size())
// {
// _node = nullptr;
// }
// else
// {
// _node = _pht->_tables[hashi];
// }
// }
//
// return *this;
// }
// //解引用*
// T& operator*()
// {
// return _node->_data;
// }
// T* operator->()
// {
// return &_node->_data;
// }
// bool operator!=(const Self& s)
// {
// return _node != s._node;
// }
//};
//哈希表
template
class HashTable
{
public:
友元聲明(但是這種方式的代碼過(guò)于冗余)
//template
//friend struct __HSIterator;
//內(nèi)部類
template
struct __HSIterator//這個(gè)是給hash表底層使用的迭代器對(duì)象
{
typedef HashNode
typedef __HSIterator Self;
const HashTable* _pht;
Node* _node;
__HSIterator( Node* node, const HashTable* pht)
:_pht(pht)
, _node(node)
{
}
//++
Self& operator++()//返回結(jié)構(gòu)體對(duì)象
{
if (_node->_next)
{
_node = _node->_next;
}
else//該節(jié)點(diǎn)為空
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size())
{
if (_pht->_tables[hashi])
break;
++hashi;
}
if (hashi == _pht->_tables.size())
{
_node = nullptr;
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
//解引用*
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
typedef __HSIterator
iterator begin()
{
//找到第一個(gè)非空節(jié)點(diǎn)
for (int i = 1;i< _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
//直接是空
return iterator(nullptr, this);
}
typedef HashNode
public:
HashTable()
{
_tables.resize(10,nullptr);
}
//插入
pair
{
Hash hs;//取模仿函數(shù)
KeyOfT kot;//取key仿函數(shù)
iterator it = Find(kot(data));
if (it._node != nullptr)//存在節(jié)點(diǎn)
{
return make_pair(it, false);
}
//擴(kuò)容
if (_n == _tables.size())
{
vector
for (size_t i = 0; i<_tables.size(); ++i)
{
//首先，插入頭節(jié)點(diǎn)
Node* cur = _tables[i];
//再處理后面的串
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % newTable.size();
//頭插
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
}
_tables.swap(newTable);
}
size_t hashi = hs(kot(data)) % _tables.size();
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return make_pair(iterator(newNode, this), true);
}
//查找
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return iterator(nullptr, this);
}
size_t size()
{
return _n;
}
//刪除
bool Erase(const K& key)
{
KeyOfT kot;
KeyOfT hs;
Node* prev = nullptr;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
//如果是第一個(gè)節(jié)點(diǎn)
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector
size_t _n = 0;
};
//void test_hash_bucket1()
//{
// HashTable
// hb.Insert({"asada",1});
// hb.Insert({"DASDAS",1});
// hb.Insert({"DASDAS",1});
// hb.Insert({"DASDAS",1});
// hb.Insert({"DASDAS",1});
// hb.Insert({"DASDAS",1});
// hb.Insert({"DASbAS",1});
// hb.Insert({"HHDH",1});
// //cout << hb.Erase("") << endl;
// cout << hb.size() << endl;
// cout << hb.Find("asada") << endl;
// cout << hb.Find("DASDAS") << endl;
// cout << hb.Find("HHDH") << endl;
//
//}
//void test_hash_bucket2()
//{
// vector
// HashTable
// for (size_t i = 0; i // { // if (i == 9) // { // int j = 0; // } // hb.Insert(make_pair(v[i],v[i])); // } // cout << hb.size() << endl; //} } 2、unordered_map #pragma once #pragma once #include"HashTable.h" namespace my_unordered_map { template class unordered_map { public: //仿函數(shù)d struct MapKeyOfT { const K& operator()(const pair { return kv.first; } }; typedef typename hash_bucket::HashTable iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair { return _ht.Insert(kv); } iterator find(const K& key) { return _ht.Find(key); } bool erase(const K& key) { return _ht.Erase(key); } //方括號(hào)重載 V& operator[](const K& key) { pair return ret.first->second; } private: hash_bucket::HashTable }; void test_unordered_map() { unordered_map um.insert({1,1}); um.insert({2,1}); um.insert({3,1}); um.insert({4,1}); um.insert({5,1}); um.insert({6,1}); um.find(1); //cout << um.find(2) << endl; //cout << um.find(200) << endl; } void test_unordered_map1() { unordered_map um.insert({ 1,1 }); um.insert({ 2,1 }); um.insert({ 3,1 }); um.insert({ 4,1 }); um.insert({ 5,1 }); um.insert({ 6,1 }); um[7]; um[8]; um[9]; um[10]; um[11]++; unordered_map while (it != um.end()) { cout << it->first << " "; ++it; } cout << endl; } void test_unordered_map2() { string arr[] = { "蘋(píng)果", "西瓜", "蘋(píng)果", "西瓜", "蘋(píng)果", "蘋(píng)果", "西瓜", "蘋(píng)果", "香蕉", "蘋(píng)果", "香蕉","蘋(píng)果","草莓", "蘋(píng)果","草莓" }; unordered_map for (auto& e : arr) { countMap[e]++; } for (auto e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; } }; 3、unordered_set #pragma once #include"HashTable.h" namespace my_unorded_set { template class unorded_set { public: struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; typedef typename hash_bucket::HashTable< K,const K, Hash, SetKeyOfT>::iterator iterator; iterator beigin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair { return _ht.Insert(key); } iterator find(const K& key) { return _ht.Find(key); } bool erase(const K& key) { return _ht.Erase(key); } private: hash_bucket::HashTable }; void test_unordered_set() { unorded_set us.insert(1); us.insert(2); us.insert(3); us.insert(4); us.insert(6); us.insert(7); //cout << us.find(1) << endl; //cout << us.find(100) << endl; cout << "http://" << endl; cout << us.erase(100) << endl; cout << us.erase(1) << endl; } void test_unordered_set1() { unorded_set us.insert(99); us.insert(4); us.insert(6); us.insert(7); us.insert(9); us.insert(2); us.insert(3); us.insert(11); us.insert(1); us.insert(96); us.insert(16); us.insert(56); us.insert(50); us.insert(57); us.insert(58); us.erase(11); unorded_set while (it != us.end()) { cout << *it << " "; ++it; } cout << endl; } }; 4、test #include"unordered_set.h" #include"unordered_map.h" int main() { //hash_bucket::test_hash_bucket1(); cout << "unordered_set" << ":"; my_unorded_set::test_unordered_set1(); cout << "unordered_map" << ":"; my_unordered_map::test_unordered_map1(); cout << "unordered_map方括號(hào)重載測(cè)試" << ":" << endl;; my_unordered_map::test_unordered_map2(); return 0; } 柚子快報(bào)激活碼778899分享：c++ 通俗易懂-＞哈希表詳解 精彩鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Jollychic時(shí)尚出海棧
