哈希法又稱散列法、雜湊法以及關(guān)鍵字地址計算法等，相應(yīng)的表稱為哈希表。這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系f，使得p=f(k)，f稱為哈希函數(shù)。創(chuàng)建哈希表時，把關(guān)鍵字為k的元素直接存入地址為f(k)的單元；以后當查找關(guān)鍵字為k的元素時，再利用哈希函數(shù)計算出該元素的存儲位置p=f(k)，從而達到按關(guān)鍵字直接存取元素的目的。

   當關(guān)鍵字集合很大時，關(guān)鍵字值不同的元素可能會映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），這種現(xiàn)象稱為沖突，此時稱k1和k2為同義詞。實際中，沖突是不可避免的，只能通過改進哈希函數(shù)的性能來減少沖突。

綜上所述，哈希法主要包括以下兩方面的內(nèi)容：

 1）如何構(gòu)造哈希函數(shù)

 2）如何處理沖突。

8.4.1   哈希函數(shù)的構(gòu)造方法

    構(gòu)造哈希函數(shù)的原則是：①函數(shù)本身便于計算；②計算出來的地址分布均勻，即對任一關(guān)鍵字k，f(k) 對應(yīng)不同地址的概率相等，目的是盡可能減少沖突。

下面介紹構(gòu)造哈希函數(shù)常用的五種方法。

1． 數(shù)字分析法

      如果事先知道關(guān)鍵字集合，并且每個關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。例如，有80個記錄，關(guān)鍵字為8位十進制整數(shù)d₁d₂d₃…d₇d₈，如哈希表長取100，則哈希表的地址空間為：00~99。假設(shè)經(jīng)過分析，各關(guān)鍵字中 d₄和d₇的取值分布較均勻，則哈希函數(shù)為：h(key)=h(d₁d₂d₃…d₇d₈)=d₄d₇。例如，h(81346532)=43，h(81301367)=06。相反，假設(shè)經(jīng)過分析，各關(guān)鍵字中 d₁和d₈的取值分布極不均勻， d₁ 都等于5，d₈ 都等于2，此時，如果哈希函數(shù)為：h(key)=h(d₁d₂d₃…d₇d₈)=d₁d₈，則所有關(guān)鍵字的地址碼都是52，顯然不可取。

2． 平方取中法

當無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為：平方后中間幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。

例：我們把英文字母在字母表中的位置序號作為該英文字母的內(nèi)部編碼。例如K的內(nèi)部編碼為11，E的內(nèi)部編碼為05，Y的內(nèi)部編碼為25，A的內(nèi)部編碼為01, B的內(nèi)部編碼為02。由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為11052501，同理我們可以得到關(guān)鍵字“KYAB”、“AKEY”、“BKEY”的內(nèi)部編碼。之后對關(guān)鍵字進行平方運算后，取出第7到第9位作為該關(guān)鍵字哈希地址，如圖8.23所示。

圖8.23平方取中法求得的哈希地址

3． 分段疊加法

      這種方法是按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分（最后一部分可以較短），然后將這幾部分相加，舍棄最高進位后的結(jié)果就是該關(guān)鍵字的哈希地址。具體方法有折疊法與移位法。移位法是將分割后的每部分低位對齊相加，折疊法是從一端向另一端沿分割界來回折疊（奇數(shù)段為正序，偶數(shù)段為倒序），然后將各段相加。例如：key=12360324711202065,哈希表長度為1000，則應(yīng)把關(guān)鍵字分成3位一段，在此舍去最低的兩位65，分別進行移位疊加和折疊疊加，求得哈希地址為105和907，如圖8.24所示。

1   2   3                    1   2   3

6   0   3                    3   0   6

2   4   7                    2   4   7

1   1   2                    2   1   1

+）   0   2   0               +）  0   2   0

        ————————            —————————

        1   1   0   5                    9   0   7

（a）移位疊加                    (b) 折疊疊加

                      圖8.24 由疊加法求哈希地址

4． 除留余數(shù)法

假設(shè)哈希表長為m，p為小于等于m的最大素數(shù)，則哈希函數(shù)為

h（k）=k  %  p ，其中%為模p取余運算。

例如，已知待散列元素為（18，75，60，43，54，90，46），表長m=10，p=7，則有

    h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   

    h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   

    h(46)=46 % 7=4

