解決Hash（哈希）沖突的四種方案

參考&鳴謝

解決哈希沖突必須知道的幾種方法 小僵魚

你還應該知道的哈希沖突解決策略 vivo互聯網技術

解決哈希沖突的三種方法 kaleidoscopic

每日一題(哈希表及哈希沖突解決辦法) 和笙

文章目錄

• 解決Hash（哈希）沖突的四種方案
• • 一、Hash概述
  • 二、開放尋址法
  • • 線性探查
    • 二次探查
    • 偽隨機探測
  • 三、鏈地址法（拉鏈法）
  • 四、再哈希法
  • 五、公共溢出區法

一、Hash概述

哈希是一種通過對數據進行壓縮, 從而提高效率的一種解決方法，但由于哈希函數有限，數據增大等緣故，哈希沖突成為數據有效壓縮的一個難題。本文主要介紹哈希沖突、解決方案，以及各種哈希沖突的解決策略上的優缺點。

哈希沖突即不同key值產生相同的地址，即發生了hash沖突。一般來說，哈希沖突是無法避免的，所以就有了解決方案。

常見的解決Hash沖突的方案有開放尋址法、鏈地址法和再哈希法。

---

二、開放尋址法

原理是當發生hash沖突時，會以當前地址為基準，然后根據尋址方法（探查尋址），去尋找下一次地址。若依舊發生沖突，則繼續尋址，直到找到一個空的位置為止。 通用的散列函數形式為：

Hi=（H（key）+di）% m （i=1，2，…，n）

其中H（key）為哈希函數，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。

線性探查

順序查找表的下一個單元，直到找到一個空單元或查遍全表。

即當hash值為3沖突時(假設此時hash表長度為11)，利用線性探查的過程為：

H1 = (3+1)%11 = 4，此時若4依舊沖突，則再hash，即

H2 = (3+2)%11 = 5 … 通過這種線性增長增量系列，直到找到空的位置為止。

二次探查

這種方法的特點是，當哈希沖突時，在表的左右進行跳躍探測，比較靈活。

此時di = 1^2, -1^2, 2^2, -2^2 …

假設當hash值為3沖突時(假設此時hash表長度為11)，利用二次探查的過程為：

H1 = (3+1^2)%11 = 4,此時若4依舊沖突，則再hash,即

H2 = (3+(-1)^2)%11 = 2 …

通過該方法直到找到空位置為止。

偽隨機探測

這種方法即是產生一些隨機系列值，并給定隨機數作為起點。

假設當hash值為3沖突時(假設此時hash表長度為11)，利用偽隨機探測的過程為：

假設產生的隨機系列為2，5，9 …，則

H1 = (3+2)%11 = 5

H2 = (3+5)%11 = 8

通過該方法直到找到空位置為止。

---

三、鏈地址法（拉鏈法）

HashMap，HashSet其實都是采用的拉鏈法來解決哈希沖突的，就是在每個位桶實現的時候，我們采用鏈表（jdk1.8之后采用鏈表+紅黑樹）的數據結構來去存取發生哈希沖突的輸入域的關鍵字（也就是被哈希函數映射到同一個位桶上的關鍵字）。首先來看使用拉鏈法解決哈希沖突的幾個操作：

• 插入操作：在發生哈希沖突的時候，我們輸入域的關鍵字去映射到位桶（實際上是實現位桶的這個數據結構，鏈表或者紅黑樹）中去的時候，我們先檢查帶插入元素x是否出現在表中，很明顯，這個查找所用的次數不會超過裝載因子（n/m : n為輸入域的關鍵字個數，m為位桶的數目），它是個常數，所以插入操作的最壞時間復雜度為O(1)的。
• 查詢操作：和插入操作一樣，在發生哈希沖突的時候，我們去檢索的時間復雜度不會超過裝載因子，也就是檢索數據的時間復雜度也是O(1)的
• 刪除操作：如果在拉鏈法中我們想要使用鏈表這種數據結構來實現位桶，在刪除一個元素x的時候，需要更改x的前驅元素的next指針的屬性，把x從鏈表中刪除。這個操作的時間復雜度也是O(1)的。

與開放定址法相比，拉鏈法有如下幾個優點：

①拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；

②由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；

③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；

④在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。

拉鏈法的缺點

指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

---

四、再哈希法

fi=(f(key)+i*g(key)) % m (i=1，2，……，m-1)

其中，f(key) 和 g(key) 是兩個不同的哈希函數，m為哈希表的長度

步驟：

雙哈希函數探測法，先用第一個函數 f(key) 對關鍵碼計算哈希地址，一旦產生地址沖突，再用第二個函數 g(key) 確定移動的步長因子，最后通過步長因子序列由探測函數尋找空的哈希地址。

比如，f(key)=a 時產生地址沖突，就計算g(key)=b，則探測的地址序列為 f1=(a+b) mod m，f2=(a+2b) mod m，……，fm-1=(a+(m-1)b) % m。

缺點：

每次沖突都要重新散列，計算時間增加。

---

五、公共溢出區法

即設立兩個表：基礎表和溢出表。將所有關鍵字通過哈希函數計算出相應的地址。然后將未發生沖突的關鍵字放入相應的基礎表中，一旦發生沖突，就將其依次放入溢出表中即可。

在查找時，先用給定值通過哈希函數計算出相應的散列地址后，首先與基本表的相應位置進行比較，如果不相等，再到溢出表中順序查找。

總結

以上是生活随笔為你收集整理的解决Hash（哈希表）冲突的四种方案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。