哈希表沖突處理方法淺析

葉軍偉

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

0 引言

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

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

1 開放定址法

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

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

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

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

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

2 再哈希法

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

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

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

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

3 鏈地址法

將所有關(guān)鍵字為同義詞的記錄存儲在同一個(gè)線性鏈表中?？梢栽诠：瘮?shù)產(chǎn)生的哈希地址區(qū)間上設(shè)計(jì)一個(gè)指針數(shù)組，其每個(gè)元素的初始狀態(tài)都是空指針，作為一個(gè)單鏈表的頭指針。凡是哈希地址為i 的記錄都插入到第i 個(gè)單鏈表中。在單鏈表中的插入位置可以在表頭或表尾，也可以按一定的順序插入到單鏈表的中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。采用鏈地址法能用有限的哈希地址存放任意多的記錄，但是增加了單鏈表的查找操作。

4 建立一個(gè)公共溢出區(qū)

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

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

5 結(jié)束語

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

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

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

［2］嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C 語言版)[M].北京:清華大學(xué)出版社,2007.

［3］李志敏,鄭世慧,楊義先.可用于哈希函數(shù)的安全迭代結(jié)構(gòu)[J].北京郵電大學(xué)學(xué)報(bào),2008(12).