基于哈希表查找方法的優勢及其算法的改進

摘要：當前是一個信息爆炸的時代，海量的信息充斥了人們生活的各個方面，所以從大量的數據中快速的找到所需信息已經成為一個熱門的課題。一般的搜索方法，在搜索時需進行關鍵字的比較。這一類建立在比較的基礎上的搜索方法，其效率依賴于搜索過程中所進行的比較次數。而通過使用哈希表人們可以不經任何比較，一次存取便能得到所需的信息，從而大大提高了搜索的效率。然而，建立哈希表不可能沒有沖突，解決沖突則會產生諸如堆積、二次聚集等現象，降低了查找效率。文中通過舉例闡明了該過程，并提出了有效的解決方法。

關鍵詞:哈希表沖突查找關鍵字

1 一般查找方法和哈希表的比較

最容易理解的莫過于按照順序查找，它的查找過程為:

從表中的第一個記錄開始，逐條地進行記錄的關鍵字和給定值的比較，這時可能會發生兩種情況，第一種情況是找到關鍵字和給定值相等的記錄，查找成功，第二種情況是找遍所有記錄卻沒有找到滿足條件的記錄，查找失敗。當表中存儲的數據量非常多的時候，該方法效率就會變得很低，最糟糕的情況就是可能要把所有的數據都讀一遍才找到指定記錄。由此可見順序查找方法效率不高。而其他查找方法如折半查找法，也稱為二分查找法，它充分利用了元素間的次序關系，它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果xa[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的思想易于理解，但是要寫一個正確的二分搜索算法也不是一件簡單的事，甚至Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索算法。其問題的關鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定。

綜上所述，查找的效率依賴于查找過程中所進行的比較次數。比較的次數越多，查找時間就越長。理想的情況是希望不經任何比較，一次存取便能得到所查找的記錄。而這個理想的情況可以用哈希表和它的算法來實現。

2 哈希表的概念

哈希表（Hash table，也叫散列表），是根據關鍵碼值而直接進行訪問的數據結構。它是通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做哈希函數，存放記錄的數組叫做哈希表。哈希表的最大特點，就是數據存儲位置和數據記錄的內容相關，存在著一個函數換算關系：

Offset=Hash (K)

其中，Offset為數據存儲的偏移量，Hash（K）為哈希函數(Hash Function)，K為關鍵字，若表中存在關鍵字和K相等的記錄，則必定在Hash(K)的存儲位置上。哈希函數，是計算機科學中一個重要的課題。其實，哈希概念并沒有一個嚴格的定義。一般說來，哈希函數滿足以下的條件：

①對輸入值運算，得到一個固定長度的摘要(Hash value)；

②散列函數的輸出值盡量接近均勻分布；

③k的微小變化可以使Hash(k)發生非常大的變化，即所謂“雪崩效應”；

原來，這是為了減少“哈希沖突”（Hash collision），也就是兩個不同輸入產生了相同輸出值的情況。根據抽屜原理，Hash算法不可能沒有沖突(collision)，但是，由于沖突會造成一些問題，可能會影響到應用Hash函數的某些算法的效率，所以，我們需要盡量避免之。這樣，對Hash算法的選擇，就是很重要的了。

3 除留余數法建立哈希表

構造哈希函數的目標是使哈希地址盡可能均勻地分布在連續的內存單元地址上，以減少沖突發生的可能性，同時使計算盡可能簡單以達到盡可能高的時間效率。根據關鍵字的結構和分布不同，可構造出與之適應的各不相同的哈希函數。

除留余數法是采用取模運算（MOD），把關鍵字除以某個不大于哈希表表長的整數得到的余數作為哈希地址。不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模。哈希函數的形式為：

Hash(k)=k MOD p(p≤m，m為哈希表表長)

而除留余數法的關鍵就是選好p，一般p取素數或m。若p選的不好，容易產生同義詞，即發生沖突。沖突會造成一些問題，可能會影響到應用Hash函數的某些算法的效率，所以好的p值可以使得記錄集合中的每個關鍵字通過該數轉換后映射到哈希表范圍內任意地址上的概率相等，從而盡可能減少發生沖突的可能性。但是，根據抽屜原理，Hash算法不可能沒有沖突。

沖突解決技術可分為兩大類：開散列法（又稱為鏈地址法）和閉散列法（又稱為開放地址法）。哈希表是用數組實現的一片連續的地址空間，兩種沖突解決技術的區別在于發生沖突的元素是存儲在這片數組的空間之外還是空間之內。

下面以閉散列法中的線性探測法為例說明，線性探測法的基本思想是：當發生沖突時，從沖突位置的下一個單元順序尋找，只要找到一個空位，就把元素放入此空位中。可用如下公式表示：

Hi=(Hash(k) + i)MODm 公式(1)

其中Hash(k)為哈希函數；m為哈希表長；i為增量。

一組關鍵字為（12，19，23，28，39，51，56，76，84），哈希表長m=13，哈希函數為：Hash(k)=k MOD11，并使用線性探測法處理沖突，可得表如下：

根據除留余數法的計算規則，12，19，28，76這4個關鍵字是直接添加到第1，8，6，10這4個位置，而其他的關鍵字則都要經過線性探測法才能確定其填充的位置，例如關鍵字39，由哈希函數Hask（39）=39 MOD 11=6，可知，39應該填充到位置6，可是位置6已經被關鍵字19占據，所以必須進行再次計算。根據公式(1)，

H1=(Hash(39)+1) MOD 13=7，即關鍵字39對應位置為7，但是，這樣就出現一個問題，根據哈希函數計算，Hask（51）=51 MOD 11=7，可以看出根據除留余數法規則，原本屬于關鍵字51的位置7卻被關鍵字39占據了，這就導致57也必須進行線性探測法尋找自己的位置：

H1=(Hash(51)+1) MOD 13=8 （沖突，位置8已被關鍵字19占據）

H2=(Hash(51)+2) MOD 13=9 （成功，位置9為空，關鍵字51填充到位置9）

每個元素經哈希函數計算出來的地址稱為基地址，這種不同基地址的元素爭奪同一個單元的現象叫做二次聚集。二次聚集實際上是在處理同義詞之間的沖突時引發的非同義詞的沖突。顯然，這種現象對查找不利。線性探測很容易出現二次聚集，小的聚集能匯合成大的聚集，最終導致很長的探測序列，從而降低哈希表的運算效率。

4 改進的除留余數法建立哈希表

使用哈希表的主要目的是為了加快查找速度，提高查找效率，任何導致查找速度和效率降低的問題都是我們盡力去解決的。由上面的論述可知二次聚集的產生，是由在建立哈希表時采取了遇到沖突立刻解決的方法引起的。我們針對這一特點，可以采用以下的策略:在建立哈希表時先依次填入所有不產生沖突的元素，在填入的過程中，將遇到沖突的元素暫時放入一臨時表中，并且記下它發生沖突位置，等全部數據處理完后，再去專門解決產生沖突元素(暫存入隊列中的元素) 。

例如，一組關鍵字為（12，19，23，28，39，51，56，76，84），哈希表長m=13，哈希函數為：Hash(k)=k MOD 11。下面分析一下它的存儲過程:Hash(12)=1，位置1為空，將12存入；Hash(19)=8，位置8為空，將19存入；Hash(23)= 1，位置1不為空，將23存入臨時表；Hash(28)=6，位置6為空，將28存入；Hash(39)=6，位置6不為空，將39存入臨時表；Hash(51)=7，位置7為空，將51存入；Hash( 56)=1，位置1不為空，將56入臨時表；Hash(76)=10，位置10為空，將76存入；Hash(84)=7，位置7不為空，將84入臨時隊列。這時建表如下:

隊列中的每個元素包括兩項：數據元素和其產生沖突的位置。要解決沖突元素問題，將臨時表中的元素填入哈希表，處理過程為:

取隊列中第一個哈希地址上沖突的數據元素得Hash(23)=1，尋找下一個空的哈希地址:

H1=(Hash(23)+1) mod11=2地址2為空，將23存入。取隊列中第二個哈希地址上沖突的數據元素得Hash(39)=6，尋找下一個空的哈希地址:

H1=(Hash(39)+1) mod11=7位置7不為空

H2=(Hash(39)+2) mod11=8位置8不為空

H3=(Hash(39)+3) mod11=9位置9為空，將39存入。取隊列中第三個哈希地址上沖突的數據元素得Hash(56)=1，尋找下一個空的哈希地址:

H1=(Hash(56)+1) mod11=2位置2不為空

H2=(Hash(56)+2) mod11=3位置3為空，將56存入。

取隊列中第三個哈希地址上沖突的數據元素得Hash(84)=7，尋找下一個空的哈希地址:

H1=(Hash(84)+1) mod11=7位置7不為空

H2=(Hash(84)+2) mod11=8位置8不為空

H3=(Hash(84)+3) mod11=9位置9不為空

H4=(Hash(84)+4) mod11=10位置10不為空

H1=(Hash(84)+5) mod11=11位置11為空，將84存入

最終結果如下:

5 結論

改進方法之后，避免了非同義詞搶占同一個位置，不會再帶來新的沖突，所以能有效的減少沖突次數，從而大大的提高了查找效率。而且，改進方法之后，在讀取數據時不需面對非同義詞的沖突，所以絕大部分數據不需要進行比較便可直接獲得查找結果，這就更符合使用哈希表的初衷。

參考文獻:

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].4版.北京:清華大學出版社，2007.

[2]Weiss M A.數據結構與算法分析[M].北京:機械工業出版社，2004.

[3]王川，王歲花.地址哈希排序算法的設計與實現[J].平原大學學報，2004，21(5):61-63.