數據結構中散列表沖突的處理方式

這篇文章給大家分享的是有關數據結構中散列表沖突的處理方式的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。

   散列是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)，建立了關鍵字與存儲位置的相互對應關系，這種關系 f 稱為散列函數（哈希函數）。

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

1. 散列函數是否均勻；

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時，才有空位，如下表所示。

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與之前的關鍵字位置有沖突，那就將它們存儲到溢出表中。如下圖所示。

在查找時，對給定值通過散列函數計算出散列地址后，先與基本表的相應位置進行比對，如果相等，則查找成功；如果不相等，則到溢出表中進行順序查找。如果相對于基本表而言，有沖突的數據很少的情況下，公共溢出區的結構對查找性能來說還是非常高的。

感謝各位的閱讀！關于數據結構中散列表沖突的處理方式就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！