資料結構中散列表（雜湊表）經典之衝突處理

雜湊是在記錄的儲存位置和它的關鍵字之間建立一個確定的對應關係f，使得每個關鍵字key對應一個儲存位置f(key)，建立了關鍵字與儲存位置的相互對應關係，這種關係f 稱為雜湊函數（雜湊函數）。本文小編主要講述雜湊函數的衝突處理問題。

在尋找過程中，關鍵碼的比較次數，取決於產生衝突的多少，產生的衝突少，查找效率就高，產生的衝突多，查找效率就低。因此，影響產生衝突多少的因素，也就是影響查找效率的因素。影響產生衝突多少有以下三個因素：

1. 雜湊函數是否均勻；

#2. 處理衝突的方法;

3. 散列函數是否均勻；

#2. 處理衝突的方法;

3. 散列表的裝填因子。

散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度

α是散列表裝滿程度的標誌因子。由於表長是定值，α與「填入表中的元素個數」成正比，所以，α越大，填入表中的元素較多，產生衝突的可能性就越大；α越小，填入表中的元素較少，產生衝突的可能性就越小。

實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理衝突的方法有不同的函數。

解決雜湊衝突的方法一般有：

NO.1開放定址法

#所謂的開放定址法就是一旦發生了衝突，就去尋找下一個空的雜湊位址，只要散列表夠大，空的雜湊地址總是能找到，並將記錄存入。

公式：f(key)=(f(key) di)%m(di=1,2,3….m-1)

比如說，關鍵字集合為{ 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，表長為12。雜湊函數f(key) = key mod 12。 當計算前5個數{12, 67, 56, 16, 25}時，都是沒有衝突的雜湊位址，直接存入；計算key = 37時，發現f(37) = 1，此時就與25所在的位置衝突。於是應用上面的公式f(37) = (f(37) 1) mod 12 =2,。於是將37存入下標為2的位置。接下來22,29,15,47都沒有衝突，正常的存入。到了48，計算得到f(48) = 0，與12所在的0位置衝突了，不要緊，我們f(48) = (f(48) 1） mod 12 = 1，此時又與25所在的位置衝突。於是f(48) = (f(48) 2) mod 12 = 2，還是衝突......一直到f(48) = (f(48) 6） mod 12 = 6時，才有空位，如下表所示。 ##3# 4567891011 關鍵字1267

		序號	0	1	2
			25			16				56

#########

NO.2再雜湊法

對於散列表來說，可以事先準備多個雜湊函數。

公式：fi(key)=RHi(key)(i=1,2,3…,k)

這裡RHi 就是不同的雜湊函數，可以把除留餘數、折疊、平方取中全部用上。每當發生雜湊位址衝突時，就換一個雜湊函數計算。

這種方法能夠使得關鍵字不產生聚集，但相應地也增加了計算的時間。

NO.3鏈結位址法（拉鍊法）

將所有關鍵字為同義詞的記錄儲存在一個單鍊錶中，稱這種表為同義詞子表，在散列表中只儲存所有同義詞子表前面的指標。對於關鍵字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，用前面同樣的12為餘數，進行除留餘數法，可以得到下圖結構。

NO.4建立公共溢出區

這個方法是當你時重新給你找個位址，為所有衝突的關鍵字建立一個公共的溢出區來存放。

就前面的例子而言，共有三個關鍵字37、48、34與先前的關鍵字位置有衝突，那就將它們儲存到溢出表中。如下圖所示。

在尋找時，對給定值透過雜湊函數計算出雜湊位址後，先與基本表的對應位置進行比對，如果相等，則尋找成功；如果不相等，則到溢出表中進行順序查找。如果相對於基本表而言，有衝突的資料很少的情況下，公共溢出區的結構對查找效能來說還是非常高的。

【推薦課程：C 相關課程】

#

以上是資料結構中散列表（雜湊表）經典之衝突處理的詳細內容。更多資訊請關注PHP中文網其他相關文章！