注：本文如涉及到代碼，均經(jīng)過Python 3.7實(shí)際運(yùn)行檢驗(yàn)，保證其嚴(yán)謹(jǐn)性。

本文閱讀時(shí)間約為6分鐘。

前面說過，如果兩個(gè)數(shù)據(jù)項(xiàng)被散列映射到同一個(gè)槽，需要一個(gè)系統(tǒng)化的方法在散列表中保存第二個(gè)數(shù)據(jù)項(xiàng)，這個(gè)過程被稱為“解決沖突”。

如果散列函數(shù)是完美的，那就不會(huì)有散列沖突，但實(shí)際情況是，完美散列函數(shù)常常并不存在，解決散列沖突成為散列方法中很重要的一部分。

解決散列的一種方法就是，為沖突的數(shù)據(jù)項(xiàng)再找一個(gè)開放的空槽來保存。最簡單的就是從沖突的槽開始往后掃描，直到碰到一個(gè)空槽。如果到散列表尾部還未找到，則從首部接著掃描。

這種尋找空槽的技術(shù)被稱為“開放定址（open addressing）”。

向后逐個(gè)槽尋找的方法則是開放定址技術(shù)中的“線性探測（linear probing）”。

線性探測Linear Probing

還是以前面說過的這一組數(shù)據(jù)來作為示例說明線性探測具體如何操作。
假設(shè)有下列數(shù)據(jù)項(xiàng)：

54, 26, 93, 17, 77, 31

通過求余法我們得到了其散列值及對應(yīng)槽號如下圖Pic-512-1的上半部分所示。

Pic-512-1 線性探測示例

現(xiàn)在，我們要做的是，把44、55、20三個(gè)數(shù)據(jù)項(xiàng)逐個(gè)插入到該散列表中。具體過程如下：

h(44)=0，但發(fā)現(xiàn)0#槽已被77占據(jù)，向后（向右）找到第一個(gè)空槽#1，把44保存在1#槽中。

h(55)=0，因?yàn)?#槽、1#槽均已被占據(jù)，后面的2#槽是空的，因此把55保存在2#槽中。

h(20)=9，發(fā)現(xiàn)9#槽已被31占據(jù)，向右，10#也被54占據(jù)，再從頭掃描，0#、1#、2#等槽均已被占據(jù)，后面的3#槽是空的，因此把20保存在3#槽中。

整個(gè)過程如上圖Pic-512-1所示。

上述方法就是開放定址里的線性探測法。

需要注意的是，如果采用線性探測方法來解決散列沖突的話，那么散列表的查找也應(yīng)該遵循同樣的規(guī)則。

如果在散列位置沒有找到查找項(xiàng)的話，就必須向后做順序查找，直到找到查找項(xiàng)或者碰到空槽（即查找失?。?/p>

線性探測的改進(jìn)

線性探測法有一個(gè)缺點(diǎn)，就是有聚集的趨勢，即：如果同一個(gè)槽沖突的數(shù)據(jù)項(xiàng)較多的話，這些數(shù)據(jù)項(xiàng)就會(huì)在槽附近聚集起來，從而連鎖式影響其他數(shù)據(jù)項(xiàng)的插入。

為了避免這種不利的聚集趨勢，一種方法就是將線性探測擴(kuò)展，從逐個(gè)探測改為跳躍式探測。比如，以+3的方式探測插入44、55、20。

還是用線性探測的例子來說明跳躍式探測是具體如何操作的。

還是假設(shè)有下列數(shù)據(jù)項(xiàng)：

54, 26, 93, 17, 77, 31

我們現(xiàn)在要把44、55、20三個(gè)數(shù)據(jù)項(xiàng)跳躍式（指定以+3的間隔）插入到該散列表中。具體過程如下：

h(44)=0，但發(fā)現(xiàn)0#槽已被77占據(jù)，向后+3個(gè)槽，找到#3槽。#3槽是空槽，可以存放數(shù)據(jù)，于是把44保存在3#槽中。

