沖突的普遍性 ? ? 生日悖論

我們可以考慮這樣一個(gè)實(shí)際問題：某課堂上的所有學(xué)生中，是否由某兩位在同一天過生日（稱作生日巧合）？

不妨將一年當(dāng)作一個(gè)容量為 365 的桶數(shù)組，以生日作為關(guān)鍵碼將所有學(xué)生組織為一個(gè)散列表。于是，上述關(guān)于生日巧合的問題就可以嚴(yán)格地轉(zhuǎn)化并表述為：
對于這樣的散列表，關(guān)鍵碼之間至少發(fā)生一次沖突的可能性有多大呢？我們將 n 個(gè)學(xué)生在場時(shí)對應(yīng)的這一概率記作 P 365 (n)。

• 若學(xué)生總數(shù) n > 365，則根據(jù)鴿巢原理，沖突將注定出現(xiàn)，即 P 365 (n) = 100%。
• 對于 n ≤ 365，運(yùn)用排列組合的知識不難證明：
  P 365 (n) = 1 -365!/（(365-n)! × 365 n）

這一概率與我們的知覺相差很大。實(shí)際上，哪怕只有 23 個(gè)學(xué)生在場，你也值得打賭認(rèn)定存在生日的巧合? ?因?yàn)?** P 365 (23) = 50.7%。**
隨著學(xué)生的增多，這一概率會(huì)急劇上升。

解決沖突

由上面的分析可知，沖突是普遍存在的，我們可以設(shè)法降低沖突發(fā)生的可能性，但最終都無法徹底回避沖突。那么，一旦發(fā)生沖突，有什么有效的方法可以解決沖突呢？

（1）分離鏈（Separate chaining）

解決沖突最直截了當(dāng)?shù)囊环N辦法，就是將所有相互沖突的條目組成一個(gè)（小規(guī)模的）映射結(jié)構(gòu)，存放在它們共同對應(yīng)的桶單元中。

也就是說，桶單元 A [ i ] 對應(yīng)于映射結(jié)構(gòu) ** M ** * i * ，其中存放所有滿足h(key) = i 的條目(key, value)。

按照這一思路，針對關(guān)鍵碼key的任何操作，都將轉(zhuǎn)化為對一個(gè)與之相對應(yīng)的映射結(jié)構(gòu) M h(key) 的操作。比如put(key, value)操作，將首先在 M h(key) 中查找關(guān)鍵碼等于key的條目。若存在這樣的條目，則將其中的數(shù)據(jù)對象替換為value；否則，生成一個(gè)新條目(key, value)，并將其插入 M h(key) 中。get(key)操作和remove(key)操作的過程也與此類似，都要首先在 M h(key) 中查找關(guān)鍵碼key。

實(shí)際上，既然好的散列函數(shù)能夠?qū)⑺嘘P(guān)鍵碼盡可能均勻地分布到桶數(shù)組的各個(gè)單元，所以通常 M h(key) 的規(guī)模的確都不大，其中相當(dāng)多的桶中只含有單個(gè)條目，有些甚至是空的。

因此，完全可以直接通過鏈表結(jié)構(gòu)來實(shí)現(xiàn)每個(gè)** M ** * i * ? ?這種解決沖突的策略也由此得名。

（2）沖突池（Collision pool）

解決沖突的另一種辦法，就是在散列表 A [ ] 之外另設(shè)一個(gè)映射結(jié)構(gòu)P，一旦（在插入條目時(shí)）發(fā)生沖突，就將沖突的條目存入P中。從效果來看，這相當(dāng)于將所有沖突的條目存入一個(gè)緩沖池，該方法也因此得名。

為此，get(key)、put(key, value)和 remove(key)操作中的查找算法都需做相應(yīng)的調(diào)整：

• 如果桶單元 A[h(key)]為空且不帶記號，則報(bào)告“查找失敗”；否則，若該桶中存放的不是所需的條目，則轉(zhuǎn)到 P 中繼續(xù)查找。

remove(key)算法也需做相應(yīng)的調(diào)整：

