哈希表的構造及解決沖突

1． 數字分析法

如果事先知道關鍵字集合，并且每個關鍵字的位數比哈希表的位址碼位數多時，可以從關鍵字中選出分布較均勻的若幹位，構成哈希位址。例如，有80個記錄，關鍵字為8位十進制整數d1d2d3…d7d8，如哈希表長取100，則哈希表的位址空間為：00~99。假設經過分析，各關鍵字中 d4和d7的取值分布較均勻，則哈希函數為：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。相反，假設經過分析，各關鍵字中 d1和d8的取值分布極不均勻， d1 都等于5，d8 都等于2，此時，如果哈希函數為：h(key)=h(d1d2d3…d7d8)=d1d8，則所有關鍵字的位址碼都是52，顯然不可取。
           

2． 平方取中法

當無法确定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然後按需要取平方值的中間幾位作為哈希位址。這是因為：平方後中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的機率産生不同的哈希位址。

3． 分段疊加法

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

4． 除留餘數法

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

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，結果如下：

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
           

處理沖突的方法：

1. 開放定址法
              

這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希位址p=H（key）出現沖突時，以p為基礎，産生另一個哈希位址p1，如果p1仍然沖突，再以p為基礎，産生另一個哈希位址p2，…，直到找出一個不沖突的哈希位址pi ，将相應元素存入其中。這種方法有一個通用的再散列函數形式：

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

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

l 線性探測再散列

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

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

l 二次探測再散列

di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )

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

l 僞随機探測再散列

di=僞随機數序列。
           

具體實作時，應建立一個僞随機數發生器，（如i=(i+p) % m），并給定一個随機數做起點。

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

1. 再哈希法
              

   這種方法是同時構造多個不同的哈希函數：

   Hi=RH1（key） i=1，2，…，k

當哈希位址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再産生。這種方法不易産生聚集，但增加了計算時間。

1. 鍊位址法
              

   這種方法的基本思想是将所有哈希位址為i的元素構成一個稱為同義詞鍊的單連結清單，并将單連結清單的頭指針存在哈希表的第i個單元中，因而查找、插入和删除主要在同義詞鍊中進行。鍊位址法适用于經常進行插入和删除的情況。

4、建立公共溢出區

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