什么是哈希

我們來重新認(rèn)識(shí)一下數(shù)據(jù)查找的過程：

在順序結(jié)構(gòu)以及平衡樹中，記錄的關(guān)鍵碼與其存儲(chǔ)位置之間沒有對(duì)應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過關(guān)鍵碼的多次比較。順序查找時(shí)間復(fù)雜度為O(N)，平衡樹中為樹的高度，即O($lo{g}_{2}N$)，搜索的效率取決于搜索過程中元素的比較次數(shù)。

順序結(jié)構(gòu)： 指的是順序表、鏈表等線性數(shù)據(jù)結(jié)構(gòu)，具體在C++中表現(xiàn)為像vector、list這樣的容器；

平衡樹： 指的是AVL樹、紅黑樹等樹形數(shù)據(jù)結(jié)構(gòu)，具體在C++中表現(xiàn)為map、set這樣的容器；

記錄： 指的是容器或數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的元素（或者說數(shù)據(jù)），為了方便后面表述什么哈希的相關(guān)知識(shí)，特地用這個(gè)名詞來指代；

關(guān)鍵碼： 它是一個(gè)記錄的唯一標(biāo)識(shí)，可能是記錄本身或者記錄中的某一項(xiàng)。舉個(gè)例子，假如說記錄是一個(gè)整數(shù) or 字符串，記錄的關(guān)鍵碼就是記錄本身，假設(shè)記錄是一個(gè)鍵值對(duì)，記錄的關(guān)鍵碼就是鍵值對(duì)中的key；假設(shè)記錄是某個(gè)類對(duì)象，記錄的關(guān)鍵碼就是對(duì)象中的某幾個(gè)成員變量；

存儲(chǔ)位置： 顧名思義，就是一個(gè)記錄在 容器 or 數(shù)據(jù)結(jié)構(gòu) 之中的存儲(chǔ)位置。

這里有一組水果相關(guān)的英文單詞，它們存儲(chǔ)在不同容器之中，可以看到記錄的關(guān)鍵碼與其存儲(chǔ)位置之間沒有對(duì)應(yīng)的關(guān)系。

正因?yàn)闆]有關(guān)系，假設(shè)我現(xiàn)在查找的目標(biāo)記錄是"watermelon"，就只能從起點(diǎn)開始，挨個(gè)地比較每個(gè)記錄的關(guān)鍵碼和目標(biāo)記錄的關(guān)鍵碼的值是 “ = ” 還是 “ ≠ ”，直到出現(xiàn)相等或者找完才算是有結(jié)果，所以才說，元素的查找效率取決于關(guān)鍵碼的比較次數(shù)。

那么有沒有一種理想化的狀態(tài)：查找的過程中，可以不通過任何的比較，而是讓記錄的關(guān)鍵碼和記錄的存儲(chǔ)位置通過某種手段建立起一種一對(duì)一的映射關(guān)系，通過關(guān)鍵碼直接就可以找到目標(biāo)記錄。

而達(dá)成這種理想化的查找狀態(tài)的方法就是 “ 哈希 ”（或者說 “ 散列 ”），通過這個(gè)方法實(shí)現(xiàn)的存儲(chǔ)結(jié)構(gòu)，我們稱之為 “ 哈希表 ”（或者說 “ 散列表 ”），記錄的關(guān)鍵碼和記錄的存儲(chǔ)位置建立映射關(guān)系的手段我們稱之為 “ 哈希函數(shù) ”（或者說 “ 散列函數(shù) ”），哈希函數(shù)的作用是將記錄的關(guān)鍵碼轉(zhuǎn)換成記錄在哈希表的地址，對(duì)于這個(gè)地址我們一般稱之為 “ 哈希值 ”（或者 “ 哈希地址 ”）。

" 哈希 "一詞源自于英文單詞 " hash "，而 " 散列 " 則是 " hash " 的中文翻譯。最初，這兩個(gè)術(shù)語可能在不同的語境中出現(xiàn)，但隨著時(shí)間的推移，它們逐漸成為了同義詞，并在計(jì)算機(jī)科學(xué)領(lǐng)域中得到廣泛使用。哈希是直接音譯，散列則是意譯。

