哈希沖突解決

在實際應用中，無論如何構造哈希函數，沖突是無法完全避免的。

1 開放位址法 

這個方法的基本思想是：當發生位址沖突時，按照某種方法繼續探測哈希表中的其他存儲單元，直到找到空位置為止。這個過程可用下式描述： 

H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1)) 

其中： H ( key ) 為關鍵字 key 的直接哈希位址， m 為哈希表的長度， di 為每次再探測時的位址增量。 

采用這種方法時，首先計算出元素的直接哈希位址 H ( key ) ，如果該存儲單元已被其他元素占用，則繼續檢視位址為 H ( key ) + d 2 的存儲單元，如此重複直至找到某個存儲單元為空時，将關鍵字為 key 的資料元素存放到該單元。 

增量 d 可以有不同的取法，并根據其取法有不同的稱呼： 

（ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 線性探測再散列； 

（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探測再散列； 

（ 3 ） d i ＝ 僞随機序列 僞随機再散列； 

例1設有哈希函數 H ( key ) = key mod 7 ，哈希表的位址空間為 0 ～ 6 ，對關鍵字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）按線性探測再散列和二次探測再散列的方法分别構造哈希表。 

解：

（ 1 ）線性探測再散列： 

32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ； 

55 ％ 7 = 6 發生沖突，下一個存儲位址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然發生沖突，再下一個存儲位址：（ 6 ＋ 2 ）％ 7 ＝ 1 未發生沖突，可以存入。 

22 ％ 7 ＝ 1 發生沖突，下一個存儲位址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未發生沖突； 

38 ％ 7 ＝ 3 ； 

21 ％ 7 ＝ 0 發生沖突，按照上面方法繼續探測直至空間 5 ，不發生沖突，所得到的哈希表對應存儲位置： 

下标： 0 1 2 3 4 5 6 

49 55 22 38 32 21 13 

（ 2 ）二次探測再散列： 

下标： 0 1 2 3 4 5 6 

49 22 21 38 32 55 13 

   注意：對于利用開放位址法處理沖突所産生的哈希表中删除一個元素時需要謹慎，不能直接地删除，因為這樣将會截斷其他具有相同哈希位址的元素的查找位址，是以，通常采用設定一個特殊的标志以示該元素已被删除。 

2 鍊位址法 

鍊位址法解決沖突的做法是：如果哈希表空間為 0 ～ m - 1 ，設定一個由 m 個指針分量組成的一維數組 ST[ m ], 凡哈希位址為 i 的資料元素都插入到頭指針為 ST[ i ] 的連結清單中。這種方法有點近似于鄰接表的基本思想，且這種方法适合于沖突比較嚴重的情況。 

 例 2 設有 8 個元素 { a,b,c,d,e,f,g,h } ，采用某種哈希函數得到的位址分别為： {0 ， 2 ， 4 ， 1 ， 0 ， 8 ， 7 ， 2} ，當哈希表長度為 10 時，采用鍊位址法解決沖突的哈希表如下圖所示。