• 如果找不到待刪除的條目，則操作可以立即完成；若在沖突池 P 中找到該條目，則可利用映射結(jié)構(gòu) ADT 提供的操作來實(shí)施刪除；若待刪除條目出現(xiàn)在散列表的桶 A[h(key)]中，則不僅需要?jiǎng)h除該條目，還要繼續(xù)給該桶做個(gè)標(biāo)記??否則，在沖突池中與 key沖突的那些關(guān)鍵碼都將會(huì)“丟失”掉。

沖突池法的構(gòu)思簡單，易于實(shí)現(xiàn)，在沖突不甚頻繁的場合，仍不失為一種較好的選擇。

其實(shí)，由于沖突池本身也是一個(gè)映射結(jié)構(gòu)，故這種結(jié)構(gòu)也可以理解為散列表的遞歸形式。

（3）開放定址（Open addressing）

分離鏈策略可以非常便捷地實(shí)現(xiàn)映射結(jié)構(gòu)的各種操作算法，但也不是盡善盡美。比如，就數(shù)據(jù)結(jié)構(gòu)本身而論，這一策略需要借助列表作為附加結(jié)構(gòu)，將相互沖突的條目分組存放。這不僅會(huì)增加代碼出錯(cuò)的可能，而且也需要占用更多的空間。

在這類情況下，我們只能在不借助附加結(jié)構(gòu)的條件下解決散列的沖突。開放定址就是這樣一種策略，實(shí)際上，由這一策略可以導(dǎo)出一系列的
變型，比如線性探測法、平方探測法以及雙散列法等等。由于不能使用附加空間，所以開放定址策略要求裝填因子λ ≤ 1，通常都要保證λ ≤ 0.5。

** 線性探測（Linear probing）**

采用開放定址策略，最簡單的一種形式就是線性探測法。

也就是說，在執(zhí)行 put(key, value )操作時(shí)，倘若發(fā)現(xiàn)桶單元 A[h(key)]已經(jīng)被占用，則轉(zhuǎn)而嘗試桶單元 A[h(key)+1]。要是 A[h(key)+1]也被占用了，就繼續(xù)嘗試 A[h(key)+2]。如果還有沖突，則繼續(xù)嘗試 A[h(key)+3]。如此不斷地進(jìn)行嘗試，直到發(fā)現(xiàn)一個(gè)可以利用的桶單元。當(dāng)然，為了保證桶地址的合法性，第 i 次嘗試的桶單元應(yīng)該為：

A[(h(key)+i) mod N]，i = 1, 2, 3, …。

按照這種辦法，被嘗試的桶單元地址構(gòu)成一個(gè)線性等差數(shù)列，故由此得名。

相應(yīng)地，get(key)和 remove(key)操作中的查找算法也需要有所調(diào)整。此時(shí)，若首次對 A[h(key)]的查找失敗，并不意味著關(guān)鍵碼 key 未在映射中出現(xiàn)。實(shí)際上，我們還需要依次掃描 A[h(key)]后續(xù)的各個(gè)桶單元 A[h(key)+1]、A[h(key)+2]、A[h(key)+3]、…，直到發(fā)現(xiàn)關(guān)鍵碼為 key 的條目（查找成功），或者到達(dá)一個(gè)空桶（查找失?。?/p>

若 H 是基于線性探測法實(shí)現(xiàn)的，則對于任一條目 e ∈ C i ，e 的 查找前驅(qū)桶單元均非空。

只有如此，才能保證線性探測式查找的順利進(jìn)行，因此也稱之為線性探測法的“桶地址連續(xù)條件”。

這一條件不僅需要在各種操作進(jìn)行之前得到滿足，而且在每一操作完成之后也應(yīng)繼續(xù)保持，以便進(jìn)行后續(xù)的操作。不難看出，對于 get(key)和 put(key, value)操作而言，這一點(diǎn)都不成問題。

然而，對于remove(key)操作，在每次將目標(biāo)條目 e 移除之后，還需要將以 e 為查找前驅(qū)單元的所有條目依次前移一個(gè)單元，填補(bǔ)刪除 e 后留出的空桶，以保持查找前驅(qū)桶非空條件。不過，這一解決辦法無疑會(huì)增加 remove(key)操作的時(shí)間復(fù)雜度。

