方瑞英　陳桂英

摘要：哈希表的理想情況是無需比較一次存取便能找到所查的記錄，但是在實際應(yīng)用中，哈希表通常存在沖突的情況，這就需要反復(fù)查找處理沖突。一般的搜索方法，在搜索時需進行關(guān)鍵字的比較。這一類建立在比較基礎(chǔ)上的搜索方法，其效率依賴于搜索過程中所進行的比較次數(shù)。而通過使用哈希表人們可以不經(jīng)任何比較，一次存取便能得到所需的信息，從而大大提高了搜索的效率。然而，建立哈希表不可能沒有沖突，解決沖突則會產(chǎn)生諸如堆積、二次聚集等現(xiàn)象，降低了查找效率。文中通過舉例闡明了線性探測再散列構(gòu)造哈希表的方法，并詳細地分析了查找成功時和查找失敗時的ASL。

關(guān)鍵詞：線性探測再散列；哈希表；ASL

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2015）015-0152-02

Abstract： The ideal condition of the hash table is to find the record without comparing an access. But in practice， the hash table usually has a conflict situation and needs to repeatedly look for conflict. General search methods need to carry out the comparison of key words. The efficiency of the search method based on the comparison of this class depends on the number of times in the search process. But by using a hash table， people can get the required information without any comparison and greatly improve the efficiency of the search. However， building a hash table cannot be without conflict. To resolve conflicts， such as the accumulation of two times， and other phenomena， reduces the search efficiency. In this paper， the method of constructing a hash table of the linear detection and hash table is illustrated by an example and the efficiency of the success and the failure is analyzed in detail.

Key words： Linear detection to hash；Hash Table； ASL

哈希表作為一種根據(jù)關(guān)鍵字直接進行訪問的數(shù)據(jù)結(jié)構(gòu)被廣泛應(yīng)用于各種查找中[1]。然而，很難找到一個哈希函數(shù)能保證對任意不同的關(guān)鍵字都產(chǎn)生不同的哈希值。通常用的處理沖突的方法有： 鏈地址法，開放定址法，再哈希法，以及建立一個公共溢出區(qū)。本文討論基于線性探測再散列法如何構(gòu)造哈希表及其查找效率的分析。在哈希表中，哈希函數(shù)的設(shè)置是非常靈活的，只要能使任一關(guān)鍵字由此所得的哈希地址都分布在哈希表允許的范圍內(nèi)就可以了。因此常常會出現(xiàn)不同的關(guān)鍵字值對應(yīng)到同一個存儲地址的現(xiàn)象，這就叫沖突。即關(guān)鍵字key1≠key2，但H（key1）= H（key2）。適當(dāng)?shù)倪x擇分布均勻的哈希函數(shù)能有效地減少沖突的發(fā)生，但是不能不免沖突。發(fā)生沖突后，必須解決，也即必須尋找下一個可用的地址。因此哈希表的建立通常為如下步驟：第一步，取出一個數(shù)據(jù)元素的關(guān)鍵字key，根據(jù)哈希函數(shù)計算其在哈希表中的存儲地址add，若地址為add 的存儲空間還沒有被占用，則將該數(shù)據(jù)元素存入，否則發(fā)生沖突，執(zhí)行下一步；第二步，根據(jù)規(guī)定的沖突處理方法，計算關(guān)鍵字為key 的數(shù)據(jù)元素的下一個存儲地址，若該地址的存儲空間沒有被占用，則存入，否則繼續(xù)執(zhí)行第二步，直到找出一個空閑的存儲空間為止。由此可見，如何處理沖突是哈希表不可缺少的部分。

1 線性探測再散列法構(gòu)造哈希表

開放定址法基本思想：當(dāng)關(guān)鍵碼key的哈希地址H0 = H（key）出現(xiàn)沖突時，以H0為基礎(chǔ)，產(chǎn)生另一個哈希地址H1，如果H1仍然沖突，再以H0 為基礎(chǔ)，產(chǎn)生另一個哈希地址H2，…，直到找出一個不沖突的哈希地址Hi，將相應(yīng)元素存入其中。這種方法有一個通用的再散列函數(shù)形式： Hi=（ H（key）+di） mod m，i=1，2，…，m-1 ，其中H （key） 哈希函數(shù)，m為表長，di稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有四種：線性探測再散列、二次探測再散列、偽隨機探測再散列和雙散列法。如果di增量序列取i時，稱線性探測再散列。

例如，已知散列表的地址區(qū)間為0～10，散列函數(shù)為H（k）=k MOD 11，采用線性探測再散列法處理沖突，將關(guān)鍵字序列20，30，70，15，8，12，18，63，19依次存儲到散列表中。比如12、70、18、30、20這五個關(guān)鍵字探測一次即可存入空閑單元，而關(guān)鍵字8探測三次存入空閑單元，最后可以得到如下哈希表，見表1。

