1. 一山二虎

此前我們已經(jīng)多次指出，對于需要?jiǎng)討B(tài)維護(hù)的散列表沖突是不可避免的，無論你的散列函數(shù)設(shè)計(jì)的有多么精妙，因此我們不得不回答的第二個(gè)重要問題就是一旦發(fā)生沖突，我們應(yīng)該如何加以排解？

當(dāng)然任何一種可行的排解方法都應(yīng)該是在事先就約定好的預(yù)案。

所謂沖突，形象地說也就是一山不容二虎。那么倘若的確有兩只老虎呢？用鐵絲網(wǎng)將這座山分成兩部分，兩只老虎各居一側(cè)。這種思路也就是所謂的多槽位法。如果此前的桶單員對應(yīng)于山，那么每一個(gè) slot 就對應(yīng)于在這個(gè)山中用鐵絲網(wǎng)分割出的一個(gè)子區(qū)域。

在這幅圖中，如果這是散列表，那么這就是一個(gè)又一個(gè)的桶單元。在這里我們將每個(gè)桶單元都繼續(xù)細(xì)分為 a、b、c、d 四個(gè)槽位。每個(gè)桶內(nèi)部的這些槽位就可以用來存放彼此沖突的若干個(gè)詞條。

比如這就是一個(gè)長度為 23 的散列表，其中每一個(gè)桶都被分成了三個(gè)槽位?，F(xiàn)在我們依次將24個(gè)詞條插入其中。

可以看到這里，盡管有些詞條的確會彼此沖突，但依然可以在對應(yīng)的桶中和平共處。當(dāng)然，查找過程需要多出一步，除了需要根據(jù)關(guān)鍵碼確定對應(yīng)的統(tǒng)單元地址，還需要在桶中遍歷所有的槽位，直到找到目標(biāo)或者失敗。

當(dāng)然，只要每個(gè)桶中槽位的總數(shù)能夠控制在常數(shù)以內(nèi)，整體的查找效率就不會有實(shí)質(zhì)的降低。

不過這種方法的缺點(diǎn)也是顯而易見的，你能看得出來嗎？是的，每一桶具體應(yīng)該細(xì)分為多少個(gè)槽位？在事先幾乎是無法預(yù)測的。如果分得過細(xì)，就會造成空間上的浪費(fèi)。而反過來，無論你分得多細(xì)，在極端情況下仍有可能在某個(gè)特定的桶中發(fā)生大規(guī)模的沖突。那么面臨這一兩難的抉擇如何破解呢？

2. 涇渭分明

多槽位法在空間效率和時(shí)間效率之間的兩難處境？我們在學(xué)習(xí)向量時(shí)也曾遇到過，還記得那時(shí)的解決辦法嗎？是的，改用列表。

新的策略，如這幅圖（上圖）所示，如果這是整個(gè)桶數(shù)組，那么其中每一個(gè)單元都將各自擁有一個(gè)對應(yīng)的列表。而每一個(gè)列表都可以用來存放一組彼此沖突的詞條。是的，將相互沖突的詞條串接起來，也就是所謂的 separate chaining。

來看獨(dú)立鏈法的一個(gè)實(shí)例，依然是一個(gè)長度為23的散列表。接下來我們將64個(gè)詞條插入其中。請留意觀察每個(gè)桶所對應(yīng)的列表是如何演化的。
~ ?
相對于與多槽位法獨(dú)立鏈法的優(yōu)勢非常明顯，比如除了最初的空鏈表，我們無需預(yù)留任何更多的空間。而且表的長度可以根據(jù)需要自由的伸縮。只要系統(tǒng)的資源足夠，任意多次的沖突都可以解決。

得益于此前對 List 結(jié)構(gòu)的良好封裝，我們只需寥寥幾句即可實(shí)現(xiàn)相應(yīng)的散列表結(jié)構(gòu)。當(dāng)然，這種方法的缺點(diǎn)也同樣是很明顯的。比如這里需要引入額外的指針，而為了生成或銷毀節(jié)點(diǎn)也需要借助動(dòng)態(tài)內(nèi)存的申請，相對于常規(guī)的操作，此類動(dòng)態(tài)申請操作的時(shí)間成本大致要高出兩個(gè)數(shù)量級。