哈希表的插入操作大致為，“ 使用哈希函數(shù)計(jì)算出待插入記錄的關(guān)鍵碼的哈希值，即記錄插入在哈希表的位置 ，然后插入 ” ；查找操作大致為，“ 使用哈希函數(shù)計(jì)算出待插入記錄的關(guān)鍵碼的哈希值，在哈希表中按此位置取元素比較，若關(guān)鍵碼相等，則查找成功 ” 。

哈希函數(shù)

從上面來看，哈希函數(shù)可以說是哈希這個(gè)思想的關(guān)鍵，所以我們就來看看常用的哈希函數(shù)都有哪些。

直接定址法

直接定址法的做法是直接取記錄的關(guān)鍵碼的某個(gè)線性函數(shù)值來作為哈希地址。

哈希函數(shù)的公式：
$$\text{Hash(Key)}=A\times \text{Key}+B$$

我們來看下面這兩個(gè)例子（例子來自《大話數(shù)據(jù)結(jié)構(gòu)》，因?yàn)楸容^好懂，我就直接拿來借用一下）。

這個(gè)的哈希函數(shù)的優(yōu)點(diǎn)就是簡單，但它只適合記錄關(guān)鍵碼分布范圍較小且數(shù)據(jù)重復(fù)度高度的場景，在某些極端場景下可能會(huì)造成極大的空間浪費(fèi)。

因此，直接定址法雖然因?yàn)楹唵味Ｒ姷菂s不使用，真正實(shí)用的哈希函數(shù)還得是接下來講的除留余數(shù)法。

除留余數(shù)法

假設(shè)散列表的長度為 $capaicty$，$p$ 是一個(gè)不大于 $capaicty$，但最接近或者等于 $capaicty$ 的質(zhì)數(shù)，除留余數(shù)法的公式如下：
$$\text{Hash(Key)}=\text{Key}\%p,(p\le \text{capacity})$$

從這個(gè)例子中我們能看到，哪怕最大值和最小值之間相差了999998，進(jìn)行取模運(yùn)算之后，我們也可以在表中找到一個(gè)位置存儲(chǔ)記錄。

然而，除留余數(shù)法還有一個(gè)致命的問題，假設(shè)我們?cè)偻砝锊迦胗涗?$48$ 時(shí)，此時(shí)就會(huì)出現(xiàn) $Hash(4)$ 和 $Hash(48)$ 的哈希值都是 $4$ 的現(xiàn)象，像這樣的，當(dāng)不同關(guān)鍵碼通過相同哈希哈函數(shù)數(shù)計(jì)算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或哈希碰撞。

而關(guān)鍵碼不同、哈希地址相同的記錄，我們稱為 “ 同義詞 ” 。

發(fā)生哈希沖突該如何處理呢？

哈希沖突

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

閉散列

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

線性探測法

線性探測的做法是，從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個(gè)空位置為止。
哈希函數(shù)的公式為：$$\text{Hash(Key)}=(\text{Hash(key)}+d_i)\%p,(d_i=1,2,3,\dots ,p?1)$$

假設(shè)哈希地址為 $8$ 和 $10$ 的位置已經(jīng)存儲(chǔ)有記錄，這時(shí)候要 “ 回頭 ” 找空位置。

從上面的插入例子，我們能看到：

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

• 線性探測缺點(diǎn)：一旦發(fā)生哈希沖突，所有的沖突連在一起，容易產(chǎn)生數(shù)據(jù)“堆積”，即：不同關(guān)鍵碼占據(jù)了可利用的空位置，使得尋找某關(guān)鍵碼的位置需要許多次比較，導(dǎo)致搜索效率降低（就像哈希值為 $8$ 和 $10$ 的位置存在記錄時(shí)插入記錄 $44$ 一樣）。

二次探測法

為了避免線性探測法產(chǎn)生 “ 堆積 ” 現(xiàn)象，還有一種找空位置的方法叫做二次探測法，與線性探測法不同的是，二次探測法使用的增量序列是 $d_i=1^2,?1^2,2^2,?2^2,\dots ,q^2,?q^2,(q\le \frac{p}{2})$，這樣的增量序列會(huì)讓記錄更加均勻的分布，從而達(dá)到降低哈希碰撞的概率。