在強(qiáng)調(diào)刪除效率的場合，可以采用另一種變通的解決辦法，以避免大量條目的移動(dòng)。每次移除條目 e 之后，可以為 e 原先占用的空桶做個(gè)特殊的記號。如此一來，查找算法只需稍做修改：每次遇到標(biāo)有這種記號的桶單元，都直接轉(zhuǎn)向后繼。另外，put(key, value)操作中的查找算法也需要有所改動(dòng)：在查找的過程中，需要記錄下最靠前的帶有記號的桶單元??若最終查找失敗，則將新條目存放到其中。

盡管線性探測法可以節(jié)約空間，但各操作的相應(yīng)實(shí)現(xiàn)卻要復(fù)雜得多。

線性探測法的最大缺陷在于，基于這一策略的散列表中往往會(huì)存在大量的條目堆積（Clustering）。實(shí)際上，因?yàn)椴荒苁褂萌魏胃郊拥目臻g，所以線性探測法每解決一次沖突都必然占用一個(gè)空桶，于是未來發(fā)生沖突的可能性也隨之增加。

實(shí)驗(yàn)統(tǒng)計(jì)表明，在一般情況下條目堆積現(xiàn)象也很普遍，當(dāng)裝填因子超過 0.5 時(shí)，這一問題更為突出。

平方探測（Quadratic probing）

平方探測法是對線性探測法的改進(jìn)。具體來說，就是在發(fā)生沖突時(shí)，依次對桶單元：

A[(h(key) + j 2 ) mod N], j = 0, 1, 2, …

進(jìn)行探測，直到發(fā)現(xiàn)一個(gè)可用的空閑桶。

這一策略可以很好地解決條目堆積的問題。這里充分利用了二次函數(shù)的特點(diǎn)，隨著沖突次數(shù)的增加，其探測的步長將以線性的速度增長，而不是像線性探測法那樣始終采用固定步長（=1）。因此，一旦發(fā)生沖突，這一辦法可以使待插入條目快速地“跳”離條目聚集的區(qū)段。

不過，這一方法也存在一些不足。首先，與線性探測法一樣，基于平方探測法的 remove(key)操作實(shí)現(xiàn)非常復(fù)雜。

其次，盡管這一策略可以有效回避條目堆積的現(xiàn)象，但還是會(huì)出現(xiàn)所謂的二階聚集（Secondary clustering）現(xiàn)象??條目雖然不會(huì)連續(xù)地聚集成片，卻會(huì)在多個(gè)（間斷的）位置多次“反彈”。

最后，如果散列表容量 N 不是素?cái)?shù)，則有可能會(huì)出現(xiàn)循環(huán)反彈，以至于無法插入的情況。即使 N 選為素?cái)?shù)，也必須保證裝填因子λ < 0.5，否則即便存在空桶，仍有可能無法找不到插入位置。

雙散列（Double hashing）

雙散列也是克服條目堆積現(xiàn)象的一種有效辦法。為此我們需要選取一個(gè)二級散列函數(shù) g()，一旦在插入 e = (key, value)時(shí)發(fā)現(xiàn) A[h(key)]已被占用，則不斷嘗試：

A[h(key) + j×g(key)]，j = 1, 2, …。

顯然，對任何關(guān)鍵碼 key，函數(shù)值 g(key)都不能為零??否則就會(huì)在“原地踏步”。
通常，若散列表長度為素?cái)?shù) N，則取另一素?cái)?shù) q < N，并取

g(key) = q - (key mod q)

為了盡可能地使關(guān)鍵碼均勻分布，可以通過實(shí)驗(yàn)統(tǒng)計(jì)確定最佳的 q 值。

綜合比較

相比而言，分離鏈策略的算法簡單，但需要耗費(fèi)更多空間。開放定址策略正好相反，可以盡可能地節(jié)省空間，但算法需做較復(fù)雜的調(diào)整。理論分析和實(shí)驗(yàn)統(tǒng)計(jì)都表明，就通常的桶數(shù)組容量 N 與裝填因子λ而言，分離鏈策略的時(shí)間效率要遠(yuǎn)遠(yuǎn)高于其它的方法。因此，除非在存儲(chǔ)空間非常緊張的場合，我們都建議采用分離鏈策略解決沖突。