然而這種方法最大的缺陷還不僅于此，你能發(fā)現(xiàn)嗎？是的，系統(tǒng)的緩存功能。在這里，每桶內(nèi)部的查找都是沿著對應(yīng)的列表順序進(jìn)行的。然而在此之前，不同列表中各節(jié)點(diǎn)的插入和銷毀次序完全是隨機(jī)的。比如可能會是這樣(上圖中的黃色線條)。

因此，對于任何一個(gè)列表而言，其中的節(jié)點(diǎn)在物理空間上往往不是連續(xù)分布。因此系統(tǒng)很難預(yù)測你的訪問方向，無法通過有效的緩存加速查找過程。當(dāng)散列表的規(guī)模非常之大，以至于不得不借助 IO 時(shí)，這一矛盾就顯得更加突出了。 那么為了有效的激活并充分利用系統(tǒng)的緩存功能，我們又當(dāng)如何繼續(xù)改進(jìn)呢？

3. 開放定址

反觀獨(dú)立鏈法，其采用的是所謂封閉定址策略 closed addressing。也就是說，對于散列表中的任何一個(gè)單元，在其所對應(yīng)的列表中能夠存放，而且只能夠存放那些與這個(gè)桶單元的地址，比如 k ，相沖突的詞條。

也就是說每個(gè)詞條應(yīng)該屬于哪個(gè)桶所對應(yīng)的列表都是在事先已經(jīng)注定了的。不難理解，只要采用這種策略，就很難保證每組沖突的詞條在空間上能夠彼此毗鄰。 因此后續(xù)我們應(yīng)該放棄這種策略并反其道而行之，也就是采用所謂的開放定址策略 open addressing。

這種策略的特點(diǎn)是散列表所占用的空間在物理上始終是地址連續(xù)的一塊，相應(yīng)的所有的沖突都在這塊連續(xù)的空間中加以排解，而無需向獨(dú)立鏈法那樣申請額外的空間。沒錯(cuò)，所有的散列以及沖突排解都在這樣一塊封閉的空間內(nèi)完成。

因此相應(yīng)的這種策略也可以稱作為閉散列 closed hashing。既然是閉散列，那么每一個(gè)桶單元都應(yīng)該面向所有可能的詞條開放。也就是說在特定的情況下，每一個(gè)詞條都有可能存放在任何一個(gè)桶中。

當(dāng)然對于每一個(gè)特定的詞條具體存放在哪個(gè)桶中是有不同的優(yōu)先級的。其中優(yōu)先級最高的自然是它本來就應(yīng)該歸屬的那個(gè)桶。從這個(gè)桶開始，所有的桶都按照某種優(yōu)先級關(guān)系排成一個(gè)序列。

而在查找對應(yīng)的詞條時(shí)，我們也總是從這個(gè)序列的起點(diǎn)出發(fā)，順次去嘗試每一個(gè)桶單元。每個(gè)詞條所對應(yīng)的這樣一個(gè)序列，也稱作試探序列、試探鏈或者查找鏈。當(dāng)然，沿查找鏈的查找，同樣有兩種結(jié)果，或者在某一個(gè)特定的桶中找到目標(biāo)元素，也就是所謂的成功，或者一旦抵達(dá)第一個(gè)空桶即可報(bào)告失敗。

那么具體的應(yīng)該如何來約定查找鏈呢？

4. 線性試探

查找鏈的第一種組織方法就是所謂的線性試探。具體來說，所謂的 linear probing 就是一旦發(fā)生沖突之后，我們會轉(zhuǎn)而去試探它的后繼，后繼的后繼，以及后繼的后繼的后繼，諸如此類。同樣的，最終可能會因?yàn)榘l(fā)現(xiàn)目標(biāo)而報(bào)告成功，或者因?yàn)榈诌_(dá)某個(gè)空桶，而說明查找失敗。

可以看到，在如此形勢的散列表中，除了數(shù)據(jù)詞條，無需任何附加空間。

