哈希表華山論劍

話(huà)說(shuō)這一日，編程語(yǔ)言聯(lián)合國(guó)準(zhǔn)備舉辦一次大會(huì)，主題為哈希表，給各大編程語(yǔ)言帝國(guó)都發(fā)去了邀請(qǐng)函。

很快就到了大會(huì)這一天。

聯(lián)合國(guó)秘書(shū)長(zhǎng)開(kāi)場(chǎng)發(fā)言：“諸位，為促進(jìn)技術(shù)交流與發(fā)展，增強(qiáng)各帝國(guó)友誼，聯(lián)合委員會(huì)特設(shè)此盛會(huì)，感謝諸位的捧場(chǎng)”

會(huì)場(chǎng)傳來(lái)一陣鼓掌聲······

秘書(shū)長(zhǎng)繼續(xù)發(fā)言：“本次大會(huì)的主題是哈希表，程序員們使用最多的數(shù)據(jù)容器之一，各大編程語(yǔ)言帝國(guó)相信都有實(shí)現(xiàn)。今天的大會(huì)就圍繞哈希表分為幾個(gè)議題討論，首先是第一個(gè)議題：存儲(chǔ)結(jié)構(gòu)與沖突解決”

存儲(chǔ)結(jié)構(gòu)與沖突解決

來(lái)自GoLang帝國(guó)的map率先發(fā)言：“哈希表，哈希表，首先得是個(gè)表嘛，所以最基本的要用一個(gè)數(shù)組來(lái)存儲(chǔ)，數(shù)組中的每一個(gè)元素叫做bucket。至于hash沖突嘛，就用鏈表來(lái)解決嘛”

圖片

GoLang帝國(guó)的map說(shuō)完，有人站了起來(lái)：“英雄所見(jiàn)略同！在下C++帝國(guó)的unordered_map，我們基本上也是選擇的這種方法”

此時(shí)，Python帝國(guó)的代表提出了質(zhì)疑：“鏈表確實(shí)可以解決沖突，不過(guò)嘛，這要是沖突太多，鏈表太長(zhǎng)，搜尋起來(lái)豈不費(fèi)時(shí)？”

GoLang帝國(guó)的map和C++帝國(guó)的unordered_map面面相覷，不知如何應(yīng)對(duì)。

“鏈表太長(zhǎng)的話(huà)，那就轉(zhuǎn)成樹(shù)結(jié)構(gòu)！”，就在這時(shí)，又有人站了起來(lái)。

見(jiàn)有人起身，Python帝國(guó)代表轉(zhuǎn)身問(wèn)道：“在下乃Python帝國(guó)的字典dict，敢問(wèn)閣下怎么稱(chēng)呼”

“我是Java帝國(guó)的HashMap，和前面兩位兄臺(tái)的策略大體相同，只是在沖突過(guò)多，具體來(lái)說(shuō)鏈表長(zhǎng)度超過(guò)8的時(shí)候就轉(zhuǎn)換成紅黑樹(shù)的結(jié)構(gòu)，以此加快查找”

圖片

說(shuō)完，map、unordered_map松了一口氣，和HashMap一起坐下了。

dict繼續(xù)發(fā)問(wèn)：“在座的都是這個(gè)思路，用鏈表解決沖突？”

說(shuō)完，另外一位代表站了起來(lái)，“等等，我們C#帝國(guó)的HashTable就沒(méi)用鏈表！”

dict露出了滿(mǎn)意的表情，“那你們是怎么解決沖突的呢？”

“咱HashTable內(nèi)部使用的是雙重散列法，咱內(nèi)部不止一種哈希計(jì)算方式，一次Hash沖突，咱就換一個(gè)再算，直到找到有空位的地方存儲(chǔ)”，HashTable回答到。

dict看起來(lái)有些失望，估計(jì)這也不是他所用的方式。

“你問(wèn)了半天，還沒(méi)說(shuō)你們Python是怎么處理沖突的呢？”，Java帝國(guó)的HashMap開(kāi)口了。