此時沖突較多。為減少沖突，可取較大的m值和p值，如m=p=13，結(jié)果如下：

    h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    

    h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   

    h(46)=46 % 13=7

此時沒有沖突，如圖8.25所示。

0      1      2     3     4     5      6     7     8     9     10     11    12

                      圖8.25  除留余數(shù)法求哈希地址

5． 偽隨機數(shù)法

    采用一個偽隨機函數(shù)做哈希函數(shù)，即h(key)=random(key)。

在實際應(yīng)用中，應(yīng)根據(jù)具體情況，靈活采用不同的方法，并用實際數(shù)據(jù)測試它的性能，以便做出正確判定。通常應(yīng)考慮以下五個因素 ：

l         計算哈希函數(shù)所需時間 （簡單）。

l         關(guān)鍵字的長度。

l         哈希表大小。

l         關(guān)鍵字分布情況。

l         記錄查找頻率

8.4.2   處理沖突的方法

   通過構(gòu)造性能良好的哈希函數(shù)，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關(guān)鍵問題。創(chuàng)建哈希表和查找哈希表都會遇到?jīng)_突，兩種情況下解決沖突的方法應(yīng)該一致。下面以創(chuàng)建哈希表為例，說明解決沖突的方法。常用的解決沖突方法有以下四種：

1.         開放定址法

這種方法也稱再散列法，其基本思想是：當關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應(yīng)元素存入其中。這種方法有一個通用的再散列函數(shù)形式：

          Hi=（H（key）+d_i）% m   i=1，2，…，n

    其中H（key）為哈希函數(shù)，m 為表長，d_i稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三種：

l         線性探測再散列

    d_ii=1，2，3，…，m-1

這種方法的特點是：沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。

l         二次探測再散列

    d_i=1²，-1²，2²，-2²，…，k²，-k²    ( k<=m/2 )

    這種方法的特點是：沖突發(fā)生時，在表的左右進行跳躍式探測，比較靈活。

l         偽隨機探測再散列

    d_i=偽隨機數(shù)序列。

具體實現(xiàn)時，應(yīng)建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m），并給定一個隨機數(shù)做起點。

例如，已知哈希表長度m=11，哈希函數(shù)為：H（key）= key  %  11，則H（47）=3，H（26）=4，H（60）=5，假設(shè)下一個關(guān)鍵字為69，則H（69）=3，與47沖突。如果用線性探測再散列處理沖突，下一個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，繼續(xù)找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元，參圖8.26 (a)。如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 1²）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 1²）% 11 = 2，此時不再沖突，將69填入2號單元，參圖8.26 (b)。如果用偽隨機探測再散列處理沖突，且偽隨機數(shù)序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元，參圖8.26 (c)。

0        1       2      3      4      5       6      7      8       9      10    

         （a） 用線性探測再散列處理沖突

0        1       2      3      4      5       6      7      8       9      10    

         （b） 用二次探測再散列處理沖突

0        1       2      3      4      5       6      7      8       9      10    

         （c） 用偽隨機探測再散列處理沖突

                      圖8.26開放地址法處理沖突

從上述例子可以看出，線性探測再散列容易產(chǎn)生“二次聚集”，即在處理同義詞的沖突時又導致非同義詞的沖突。例如，當表中i, i+1 ,i+2三個單元已滿時，下一個哈希地址為i, 或i+1 ,或i+2，或i+3的元素，都將填入i+3這同一個單元，而這四個元素并非同義詞。線性探測再散列的優(yōu)點是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。

2.         再哈希法

    這種方法是同時構(gòu)造多個不同的哈希函數(shù)：

    H_i=RH₁（key）  i=1，2，…，k

當哈希地址H_i=RH₁（key）發(fā)生沖突時，再計算H_i=RH₂（key）……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。

3.         鏈地址法

    這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。

例如，已知一組關(guān)鍵字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表長度為13，哈希函數(shù)為：H（key）= key % 13，則用鏈地址法處理沖突的結(jié)果如圖8.27所示：

圖8.27  鏈地址法處理沖突時的哈希表

本例的平均查找長度 ASL=(1*7+2*4+3*1)=1.5

4、建立公共溢出區(qū)

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表