而更重要的是，每一查找鏈都集中在某一局部。因此系統(tǒng)的緩存作用將得到充分的發(fā)揮，而對于大規(guī)模的數(shù)據(jù)集，如此更可以有效地減少 IO。當(dāng)然，這種策略同樣也具有它的弱點(diǎn)。

其中重要一點(diǎn)就是為了消除以往的沖突，可能會導(dǎo)致后續(xù)發(fā)生更多的沖突。來看這樣一個(gè)實(shí)例，考察一個(gè)長度為7的散列表。

假設(shè)我們需要插入的是 0 1 2 3 7 這樣 5 個(gè)詞條，如果就按照這種順序依次插入，那么首先是0就位，1 就位，2 和3 也相繼就位。為了插入最后的7，我們首先去試探 0 號單元，結(jié)果發(fā)現(xiàn)它非空，為了排解這一沖突，我們會轉(zhuǎn)而試探它的后繼，也就是 1 號單元，情況一樣，進(jìn)而去試探 2 號 3號單元，直到最終在4號單元發(fā)現(xiàn)一個(gè)空桶，從而將7安置在這個(gè)桶中。在這個(gè)散列表的生命期內(nèi)發(fā)生沖突的只有一個(gè)詞條，也就是7。
~ ?
現(xiàn)在再來看另一插入次序，比如將 7 調(diào)整到最前端，首先插入它，我們依然開始于一個(gè)空的散列表。按照約定的次序，首先將 7 安置在0號桶，沒有沖突。既然0號單元已被占用，所以接下來插入 0 必然發(fā)生一次沖突，并經(jīng)過一次試探，最終將 0 安置在 1 號單元。至此1號桶也會被占用。因此接下來詞條 1 的插入也會發(fā)生一次沖突，并最終將它安置在 2 號桶。這樣的故事還會發(fā)生多次，具體的也需要在這個(gè)位置發(fā)現(xiàn)一次沖突之后，再將詞條2存入到3號桶，最后依然要經(jīng)過一次沖突，才能將詞條 3 存入 4 號桶。在整個(gè)這樣的過程中，詞條0、詞條1 2和3都發(fā)生了沖突。前后對比不難發(fā)現(xiàn)后一種插入序列所對應(yīng)的很多沖突本來的確是可以不必發(fā)生的。

5. 賴惰刪除

以線性試探為代表的開放定址策略在使用時(shí)若要支持詞條的刪除，則需格外的小心。我們來就此做一探討。按照這種策略先后插入彼此沖突的一組詞條都將存放在同一個(gè)查找序列中。而更確切地講，他們應(yīng)該按照邏輯次序構(gòu)成整個(gè)查找鏈的一個(gè)前綴，其中不得有任何的空桶縫隙。

因此詞條的刪除操作需要做額外的一些處理。反之如果直接將詞條刪除，那么被刪除的詞條所留下的空桶就有可能將查找鏈切斷，從而導(dǎo)致在此之后的詞條丟失掉。盡管他們的確存在于散列表中，卻如何也訪問不到。

針對這一問題，一種簡明的方法就是所謂的懶惰刪除 lazy removal。也就是說如果在某個(gè)桶中此前曾有一個(gè)詞條，那么在這個(gè)詞條被刪除之后，我們并不是簡單地將這個(gè)桶清空，而是為其做上一個(gè)特殊的標(biāo)記，比如說R，在這樣一個(gè)桶所屬的每一條查找鏈中，這類桶單元將根據(jù)具體情況可能扮演兩種角色。

如果是針對某一特定詞條的查找，那么在抵達(dá)這個(gè)桶時(shí)，根據(jù)這個(gè)標(biāo)志我們就知道不應(yīng)該在此中斷，而因越過它繼續(xù)查找下去。反過來，如果我們是為了插入新的詞條而尋找一個(gè)空桶，那么在首次抵達(dá)帶有這樣一個(gè)標(biāo)志的桶之后，就可以將它等效的視作是一個(gè)空桶，并將待插入的新詞條徑直的插入其中。

應(yīng)該說針對開放定制策略，懶度刪除不僅是不得已而為之的方法，也甚至可以說是針對這種情況的最優(yōu)方法。因?yàn)楫吘乖陂_放定址策略中，每一個(gè)同單元都同時(shí)屬于多個(gè)查找鏈。