最近在復(fù)習(xí)算法和數(shù)據(jù)結(jié)構(gòu) ，這章把hash表的概念和相關(guān)題目進行匯總。 ? ? ? ? ? ??

一、前言

1.1、哈希表和數(shù)組、以及鏈表的對比：

(1).數(shù)組的特點：尋址容易，插入和刪除困難；數(shù)組存儲連續(xù),查找一個元素的時間復(fù)雜度為O(1)；

(2).鏈表的特點：尋址困難，插入和刪除容易。鏈表存儲區(qū)是離散的，遍歷鏈表的元素的時間復(fù)雜度為O(N)。

(3).hash-table是根據(jù)關(guān)鍵值（key-value）來直接進行訪問的數(shù)據(jù)結(jié)構(gòu)，它結(jié)合了數(shù)組和鏈表的優(yōu)點。hash表的難點

在于設(shè)計hash函數(shù)，以及解決沖突。這里我們會在后面提及；

1.2、一個hash表運用的的直觀理解(內(nèi)容取自教材書)

這里是一些聯(lián)系人的信息，如果要存儲這些信息你會怎么做？我們比較直觀的想法是，設(shè)計一個結(jié)構(gòu)體，用鏈表來存儲。結(jié)構(gòu)體里面包含一個char型數(shù)組存放名字，char字符串存放電話號碼，和一個結(jié)構(gòu)體指針用來存放下個結(jié)構(gòu)體的地址。

[cpp]view plaincopy

張三?13980593357

李四?15828662334

王五?13409821234

張帥?13890583472

當(dāng)要查找”王五 15828662334“這條記錄是否在這張鏈表中時，可能會從鏈表的頭結(jié)點開始遍歷，依次將每個結(jié)點中的姓名同”李四“進行比較，直到查找成功或者失敗為止，這種做法的時間復(fù)雜度為O(n)。即使采用二叉排序樹進行存儲，也最多為O(logn)。假設(shè)能夠通過”王五“這個信息直接獲取到該記錄在表中的存儲位置，就能省掉中間關(guān)鍵字比較的這個環(huán)節(jié)，復(fù)雜度直接降到O(1)。Hash表就能夠達到這樣的效果。

Hash表采用一個映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲位置，從而在想要查找該記錄時，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計算出該記錄在表中的存儲位置，通常情況下，這種映射關(guān)系稱作為Hash函數(shù)，而通過Hash函數(shù)和關(guān)鍵字計算出來的存儲位置(注意這里的存儲位置只是表中的存儲位置，并不是實際的物理地址)稱作為Hash地址。比如上述例子中，假如聯(lián)系人信息采用Hash表存儲，則當(dāng)想要找到“李四”的信息時，直接根據(jù)“李四”和Hash函數(shù)計算出Hash地址即可。

二、hash函數(shù)的設(shè)計

1、整數(shù)的hash函數(shù)設(shè)計

常見的hash函數(shù)有三種，分別是：直接取余法、乘積取整法、平方取中法。下面一一介紹：

1.1、直接取余法

直接取余法根據(jù)字面意思我們就能理解到，它的基本實現(xiàn)是用關(guān)鍵字直接除以散列表的大小(我們一般取跟元素個數(shù)最

接近的質(zhì)數(shù)作為散列表的大小)。如果知道Hash表的最大長度為m，可以取不大于m的最大質(zhì)數(shù)p，然后對關(guān)鍵字進

行取余運算，h(key)=key%p。很多的書上認為，哈希表的大小最好是選擇一個大的質(zhì)數(shù)，并且最好不要和2的整數(shù)冪接近。最不好的選擇是哈希表的大小恰好是2的整數(shù)冪。

這里可以這么認為：計算機是用二進制存儲的，當(dāng)一個二進制數(shù)除以一個2的整數(shù)冪的時候，結(jié)果就是這個二進制數(shù)的后幾位，前面的位都丟失了，也就意味著丟失了一部分信息，進而導(dǎo)致哈希表中的元素分布不均勻。為了避免產(chǎn)生沖突，我們可以采用加、乘法、移位等等運算關(guān)系來進行處理，然后再取余數(shù)，獲得哈希地址。

下面是個例子。

[cpp]view plaincopy

staticintadditiveHash(String?key,intprime)//prime為我們選取的hash表大小。

{

inthash,?i;

for(hash?=?key.length(),?i?=?0;?i?<?key.length();?i++)

?hash?+=?key.charAt(i);

return(hash?%?prime);

}

1.2、乘積取整法

關(guān)鍵字k乘以一個在(0,1)中的實數(shù)（最好是無理數(shù)），得到一個(0,1)之間的實數(shù)；取出其小數(shù)部分，乘以m，再取整數(shù)部分，即得K在Hash表中的位置。

1.3、平方取中法

對關(guān)鍵字進行平方運算，然后取結(jié)果的中間幾位作為Hash地址。假如有以下關(guān)鍵字序列{421，423，436}，平

方之后的結(jié)果為{177241，178929，190096}，那么可以取{72，89，00}作為Hash地址。

2、字符串的hash函數(shù)設(shè)計

我們一般是通過某種算法，以把一個字符串"壓縮" 成一個整數(shù)。當(dāng)然，一個32位整數(shù)是無法對應(yīng)回一個字符串的，但在程序中，兩個字符串計算出的Hash值相等的可能非常小。下面我介紹幾個經(jīng)典的字符串hash函數(shù)設(shè)計。

2.1"One-Way Hash"算法

這個算法是Blizzard的創(chuàng)作，是一個非常高效的把字符串轉(zhuǎn)換成整數(shù)的算法，舉個例子，字符串"unitneutralacritter.grp"，通過這個算法得到的結(jié)果是0xA26067F3。

[cpp]view plaincopy