二次探測法的哈希函數(shù)公式：
$$\text{Hash(Key)}=(\text{Hash(key)}+d_i)\%p,(d_i=1^2,?1^2,2^2,?2^2,\dots ,q^2,?q^2,q\le \frac{p}{2})$$

從上面的例子看到，用二次探測法來處理線性探測法的殘局還是很有效的。

負(fù)載因子和閉散列的擴(kuò)容

哈希表中還有一個(gè)叫做 “ 負(fù)載因子 ” 的概念，它的定義為：
$$\text{負(fù)載因子}=\frac{\text{當(dāng)前哈希表記錄個(gè)數(shù)}}{\text{哈希表的長度}}$$

由于表的長度是一個(gè)定值，負(fù)載因子與 “ 填入表中的記錄個(gè)數(shù) ” 成正比，所以，當(dāng)負(fù)載因子越大，表明填入表中的記錄就越多，產(chǎn)生哈希沖突的可能性就越大，而哈希表的查找效率與哈希沖突的息息相關(guān)，在閉散列不可避免會(huì)產(chǎn)生哈希沖突的情況下，我們應(yīng)當(dāng)盡量降低哈希沖突的可能性。

存在研究表明：

當(dāng)表的長度為質(zhì)數(shù)且表裝載因子a不超過0.5時(shí)，新的表項(xiàng)一定能夠插入，而且任何一個(gè)位置都不會(huì)被探查兩次，如果插入過程中超過0.5就考慮對(duì)哈希表進(jìn)行擴(kuò)容，這種方法雖然查找效率極高，但是空間浪費(fèi)也很嚴(yán)重。

而當(dāng)負(fù)載因子超過0.8時(shí)，哈希表的空間利用率雖然提高了，但是查表時(shí)的CPU緩存不命中率次數(shù)會(huì)按照按照指數(shù)曲線上升，查找效率反而急速下降。

一般來說，負(fù)載因子控制在0.5到0.7之間空間利用率和操作效率之間取得較好的平衡。

哈希表的擴(kuò)容一般是1.5倍擴(kuò)容或者是2倍擴(kuò)容，對(duì)哈希表進(jìn)行擴(kuò)容操作之后有一個(gè)點(diǎn)要處理，除留余數(shù)法的的操作讓關(guān)鍵碼除以表長后的余數(shù)作為哈希值，因此需要重新計(jì)算所有記錄的哈希值，并將它們重新分配到新的哈希表中。

這個(gè)過程涉及以下幾個(gè)步驟：

1. 創(chuàng)建一個(gè)新的、更大容量的哈希表。
2. 將舊哈希表中的所有鍵值對(duì)重新計(jì)算哈希值，并根據(jù)新的表長，將它們插入到新的哈希表中的相應(yīng)位置。
3. 銷毀舊的哈希表，釋放內(nèi)存空間。

開散列

閉散列處理哈希沖突的思路是，這個(gè)位置有 “ 人 ” 了，我就找一個(gè)新的位置，但其實(shí)思路還可以再換一換，為了有沖突就一定得換地方呢？我們直接就在原地想辦法不可以嗎？

于是就有了這里的開散列法。

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

像上圖那樣，已經(jīng)不存在什么沖突換地址的問題了，無論來多少個(gè)沖突的記錄，都只是在當(dāng)前位置給單鏈表增加結(jié)點(diǎn)的問題。

開散列對(duì)于可能會(huì)造成很多沖突的哈希函數(shù)來說，提供了絕對(duì)不會(huì)出現(xiàn)找不到地址的保障，但是這也并不是沒有代價(jià)的，單鏈表來存儲(chǔ)沖突記錄就以為著需要遍歷單鏈表的性能損耗。

開散列的擴(kuò)容

桶的個(gè)數(shù)是一定的，隨著元素的不斷插入，每個(gè)桶中元素的個(gè)數(shù)不斷增多，極端情況下，可能會(huì)導(dǎo)致一個(gè)桶中鏈表節(jié)點(diǎn)非常多，會(huì)影響的哈希表的性能，因此在一定條件下需要對(duì)哈希表進(jìn)行增容，，那該條件怎么確認(rèn)呢？

