前面我們已經(jīng)講到了數(shù)組和鏈表，數(shù)組能通過(guò)下標(biāo) O(1) 訪問(wèn)，但是刪除一個(gè)中間元素卻要移動(dòng)其他元素，時(shí)間 O(n)。 循環(huán)雙端鏈表倒是可以在知道一個(gè)節(jié)點(diǎn)的情況下迅速刪除它，但是吧查找又成了 O(n)。

難道就沒(méi)有一種方法可以快速定位和刪除元素嗎？似乎想要快速找到一個(gè)元素除了知道下標(biāo)之外別無(wú)他法，于是乎聰明的計(jì)算機(jī)科學(xué)家又想到了一種方法。 能不能給每個(gè)元素一種『邏輯下標(biāo)』，然后直接找到它呢，哈希表就是這種實(shí)現(xiàn)。它通過(guò)一個(gè)哈希函數(shù)來(lái)計(jì)算一個(gè)元素應(yīng)該放在數(shù)組哪個(gè)位置，當(dāng)然對(duì)于一個(gè) 特定的元素，哈希函數(shù)每次計(jì)算的下標(biāo)必須要一樣才可以，而且范圍不能超過(guò)給定的數(shù)組長(zhǎng)度。

我們還是以書中的例子說(shuō)明，假如我們有一個(gè)數(shù)組 T，包含 M=13 個(gè)元素，我們可以定義一個(gè)簡(jiǎn)單的哈希函數(shù) h

h(key) = key % M

這里取模運(yùn)算使得 h(key) 的結(jié)果不會(huì)超過(guò)數(shù)組的長(zhǎng)度下標(biāo)。我們來(lái)分別插入以下元素：

765, 431, 96, 142, 579, 226, 903, 388

先來(lái)計(jì)算下它們應(yīng)用哈希函數(shù)后的結(jié)果:

?

下邊我畫個(gè)圖演示整個(gè)插入過(guò)程(純手工繪制，原諒我字寫得不太優(yōu)雅):

?

哈希沖突 (collision)

這里到插入 226 這個(gè)元素的時(shí)候，不幸地發(fā)現(xiàn) h(226) = h(96) = 5，不同的 key 通過(guò)我們的哈希函數(shù)計(jì)算后得到的下標(biāo)一樣， 這種情況成為哈希沖突。怎么辦呢？聰明的計(jì)算機(jī)科學(xué)家又想到了辦法，其實(shí)一種直觀的想法是如果沖突了我能不能讓數(shù)組中 對(duì)應(yīng)的槽變成一個(gè)鏈?zhǔn)浇Y(jié)構(gòu)呢？這就是其中一種解決方法，叫做 鏈接法(chaining)。如果我們用鏈接法來(lái)處理沖突，后邊的插入是這樣的：

?

這樣就用鏈表解決了沖突問(wèn)題，但是如果哈希函數(shù)選不好的話，可能就導(dǎo)致沖突太多一個(gè)鏈變得太長(zhǎng)，這樣查找就不再是 O(1) 的了。 還有一種叫做開(kāi)放尋址法(open addressing)，它的基本思想是當(dāng)一個(gè)槽被占用的時(shí)候，采用一種方式來(lái)尋找下一個(gè)可用的槽。 （這里槽指的是數(shù)組中的一個(gè)位置），根據(jù)找下一個(gè)槽的方式不同，分為：

• 線性探查(linear probing): 當(dāng)一個(gè)槽被占用，找下一個(gè)可用的槽。h(k,i)=(h′(k)+i)%m,i=0,1,...,m?1h(k,i)=(h′(k)+i)%m,i=0,1,...,m?1
• 二次探查(quadratic probing): 當(dāng)一個(gè)槽被占用，以二次方作為偏移量。 h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,...,m?1h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,...,m?1
• 雙重散列(double hashing): 重新計(jì)算 hash 結(jié)果。 h(k,i)=(h1(k)+ih2(k))%mh(k,i)=(h1(k)+ih2(k))%m

我們選一個(gè)簡(jiǎn)單的二次探查函數(shù) h(k,i)=(home+i2)%mh(k,i)=(home+i2)%m，它的意思是如果 遇到了沖突，我們就在原始計(jì)算的位置不斷加上 i 的平方。我寫了段代碼來(lái)模擬整個(gè)計(jì)算下標(biāo)的過(guò)程：