“是啊，是啊”，其他代表也跟著起哄。

見(jiàn)眾人起哄，dict只好應(yīng)答：“鏈表法固然不錯(cuò)，不過(guò)需要在插入數(shù)據(jù)過(guò)程中動(dòng)態(tài)分配內(nèi)存構(gòu)建鏈表節(jié)點(diǎn)，開(kāi)銷(xiāo)不小，我們沒(méi)有采用。”

“那到底用了啥，你倒是說(shuō)啊，快急死我了”，C++的unordered_map有些急了。

“我們用的是一種叫開(kāi)放尋址法的策略，如果發(fā)現(xiàn)了沖突，就按照制定的策略從這個(gè)位置往后找，直到找到有空的位置存儲(chǔ)”，dict{}繼續(xù)說(shuō)到。

圖片

“哪有那么簡(jiǎn)單的事，你把別人的位置占了，那對(duì)應(yīng)那個(gè)位置的數(shù)據(jù)來(lái)了怎么辦？還有查找怎么找？刪除怎么處理？這不全亂套了嗎”，unordered_map追問(wèn)不舍。

“是這樣的，按照我們既定的規(guī)則，在查找的時(shí)候就需要額外做一些工作，另外刪除的時(shí)候也不能直接刪除，否則會(huì)破壞規(guī)則鏈條·····”，接下來(lái)一段時(shí)間，dict給大家仔細(xì)介紹了他們的處理思路。

“你這個(gè)也太麻煩了，不如我們鏈表法來(lái)的清晰明了”

“這怎么就麻煩了？這好處不顯而易見(jiàn)嘛？”，dict也不甘示弱。

這時(shí)，秘書(shū)長(zhǎng)打斷了大家的爭(zhēng)辯：“諸位，諸位，靜一靜，靜一靜，咱們這個(gè)議題到此為止，進(jìn)入下一個(gè)議題：哈希到位置映射”

哈希到位置映射

急性子的C++帝國(guó)代表unordered_map第一個(gè)說(shuō)話(huà)：“這有什么好討論的，不就是用hash值對(duì)哈希表數(shù)組長(zhǎng)度進(jìn)行一個(gè)求模運(yùn)算嗎？”

圖片

“就是，這有什么好討論的”，C#帝國(guó)的HashTable也附和到。

“哎，此言差矣，我就沒(méi)用取模運(yùn)算”，眾人望去，這Python帝國(guó)的dict又要鬧什么新鮮玩意。

GoLang帝國(guó)的map問(wèn)道：“老哥用的什么辦法，別賣(mài)關(guān)子了，快說(shuō)來(lái)聽(tīng)聽(tīng)”

dict掃了眾人一眼說(shuō)到，“我的辦法就是：”

圖片

這是怎么個(gè)映射法？眾代表皆摸不著頭腦，議論紛紛，唯有Java帝國(guó)的HashMap聽(tīng)聞微微一笑。

dict見(jiàn)狀問(wèn)道：“HashMap兄臺(tái)，莫非知曉其中玄機(jī)？”

只見(jiàn)HashMap不緊不慢的站了起來(lái)說(shuō)到：“哈希表長(zhǎng)度是2的冪次，減1之后的二進(jìn)制均變成了1，比如長(zhǎng)度16，減1變成15，也就是二進(jìn)制1111。再進(jìn)行與運(yùn)算，相當(dāng)于取了哈希值的低位，直接映射到對(duì)應(yīng)的數(shù)組位置，與運(yùn)算比取模運(yùn)算要快不少。不瞞諸位，我HashMap中也是使用的這種方式，此乃雕蟲(chóng)小技，不值得炫耀”

圖片

眾代表聽(tīng)完紛紛點(diǎn)頭稱(chēng)贊，dict不知何時(shí)卻已坐下。