對(duì)于開散列來說最好的情況是：每個(gè)哈希桶中剛好掛一個(gè)節(jié)點(diǎn)，再繼續(xù)插入元素時(shí)，每一次都會(huì)發(fā)生哈希沖突，因此，在記錄個(gè)數(shù)剛好等于桶的個(gè)數(shù)時(shí)，即負(fù)載因子為 $1$ 時(shí)，可以給哈希表增容。

擴(kuò)容的過程為如下幾個(gè)步驟：

1. 創(chuàng)建一個(gè)新的、更大容量的哈希表。
2. 遍歷舊哈希表中的每個(gè)哈希桶，將其中的記錄的關(guān)鍵碼對(duì)重新計(jì)算哈希值，并將其挪到新的哈希表中的對(duì)應(yīng)位置。
3. 釋放舊哈希表的內(nèi)存空間。

非整形關(guān)鍵碼

除留余數(shù)法中，% 運(yùn)算符已經(jīng)規(guī)定了左右操作數(shù)是整形，右邊的運(yùn)算符是表長，它本身就是一個(gè)整數(shù)，不用過多考慮，關(guān)鍵是記錄的關(guān)鍵碼，假如說記錄的關(guān)鍵碼是一個(gè)字符串而不是一個(gè)整數(shù)時(shí)，我們又該怎么處理呢？

其實(shí)就是一句話，關(guān)鍵碼不是整形，那就轉(zhuǎn)換成整型！

方法一：直接轉(zhuǎn)換

通過觀察我們發(fā)現(xiàn)，所謂字符串其實(shí)就是多個(gè)字符的組合，而字符的本質(zhì)其實(shí)是ASCII碼，也是一個(gè)整型值，最簡單的處理我們可以考慮將一個(gè)字符串中所有字符的ASCII碼加起來作為記錄的關(guān)鍵碼，比如說字符串 "hello"，ASCII 碼表中 'h' 的值是 104，'e' 的值是 101，'l' 的值是 108，'o' 的值是 111，那么，$$關(guān)鍵碼=104+101+108+108+111=532$$

但是，這個(gè)方法也有很大的缺陷，容易引發(fā)哈希沖突，假設(shè)字符串是 "olleh"，它轉(zhuǎn)換處理出來的關(guān)鍵碼同樣也是 532，這必然會(huì)導(dǎo)致哈希沖突。

方法二：加權(quán)轉(zhuǎn)換

為了減少哈希沖突，可以為每個(gè)字符指定一個(gè)權(quán)值，然后將每個(gè)字符的ASCII碼值乘以對(duì)應(yīng)的權(quán)值再相加，得到一個(gè)關(guān)鍵碼。這種方法可以根據(jù)實(shí)際情況調(diào)整權(quán)重，以盡可能地減少哈希沖突。

同樣以字符串 "hello" 為例，給定一個(gè)權(quán)值數(shù)組，例如 [1, 3, 5, 7, 11]，$$\text{hello?的關(guān)鍵碼}=104\times 1+101\times 3+108\times 5+108\times 7+111\times 11=2924$$

假設(shè) "olleh" 的權(quán)值數(shù)組也是 [1, 3, 5, 7, 11]，但是轉(zhuǎn)換后的關(guān)鍵碼，卻不是一樣的，$$\text{olleh?的關(guān)鍵碼}=111\times 1+108\times 3+108\times 5+105\times 7+104\times 11=2854$$

有興趣的話，這里推薦一篇文章《各種字符串Hash函數(shù)》，里面的內(nèi)容是關(guān)于如何調(diào)整權(quán)值來最大化的減少哈希沖突發(fā)生的可能性，以及各種字符串哈希函數(shù)之間的性能對(duì)比。

方法三：自定義轉(zhuǎn)換

根據(jù)應(yīng)用場景的特點(diǎn)，設(shè)計(jì)自定義的轉(zhuǎn)換方法。例如，對(duì)于日期類型的關(guān)鍵碼，可以將日期轉(zhuǎn)換成天數(shù)或秒數(shù)作為整數(shù)哈希碼；對(duì)于自定義類對(duì)象，可以根據(jù)對(duì)象的屬性值計(jì)算出一個(gè)整數(shù)哈希碼，這個(gè)就不好距離了，得根據(jù)實(shí)際需求來定。文章來源地址http://www.zghlxwxcb.cn/news/detail-852788.html

到了這里，關(guān)于由淺入深一步步了解什么是哈希（概念向）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！