哈希表沖突處理方法淺析

葉軍偉

(麗江師范高等專科學校，云南 麗江 674100)

0 引言

在哈希表中，哈希函數的設置是非常靈活的，只要能使任一關鍵字由此所得的哈希地址都分布在哈希表允許的范圍內就可以了。因此常常會出現不同的關鍵字值對應到同一個存儲地址的現象，這就叫沖突。即關鍵字key1≠key2，但H(key1）=H(key2）。

適當的選擇分布均勻的哈希函數能有效地減少沖突的發生，但是不能不免沖突。發生沖突后，必須解決，也即必須尋找下一個可用的地址。因此哈希表的建立通常為如下步驟：第一步，取出一個數據元素的關鍵字key，根據哈希函數計算其在哈希表中的存儲地址D，若地址為D 的存儲空間還沒有被占用，則將該數據元素存入,否則發生沖突，執行下一步；第二步，根據規定的沖突處理方法，計算關鍵字為key 的數據元素的下一個存儲地址，若該地址的存儲空間沒有被占用，則存入，否則繼續執行第二步，直到找出一個空閑的存儲空間為止。由此可見，如何處理沖突是哈希表不可缺少的部分。

1 開放定址法

這是應用最為廣泛的一種沖突處理方法。其公式描述為：Hi=（H(key)+di) MOD L i=1,2,…,k(k<=L-1)

其中：H(key)為哈希函數，L 為哈希表的表長，di為增量序列。

根據增量序列取值方法的有三種：（1）線性探測再散列di=1,2,3,…,m-1；（2）二次探測再散列di=12，-12，22，-22，32，...，k2，(k<=L/2)；（3）偽隨機探測再散列di=偽隨機數序列。

用線性探測再散列處理沖突可以保證做到，只要哈希表未滿，總能找到不發生沖突的地址，但是容易發生二次聚集的情況，即在處理同義詞的沖突過程中又添加了非同義詞的沖突，效率不高。比如當哈希表中k，k+1，k+2 位置上已存放有數據時，下一個哈希地址為k，k+1，k+2 和k+3 的數據都將填入k+3 的位置，這樣原本不沖突的哈希地址在經過沖突處理后，反而發生沖突，這種現象對查找不利。

二次探測再散列能夠減少二次聚集的情況，提高效率，但是只能在哈希表的長度為4n+3（n 為整數）的素數時才能使用。隨機探測再散列，則取決于偽隨機數序列。

2 再哈希法

Hi=RHi(key) i=1，2，...，k

RHi均是不同的哈希函數，在同義詞發生地址沖突時用另一個哈希函數產生新的地址，直到不再發生沖突為止。再哈希法不易產生二次聚集，但是增加了計算的時間和哈希函數的數量，而且不能保證在哈希表未滿時，總能找到不發生沖突的地址。

除了對同一關鍵字用不同的哈希函數進行再哈希外，還可以用同一哈希函數對次要關鍵字進行計算得到新的哈希地址。即：Hi=RH(keyi) i=1，2，...，k。

比如對中文詞典的進行哈希查找，關鍵字為一個四字成語，可以把成語的第一個字當做關鍵字key1，計算出哈希地址，若發生沖突，則把第二個字當做key2，計算新的哈希地址，以次類推，還可以計算key3和key4。

3 鏈地址法

將所有關鍵字為同義詞的記錄存儲在同一個線性鏈表中。可以在哈希函數產生的哈希地址區間上設計一個指針數組，其每個元素的初始狀態都是空指針，作為一個單鏈表的頭指針。凡是哈希地址為i 的記錄都插入到第i 個單鏈表中。在單鏈表中的插入位置可以在表頭或表尾，也可以按一定的順序插入到單鏈表的中間，以保持同義詞在同一線性鏈表中按關鍵字有序。采用鏈地址法能用有限的哈希地址存放任意多的記錄，但是增加了單鏈表的查找操作。

4 建立一個公共溢出區

建立一個基本表，基本表的大小等于哈希地址的個數，另外再建立一個溢出表。所有哈希地址的第一個記錄存放在基本表中，其他關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數得到的哈希地址是什么，一旦發生沖突，都存放在溢出表中。

建立基本表需要事先能夠知道哈希地址可能的個數，而溢出表中的數據則不能太多，不然難以高效地查找溢出表。也就是說，所有需要存放的記錄的關鍵字，不能有太多的沖突。

5 結束語

在哈希表上進行查找的過程和哈希造表的過程基本一致。對于給定關鍵字，根據造表時設定的哈希函數求得哈希地址，若表中此位置上沒有記錄，則說明該哈希表中無此數據，查找結束。若有記錄，就比較關鍵字，若相等，則查找成功；若不相等，則根據造表時設定的沖突處理方法查找下一個地址。因此要提高查找的效率，就要盡量減少發生沖突的情況。

由于哈希表查找的復雜度只與哈希表的裝填充因子有關，隨著硬件技術的不斷發展，內存容量不斷提高，可以通過簡單的降低哈希表填充因子，增大哈希表的長度來降低系統復雜度，減少沖突發生的概率。

［1］張科.多次Hash 快速分詞算法[J].計算機工程與設計,2007(4).

［2］嚴蔚敏,吳偉民.數據結構(C 語言版)[M].北京:清華大學出版社,2007.

［3］李志敏,鄭世慧,楊義先.可用于哈希函數的安全迭代結構[J].北京郵電大學學報,2008(12).