unsignedlongHashString(char*lpszFileName,?unsignedlongdwHashType)

{

unsignedchar*key?=?(unsignedchar*)lpszFileName;

unsignedlongseed1?=?0x7FED7FED,?seed2?=?0xEEEEEEEE;

intch;

while(*key?!=?0)

{

ch?=?toupper(*key++);//toupper是轉(zhuǎn)換為大寫

seed1?=?cryptTable[(dwHashType?<<?8)?+?ch]?^?(seed1?+?seed2);

seed2?=?ch?+?seed1?+?seed2?+?(seed2?<<?5)?+?3;

}

returnseed1;

}

運用上面的函數(shù)就可以把字符串轉(zhuǎn)化為整數(shù)，接下來我們用這個整數(shù)就可以通過hash函數(shù)產(chǎn)生hash地址了。

[cpp]view plaincopy

intGetHashTablePos(char*lpszString,?SOMESTRUCTURE?*lpTable,intnTableSize)

{

intnHash?=?HashString(lpszString),?nHashPos?=?nHash?%?nTableSize;

if(lpTable[nHashPos].bExists?&&?!strcmp(lpTable[nHashPos].pString,?lpszString))

returnnHashPos;

else

return-1;//Error?value

}

其他的字符串轉(zhuǎn)換成整數(shù)算法，可以查閱相關(guān)書籍，這不再深入分析。

三、hash沖突的解決方法

1、拉鏈法

最常用的一種解決哈希沖突的方法，我們可以理解為“鏈表的數(shù)組”，如圖：

左邊很明顯是個數(shù)組，數(shù)組的每個成員包括一個指針，指向一個鏈表的頭，當(dāng)然這個鏈表可能為空，也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

這里給個例子：設(shè)有 m ＝ 5 ， H(K) ＝ K mod 5 ，關(guān)鍵字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外鏈地址法所建立的哈希表如下圖所示：

2、開放定址法

用開放定址法解決沖突的做法是：當(dāng)沖突發(fā)生時，使用某種探查(亦稱探測)技術(shù)在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定 的關(guān)鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結(jié)點存人該地址單元）。查找時探查到開放的 地址則表明表中無待查的關(guān)鍵字，即查找失敗。

注意：

①用開放定址法建立散列表時，建表前須將表中所有單元(更嚴(yán)格地說，是指單元中存儲的關(guān)鍵字)置空。

②空單元的表示與具體的應(yīng)用相關(guān)。

按照形成探查序列的方法不同，可將開放定址法區(qū)分為線性探查法、線性補償探測法、隨機探測等。

2.1、線性探查法(Linear Probing)

該方法的基本思想是：

將散列表T[0..m-1]看成是一個循環(huán)向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為

d，d+l，d+2，…，m-1，0，1，…，d-

即:探查時從地址d開始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到T[d-1]為止。

探查過程終止于三種情況：

(1)若當(dāng)前探查的單元為空，則表示查找失?。ㄈ羰遣迦雱t將key寫入其中）；

(2)若當(dāng)前探查的單元中含有key，則查找成功，但對于插入意味著失敗；

(3)若探查到T[d-1]時仍未發(fā)現(xiàn)空單元也未找到key，則無論是查找還是插入均意味著失敗(此時表滿)。

利用開放地址法的一般形式，線性探查法的探查序列為：

hi=(h(key)+i)％m 0≤i≤m-1//即di=i

用線性探測法處理沖突，思路清晰，算法簡單，但存在下列缺點：

① 處理溢出需另編程序。一般可另外設(shè)立一個溢出表，專門用來存放上述哈希表中放不下的記錄。此溢出表最簡

單的結(jié)構(gòu)是順序表，查找方法可用順序查找。

② 按上述算法建立起來的哈希表，刪除工作非常困難。假如要從哈希表 HT 中刪除一個記錄，按理應(yīng)將這個記錄所

在位置置為空，但我們不能這樣做，而只能標(biāo)上已被刪除的標(biāo)記，否則，將會影響以后的查找。

③ 線性探測法很容易產(chǎn)生堆聚現(xiàn)象。所謂堆聚現(xiàn)象，就是存入哈希表的記錄在表中連成一片。按照線性探測法處

理沖突，如果生成哈希地址的連續(xù)序列愈長 ( 即不同關(guān)鍵字值的哈希地址相鄰在一起愈長 ) ，則當(dāng)新的記錄加入該

表時，與這個序列發(fā)生沖突的可能性愈大。因此，哈希地址的較長連續(xù)序列比較短連續(xù)序列生長得快，這就意味

著，一旦出現(xiàn)堆聚 ( 伴隨著沖突 ) ，就將引起進一步的堆聚。

2.2、線性補償探測法

線性補償探測法的基本思想是：

將線性探測的步長從 1 改為 Q ，即將上述算法中的 j ＝ (j ＋ 1) % m 改為： j ＝ (j ＋ Q) % m ，而且要求 Q 與

m 是互質(zhì)的，以便能探測到哈希表中的所有單元。

【例】 PDP-11 小型計算機中的匯編程序所用的符合表，就采用此方法來解決沖突，所用表長 m ＝ 1321 ，選用

Q ＝ 25 。

2.3、隨機探測

隨機探測的基本思想是：

將線性探測的步長從常數(shù)改為隨機數(shù)，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一個隨機數(shù)。在實際程序中應(yīng)預(yù)先

用隨機數(shù)發(fā)生器產(chǎn)生一個隨機序列，將此序列作為依次探測的步長。這樣就能使不同的關(guān)鍵字具有不同的探測次

序，從而可以避 免或減少堆聚?；谂c線性探測法相同的理由，在線性補償探測法和隨機探測法中，刪除一個記

錄后也要打上刪除標(biāo)記。