?
這段代碼輸出的結(jié)果如下：

?
遇到?jīng)_突之后會(huì)重新計(jì)算，每個(gè)待插入元素最終的下標(biāo)就是：

?

Cpython 如何解決哈希沖突

如不同 cpython 版本實(shí)現(xiàn)的探查方式是不同的，后邊我們自己實(shí)現(xiàn) HashTable ADT 的時(shí)候會(huì)模仿這個(gè)探查方式來(lái)解決沖突。

?

哈希函數(shù)

到這里你應(yīng)該明白哈希表插入的工作原理了，不過(guò)有個(gè)重要的問(wèn)題之前沒(méi)提到，就是 hash 函數(shù)怎么選？ 當(dāng)然是散列得到的沖突越來(lái)越小就好啦，也就是說(shuō)每個(gè) key 都能盡量被等可能地散列到 m 個(gè)槽中的任何一個(gè)，并且與其他 key 被散列到哪個(gè)槽位無(wú)關(guān)。 如果你感興趣，可以閱讀后邊提到的一些參考資料。視頻里我們使用二次探查函數(shù)，它相比線性探查得到的結(jié)果沖突會(huì)更少。

裝載因子(load factor)

如果繼續(xù)往我們的哈希表里塞東西會(huì)發(fā)生什么？空間不夠用。這里我們定義一個(gè)負(fù)載因子的概念(load factor)，其實(shí)很簡(jiǎn)單，就是已經(jīng)使用的槽數(shù)比哈希表大小。 比如我們上邊的例子插入了 8 個(gè)元素，哈希表總大小是 13， 它的 load factor 就是 8/13≈0.628/13≈0.62。當(dāng)我們繼續(xù)往哈希表插入數(shù)據(jù)的時(shí)候，很快就不夠用了。 通常當(dāng)負(fù)載因子開(kāi)始超過(guò) 0.8 的時(shí)候，就要新開(kāi)辟空間并且重新進(jìn)行散列了。

重哈希(Rehashing)

當(dāng)負(fù)載因子超過(guò) 0.8 的時(shí)候，需要進(jìn)行 rehashing 操作了。步驟就是重新開(kāi)辟一塊新的空間，開(kāi)多大呢？感興趣的話可以看下 cpython 的 dictobject.c 文件然后搜索 GROWTH_RATE 這個(gè)關(guān)鍵字，你會(huì)發(fā)現(xiàn)不同版本的 cpython 使用了不同的策略。python3.3 的策略是擴(kuò)大為已經(jīng)使用的槽數(shù)目的兩倍。開(kāi)辟了新空間以后，會(huì)把原來(lái)哈希表里 不為空槽的數(shù)據(jù)重新插入到新的哈希表里，插入方式和之前一樣。這就是 rehashing 操作。

HashTable ADT

實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)，這里我們來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)化版的哈希表 ADT，主要是為了讓你更好地了解它的工作原理，有了它，后邊實(shí)現(xiàn)起 dict 和 set 來(lái)就小菜一碟了。 這里我們使用到了定長(zhǎng)數(shù)組，還記得我們?cè)跀?shù)組和列表章節(jié)里實(shí)現(xiàn)的 Array 吧，這里要用上了。

解決沖突我們使用二次探查法，模擬 cpython 二次探查函數(shù)的實(shí)現(xiàn)。我們來(lái)實(shí)現(xiàn)三個(gè)哈希表最常用的基本操作，這實(shí)際上也是使用字典的時(shí)候最常用的操作。

• add(key, value)
• get(key, default)
• remove(key)

?
具體的實(shí)現(xiàn)和代碼編寫在視頻里講解。這個(gè)代碼可不太好實(shí)現(xiàn)，稍不留神就會(huì)有錯(cuò)，我們還是通過(guò)編寫單元測(cè)試驗(yàn)證代碼的正確性。公眾號(hào)：學(xué)習(xí)py最風(fēng)sao的方式歡迎大家繼續(xù)關(guān)注！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的哈希表数据结构_算法与数据结构-哈希表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。