散列地址不同的結(jié)點爭奪同一個后繼散列地址的現(xiàn)象稱為堆積（Clustering）。比如63和19，63 本來位置是8，直到探測了4次才找到合適位置0，19本來位置也是8，直到探測了6次才找到合適位置2。這將造成不是同義詞的結(jié)點也處在同一個探測序列中，從而增加了探測序列長度，即增加了查找時間。 若散列函數(shù)不好、或裝填因子a 過大，都會使堆積現(xiàn)象加劇。

2 線性探測再散列法查找效率分析

在哈希表上進行查找的過程和哈希造表的過程基本一致。給定K值，根據(jù)造表時設(shè)定的哈希函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找失??；否則比較關(guān)鍵字，若和給定值相等，則查找成功；否則根據(jù)造表時設(shè)定的處理沖突的方法找“下一個地址”，直至哈希表中某個位置為“空”或者表中所填記錄的關(guān)鍵字等于給定值時為止。

查找成功的ASL指查找到哈希表中已有元素的平均探測次數(shù)，它是找到表中各個已有元素的探測次數(shù)的平均值。比如，給定值key=63的查找過程為：首先求得哈希地址H（63）=8，因為H.elem[8]不空且H.elem[8].key≠63，則找到第一次沖突處理后的地址H1=（8+1） MOD 11=9，而H.elem[9]不空且H.elem[9].key≠63，則找第二次沖突處理后的地址H2=（8+2） MOD 11=10， 而H.elem[10]不空且H.elem[10].key≠63，則找第三次沖突處理后的地址H3=（8+3） MOD 11=0， 而H.elem[0]不空且H.elem[0].key=63，則查找成功，查找次數(shù)等于構(gòu)造哈希表時探測次數(shù)4。依此類推，可得等概率情況下查找成功的ASL為：

接下來討論失敗的情況， 查找失敗的ASL是指在表中查找不到待查的元素，但找到插入位置的平均探測次數(shù)，它是表中所有可能散列的位置上要插入新元素時為找到空位置的探測次數(shù)的平均值。

計算失敗時n是散列函數(shù)能夠計算出的散列地址數(shù)，例如，若m=16，使用除留余數(shù)法，散列函數(shù)可以是H（x）=x%13，除數(shù)取不大于m但接近m的質(zhì)數(shù)，此時n=13而不是16，sj是一旦在第j位置插入新元素（表中原來沒有），要找到空閑位置的探測次數(shù)，也是它若存放進去，將來找到它的比較次數(shù)。也就是說，計算查找失敗的次數(shù)就直接找關(guān)鍵字到第一個地址上關(guān)鍵字為空的距離即可， 但根據(jù)哈希函數(shù)，因此初始只可能在0～6的位置。等概率情況下，查找0～6位置查找失敗的查找次數(shù)為：看地址0，到第一個關(guān)鍵字為空的地址3的距離為4，因此查找失敗的次數(shù)為4；地址1， 到第一個關(guān)鍵字為空的地址3的距離為3，因此查找失敗的次數(shù)為3；地址2， 到第一個關(guān)鍵字為空的地址3的距離為2，因此查找失敗的次數(shù)為2；地址3，到第一個關(guān)鍵字為空的地址3的距離為1，因此查找失敗的次數(shù)為1；地址4，到第一個關(guān)鍵字為空的地址6的距離為3，因此查找失敗的次數(shù)為3；地址5，到第一個關(guān)鍵字為空的地址6的距離為2，因此查找失敗的次數(shù)為2；地址6，到第一個關(guān)鍵字為空的地址6的距離為1，因此查找失敗的次數(shù)為1；地址7，到第一個關(guān)鍵字為空的地址3（因為初始只可能在0～10之間，因此循環(huán)回去）的距離為8，因此查找失敗的次數(shù)為8，依此類推，因此查找失敗的ASL為：

3 結(jié)束語

線性探測法的優(yōu)點：只要哈希表未被填滿，總能找到一個空地址單元存放有沖突的元素；線性探測法的缺點：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞……因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測法或偽隨機探測法，以改善“堆積”問題。

參考文獻：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1998.

[2] 張朝霞，劉耀軍.有效的哈希沖突解決辦法[J]. 計算機應(yīng)用， 2010（11）.

[3]王秋芬，邵艷玲. 一種新的基于哈希函數(shù)的排序算法[J].計算機與現(xiàn)代化，2010，9（10）.

[4]馬如林，蔣華，張慶霞.一種哈希表快速查找的改進方法[J]. 計算機工程與科學(xué)， 2008（9）.

[5] 葉軍偉.哈希表沖突處理方法淺析[J]. 科技視界， 2014（06）.

[6] 趙宇. 基于哈希表查找方法的優(yōu)勢及其算法的改進[J]. 中小企業(yè)管理與科技（下旬刊）， 2012（3）.

[7] 阮群生，李豫穎，劉錫鈴.基于哈希表與線性表建立FP-Tree的改進算法[J]. 長江大學(xué)學(xué)報（自然科學(xué)版）理工卷， 2010（1）.

[8] 徐士良.實用數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2006.