Hash演算法解決衝突的方法

Hash演算法解決衝突的方法一般有以下幾種常用的解決方法

1， 開放定址法：

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

公式為：fi(key) = (f(key)+di) MOD m (di=1,2,3,……,m-1)

※ 用開放定址法解決衝突的做法是：當衝突發生時，使用某種探測技術在散列表中形成一個探測序列。沿此序列逐個單元地查找，直到找到給定的關鍵字，或者

碰到一個開放的地址（即該地址單元為空）為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。查找時探測到開放的地址則表明表

中無待查的關鍵字，即查找失敗。

比如說，我們的關鍵字集合為{12,67,56,16,25,37,22,29,15,47,48,34},表長為12。 我們用散列函數f(key) = key mod l2

當計算前S個數{12,67,56,16,25}時，都是沒有衝突的散列地址，直接存入：

計算key = 37時，發現f(37) = 1，此時就與25所在的位置衝突。

於是我們應用上面的公式f(37) = (f(37)+1) mod 12 = 2。於是將37存入下標為2的位置：

2， 再哈希法：

再哈希法又叫雙哈希法，有多個不同的Hash函數，當發生衝突時，使用第二個，第三個，….，等哈希函數

計算地址，直到無衝突。雖然不易發生聚集，但是增加了計算時間。

3， 鏈地址法：

鏈地址法的基本思想是：每個哈希表節點都有一個next指針，多個哈希表節點可以用next指針構成一個單向鏈表，被分配到同一個索引上的多個節點可以用這個單向

鏈表連接起來，如：

鍵值對k2, v2與鍵值對k1, v1通過計算後的索引值都為2，這時及產生衝突，但是可以通道next指針將k2, k1所在的節點連接起來，這樣就解決了哈希的衝突問題

4， 建立公共溢出區：

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生衝突的元素，一律填入溢出表

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！