h(55)=0，因?yàn)?#槽，向后+3個(gè)槽，找到#3槽，已有數(shù)據(jù)項(xiàng)44；繼續(xù)向后+3個(gè)槽，找到#6槽，已有數(shù)據(jù)項(xiàng)17在里面；繼續(xù)向后+3個(gè)槽，找到#9槽，依然有數(shù)據(jù)項(xiàng)31占據(jù)著；繼續(xù)向右+3個(gè)槽，到了#1槽。#1槽為空，可以存放數(shù)據(jù)項(xiàng)，于是把55保存在#1槽中。

h(20)=9，發(fā)現(xiàn)9#槽已被31占據(jù)，向右+3個(gè)槽，找到1#槽，不為空；繼續(xù)向右+3個(gè)槽，找到#4，有26在里面；繼續(xù)向右+3個(gè)槽，#7槽為空，可以存放數(shù)據(jù)項(xiàng)，于是把20存放到#7槽中。

如下圖Pic-512-2所示：

Pic-512-2 跳躍式探測示例

沖突解決方案：再散列rehashing

重新尋找空槽的過程可以用一個(gè)更為通用的“再散列rehashing”來概括：

newhashvalue = rehash(oldhashvalue)

對于線性探測來說，

rehash(pos) = (pos + 1) % sizeoftable

對于“+3”的跳躍式探測則是：

rehash(pos) = (pos + 3) % sizeoftable

跳躍式探測的再散列通式是：

rehash(pos) = (pos + skip) % sizeoftable

這里要注意的是，skip的取值不能被散列表大小整除，否則會(huì)產(chǎn)生周期，造成很多空槽永遠(yuǎn)無法探測到的后果。如果把散列表的大小設(shè)為質(zhì)數(shù)（如11），則可以避免這種情況。

除了將線性探測改善為跳躍式探測，還能將其變?yōu)椤岸翁綔y（quadratic probing）”。

二次探測是什么意思呢？就是對于

rehash(pos) = (pos + skip) % sizeoftable

來說，skip的值不再是固定的某個(gè)值，而是逐步增加的，如1、3、5、7、9等。
這樣槽號就會(huì)是原散列值以平方數(shù)增加：

h, h+1, h+4, h+9, h+16...

這也是一種能令散列值分散的好辦法。

沖突解決方案：數(shù)據(jù)項(xiàng)鏈Chaining

除了尋找空槽的開放定址技術(shù)之外，另一種解決散列沖突的方案是，將容納單個(gè)數(shù)據(jù)項(xiàng)的槽擴(kuò)展為容納數(shù)據(jù)項(xiàng)集合（或者對數(shù)據(jù)項(xiàng)鏈表的引用）。

這樣，散列表中的每個(gè)槽就可以容納多個(gè)數(shù)據(jù)項(xiàng)，如果有散列沖突發(fā)生，只需要簡單地將數(shù)據(jù)項(xiàng)添加到數(shù)據(jù)項(xiàng)集合中。

查找數(shù)據(jù)項(xiàng)時(shí)則需要查找同一個(gè)槽中的整個(gè)集合。在同一個(gè)集合中查找，就用順序查找法。當(dāng)然，隨著散列沖突的增加，對數(shù)據(jù)項(xiàng)的查找時(shí)間也會(huì)相應(yīng)增加。

還是拿那組數(shù)據(jù)為例：

54, 26, 93, 17, 77, 31

要求插入44、55、20三個(gè)數(shù)據(jù)項(xiàng)。

如用數(shù)據(jù)項(xiàng)鏈的方法，每個(gè)槽都可以容納一個(gè)數(shù)據(jù)項(xiàng)的集合。操作示意如下圖Pic-512-3所示：

Pic-512-3 數(shù)據(jù)項(xiàng)鏈?zhǔn)纠?/div>

To be continued.