java解決hash算法沖突

看了concurrenthashmap的實作, 使用的是拉鍊法.

雖然我們不希望發生沖突，但實際上發生沖突的可能性仍是存在的。當關鍵字值域遠大于哈希表的長度，而且事先并不知道關鍵字的具體取值時。沖突就難免會發 生。另外，當關鍵字的實際取值大于哈希表的長度時，而且表中已裝滿了記錄，如果插入一個新記錄，不僅發生沖突，而且還會發生溢出。是以，處理沖突和溢出是 哈希技術中的兩個重要問題。

1、開放定址法

    　用開放定址法解決沖突的做法是：當沖突發生時，使用某種探查(亦稱探測)技術在散清單中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定 的關鍵字，或者碰到一個開放的位址(即該位址單元為空)為止（若要插入，在探查到開放的位址，則可将待插入的新結點存人該位址單元）。查找時探查到開放的 位址則表明表中無待查的關鍵字，即查找失敗。

注意：

①用開放定址法建立散清單時，建表前須将表中所有單元(更嚴格地說，是指單元中存儲的關鍵字)置空。

②空單元的表示與具體的應用相關。

    　按照形成探查序列的方法不同，可将開放定址法區分為線性探查法、線性補償探測法、随機探測等。

（1）線性探查法(linear probing)

該方法的基本思想是：

    将散清單t[0..m-1]看成是一個循環向量，若初始探查的位址為d(即h(key)=d)，則最長的探查序列為：

        d，d+l，d+2，…，m-1，0，1，…，d-1

    　即:探查時從位址d開始，首先探查t[d]，然後依次探查t[d+1]，…，直到t[m-1]，此後又循環到t[0]，t[1]，…，直到探查到t[d-1]為止。

探查過程終止于三種情況：

    　(1)若目前探查的單元為空，則表示查找失敗（若是插入則将key寫入其中）；

    (2)若目前探查的單元中含有key，則查找成功，但對于插入意味着失敗；

    　(3)若探查到t[d-1]時仍未發現空單元也未找到key，則無論是查找還是插入均意味着失敗(此時表滿)。

利用開放位址法的一般形式，線性探查法的探查序列為：

        hi=(h(key)+i)％m 0≤i≤m-1 //即di=i

用線性探測法處理沖突，思路清晰，算法簡單，但存在下列缺點：

① 處理溢出需另程式設計式。一般可另外設立一個溢出表，專門用來存放上述哈希表中放不下的記錄。此溢出表最簡單的結構是順序表，查找方法可用順序查找。

② 按上述算法建立起來的哈希表，删除工作非常困難。假如要從哈希表 ht 中删除一個記錄，按理應将這個記錄所在位置置為空，但我們不能這樣做，而隻能标上已被删除的标記，否則，将會影響以後的查找。

③ 線性探測法很容易産生堆聚現象。所謂堆聚現象，就是存入哈希表的記錄在表中連成一片。按照線性探測法處理沖突，如果生成哈希位址的連續序列愈長 ( 即不同關鍵字值的哈希位址相鄰在一起愈長 ) ，則當新的記錄加入該表時，與這個序列發生沖突的可能性愈大。是以，哈希位址的較長連續序列比較短連續序列生長得快，這就意味着，一旦出現堆聚 ( 伴随着沖突 ) ，就将引起進一步的堆聚。

（2）線性補償探測法 

線性補償探測法的基本思想是：

将線性探測的步長從 1 改為 q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改為： j ＝ (j ＋ q) % m ，而且要求 q 與 m 是互質的，以便能探測到哈希表中的所有單元。

【例】 pdp-11 小型計算機中的彙程式設計式所用的符合表，就采用此方法來解決沖突，所用表長 m ＝ 1321 ，選用 q ＝ 25 。

（3）随機探測 

随機探測的基本思想是：

将線性探測的步長從常數改為随機數，即令： j ＝ (j ＋ rn) % m ，其中 rn 是一個随機數。在實際程式中應預先用随機數發生器産生一個随機序列，将此序列作為依次探測的步長。這樣就能使不同的關鍵字具有不同的探測次序，進而可以避 免或減少堆聚。基于與線性探測法相同的理由，線上性補償探測法和随機探測法中，删除一個記錄後也要打上删除标記。

2、拉鍊法

（1）拉鍊法解決沖突的方法

    　拉鍊法解決沖突的做法是：将所有關鍵字為同義詞的結點連結在同一個單連結清單中。若標明的散清單長度為m，則可将散清單定義為一個由m個頭指針組成的指針數 組t[0..m-1]。凡是散列位址為i的結點，均插入到以t[i]為頭指針的單連結清單中。t中各分量的初值均應為空指針。在拉鍊法中，裝填因子α可以大于 1，但一般均取α≤1。

【例】設有 m ＝ 5 ， h(k) ＝ k mod 5 ，關鍵字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外鍊位址法所建立的哈希表如下圖所示：

（2）拉鍊法的優點

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

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

②由于拉鍊法中各連結清單上的結點空間是動态申請的，故它更适合于造表前無法确定表長的情況；

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

④在用拉鍊法構造的散清單中，删除結點的操作易于實作。隻要簡單地删去連結清單上相應的結點即可。而對開放位址法構造的散清單，删除結點不能簡單地将被删結 點的空間置為空，否則将截斷在它之後填人散清單的同義詞結點的查找路徑。這是因為各種開放位址法中，空位址單元(即開放位址)都是查找失敗的條件。是以在 用開放位址法處理沖突的散清單上執行删除操作，隻能在被删結點上做删除标記，而不能真正删除結點。

（3）拉鍊法的缺點

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