C#的HashTable問(wèn)道：“這樣直接取低幾位，會(huì)不會(huì)造成Hash值到數(shù)組的映射不均勻，拿你舉的例子來(lái)說(shuō)，18的二進(jìn)制是0001 0010，34的二進(jìn)制是0010 0010，他們的低4位都一樣，和1111與上以后都是0010，也就是都該存到數(shù)組的2號(hào)位，這豈不是一定程度上的增加了沖突的概率嗎？”

突如其來(lái)的質(zhì)疑并沒(méi)有讓HashMap慌亂，反而是從容不迫的解釋到：“C#代表的這個(gè)問(wèn)題提的非常好，不知dict兄臺(tái)是如何處理的。我們的方案是在進(jìn)行與運(yùn)算映射之前，對(duì)hash值進(jìn)行一個(gè)處理，具體來(lái)說(shuō)就是將其高16位與低16位進(jìn)行一個(gè)異或運(yùn)算，如此一來(lái)，最終參與與運(yùn)算的部分就融合了原始hash的全部信息，而不僅僅是低位。”

圖片

眾代表聽(tīng)完再次點(diǎn)頭稱(chēng)贊。

秘書(shū)長(zhǎng)打破了平靜，“看來(lái)大家收獲都頗豐，咱們接著下一個(gè)話(huà)題吧：初始容量與擴(kuò)容”

初始容量與擴(kuò)容

眾代表這一次皆不爭(zhēng)先，互相觀望。

秘書(shū)長(zhǎng)見(jiàn)狀說(shuō)到：“沒(méi)人主動(dòng)，那我可就要點(diǎn)名了······”

“那就我先吧”，Java帝國(guó)的HashMap站了起來(lái)，“我的默認(rèn)初始容量是16，有一個(gè)叫負(fù)載因子的參數(shù)，默認(rèn)是0.75。我的策略是，如果內(nèi)部數(shù)組的空間使用了超過(guò)75%，那就要準(zhǔn)備擴(kuò)容了，否則后續(xù)Hash沖突的概率就會(huì)很大。哦對(duì)了，擴(kuò)容時(shí)容量得是2的指數(shù)次方，原因前面已經(jīng)交代了”

圖片

dict第二個(gè)起身：“嗯，差不多，我的默認(rèn)初始容量是8，擴(kuò)容的時(shí)候也是要求是2的指數(shù)次方，另外我的負(fù)載因子是2/3，擴(kuò)容時(shí)機(jī)比這位HashMap老哥更早一些”

C#帝國(guó)代表HashTable聽(tīng)聞也起身發(fā)言：“我的初始容量是3，至于負(fù)載因子嘛，我經(jīng)過(guò)大量實(shí)驗(yàn)測(cè)試，得出的數(shù)據(jù)在兩位之間，是0.72。容量大小方面我就沒(méi)有2的指數(shù)次方的要求了，而是要求一個(gè)素?cái)?shù)。之所以要求素?cái)?shù)的原因，是因?yàn)槲沂褂玫那竽＿\(yùn)算進(jìn)行的映射，使用素?cái)?shù)的話(huà)，沖突會(huì)少一些。”

這時(shí)，C++帝國(guó)代表unordered_map也說(shuō)話(huà)了，“巧了！我也是素?cái)?shù)哎，你看，我提前把容量都算好存起來(lái)了，到時(shí)候擴(kuò)容就挨個(gè)取就行了。”

圖片

尾聲

時(shí)間過(guò)的很快，在大家熱情的討論中，一上午時(shí)間很快就結(jié)束了。

大會(huì)臨近尾聲，秘書(shū)長(zhǎng)致辭宣布：“感謝各位代表積極探討，大會(huì)取得圓滿(mǎn)成功，本次大會(huì)到此結(jié)束，咱們下次再會(huì)！”

會(huì)場(chǎng)再次傳來(lái)一陣熱烈的鼓掌聲······

然而就在此時(shí)，會(huì)場(chǎng)外突然傳來(lái)一個(gè)聲音：“舉辦如此盛會(huì)，怎能少了我”

眾人望去，皆嘆：“他果然還是來(lái)了”