最近在復(fù)習(xí)算法和數(shù)據(jù)結(jié)構(gòu) 钟些，這章把hash表的概念和相關(guān)題目進(jìn)行匯總墩朦。 ? ? ? ? ? ??
1.1、哈希表和數(shù)組氓涣、以及鏈表的對(duì)比：
(1).數(shù)組的特點(diǎn)：尋址容易牛哺，插入和刪除困難；數(shù)組存儲(chǔ)連續(xù),查找一個(gè)元素的時(shí)間復(fù)雜度為O(1)劳吠；
(2).鏈表的特點(diǎn)：尋址困難引润，插入和刪除容易。鏈表存儲(chǔ)區(qū)是離散的痒玩，遍歷鏈表的元素的時(shí)間復(fù)雜度為O(N)淳附。
(3).hash-table是根據(jù)關(guān)鍵值（key-value）來(lái)直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)议慰，它結(jié)合了數(shù)組和鏈表的優(yōu)點(diǎn)。hash表的難點(diǎn)
在于設(shè)計(jì)hash函數(shù)奴曙，以及解決沖突别凹。這里我們會(huì)在后面提及；
1.2洽糟、一個(gè)hash表運(yùn)用的的直觀理解(內(nèi)容取自教材書)
這里是一些聯(lián)系人的信息炉菲，如果要存儲(chǔ)這些信息你會(huì)怎么做？我們比較直觀的想法是脊框，設(shè)計(jì)一個(gè)結(jié)構(gòu)體颁督，用鏈表來(lái)存儲(chǔ)。結(jié)構(gòu)體里面包含一個(gè)char型數(shù)組存放名字浇雹，char字符串存放電話號(hào)碼，和一個(gè)結(jié)構(gòu)體指針用來(lái)存放下個(gè)結(jié)構(gòu)體的地址屿讽。
[cpp]view plaincopy
張三?13980593357
李四?15828662334
王五?13409821234
張帥?13890583472
當(dāng)要查找”王五 15828662334“這條記錄是否在這張鏈表中時(shí)昭灵，可能會(huì)從鏈表的頭結(jié)點(diǎn)開(kāi)始遍歷，依次將每個(gè)結(jié)點(diǎn)中的姓名同”李四“進(jìn)行比較伐谈，直到查找成功或者失敗為止烂完，這種做法的時(shí)間復(fù)雜度為O(n)。即使采用二叉排序樹(shù)進(jìn)行存儲(chǔ)诵棵，也最多為O(logn)抠蚣。假設(shè)能夠通過(guò)”王五“這個(gè)信息直接獲取到該記錄在表中的存儲(chǔ)位置，就能省掉中間關(guān)鍵字比較的這個(gè)環(huán)節(jié)履澳，復(fù)雜度直接降到O(1)嘶窄。Hash表就能夠達(dá)到這樣的效果。
Hash表采用一個(gè)映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲(chǔ)位置距贷，從而在想要查找該記錄時(shí)柄冲，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲(chǔ)位置，通常情況下忠蝗，這種映射關(guān)系稱作為Hash函數(shù)现横，而通過(guò)Hash函數(shù)和關(guān)鍵字計(jì)算出來(lái)的存儲(chǔ)位置(注意這里的存儲(chǔ)位置只是表中的存儲(chǔ)位置，并不是實(shí)際的物理地址)稱作為Hash地址阁最。比如上述例子中戒祠，假如聯(lián)系人信息采用Hash表存儲(chǔ)，則當(dāng)想要找到“李四”的信息時(shí)速种，直接根據(jù)“李四”和Hash函數(shù)計(jì)算出Hash地址即可姜盈。
1哟旗、整數(shù)的hash函數(shù)設(shè)計(jì)
常見(jiàn)的hash函數(shù)有三種贩据，分別是：直接取余法栋操、乘積取整法、平方取中法饱亮。下面一一介紹：
直接取余法根據(jù)字面意思我們就能理解到，它的基本實(shí)現(xiàn)是用關(guān)鍵字直接除以散列表的大小(我們一般取跟元素個(gè)數(shù)最
接近的質(zhì)數(shù)作為散列表的大小)近上。如果知道Hash表的最大長(zhǎng)度為m剔宪，可以取不大于m的最大質(zhì)數(shù)p，然后對(duì)關(guān)鍵字進(jìn)
行取余運(yùn)算壹无，h(key)=key%p葱绒。很多的書上認(rèn)為，哈希表的大小最好是選擇一個(gè)大的質(zhì)數(shù)斗锭，并且最好不要和2的整數(shù)冪接近地淀。最不好的選擇是哈希表的大小恰好是2的整數(shù)冪。
這里可以這么認(rèn)為：計(jì)算機(jī)是用二進(jìn)制存儲(chǔ)的岖是，當(dāng)一個(gè)二進(jìn)制數(shù)除以一個(gè)2的整數(shù)冪的時(shí)候帮毁，結(jié)果就是這個(gè)二進(jìn)制數(shù)的后幾位，前面的位都丟失了豺撑，也就意味著丟失了一部分信息烈疚，進(jìn)而導(dǎo)致哈希表中的元素分布不均勻。為了避免產(chǎn)生沖突聪轿，我們可以采用加爷肝、乘法、移位等等運(yùn)算關(guān)系來(lái)進(jìn)行處理陆错，然后再取余數(shù)灯抛，獲得哈希地址。
下面是個(gè)例子危号。
[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);
}
關(guān)鍵字k乘以一個(gè)在(0,1)中的實(shí)數(shù)（最好是無(wú)理數(shù)）外莲，得到一個(gè)(0,1)之間的實(shí)數(shù)猪半；取出其小數(shù)部分，乘以m偷线，再取整數(shù)部分磨确，即得K在Hash表中的位置。
對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算，然后取結(jié)果的中間幾位作為Hash地址鸯隅。假如有以下關(guān)鍵字序列{421卒蘸，423，436}庞钢，平
方之后的結(jié)果為{177241晕窑，178929粘优，190096}骗炉，那么可以取{72照宝，89，00}作為Hash地址句葵。
2厕鹃、字符串的hash函數(shù)設(shè)計(jì)
2.1"One-Way Hash"算法
這個(gè)算法是Blizzard的創(chuàng)作请垛，是一個(gè)非常高效的把字符串轉(zhuǎn)換成整數(shù)的算法洪碳，舉個(gè)例子，字符串"unitneutralacritter.grp"叼屠，通過(guò)這個(gè)算法得到的結(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;
}
運(yùn)用上面的函數(shù)就可以把字符串轉(zhuǎn)化為整數(shù)绞铃，接下來(lái)我們用這個(gè)整數(shù)就可以通過(guò)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)書籍儿捧，這不再深入分析荚坞。
最常用的一種解決哈希沖突的方法颓影，我們可以理解為“鏈表的數(shù)組”，如圖：
左邊很明顯是個(gè)數(shù)組懒鉴，數(shù)組的每個(gè)成員包括一個(gè)指針诡挂，指向一個(gè)鏈表的頭，當(dāng)然這個(gè)鏈表可能為空临谱，也可能元素很多璃俗。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征悉默，找到正確的鏈表城豁，再?gòu)逆湵碇姓页鲞@個(gè)元素。
這里給個(gè)例子：設(shè)有 m ＝ 5 抄课， H(K) ＝ K mod 5 唱星，關(guān)鍵字值序例 5 雳旅， 21 ， 17 间聊， 9 攒盈， 15 ， 36 甸饱， 41 沦童， 24 ，按外鏈地址法所建立的哈希表如下圖所示：
用開(kāi)放定址法解決沖突的做法是：當(dāng)沖突發(fā)生時(shí)偷遗，使用某種探查(亦稱探測(cè))技術(shù)在散列表中形成一個(gè)探查(測(cè))序列。沿此序列逐個(gè)單元地查找驼壶，直到找到給定 的關(guān)鍵字氏豌，或者碰到一個(gè)開(kāi)放的地址(即該地址單元為空)為止（若要插入，在探查到開(kāi)放的地址热凹，則可將待插入的新結(jié)點(diǎn)存人該地址單元）泵喘。查找時(shí)探查到開(kāi)放的 地址則表明表中無(wú)待查的關(guān)鍵字，即查找失敗般妙。
注意：
①用開(kāi)放定址法建立散列表時(shí)纪铺，建表前須將表中所有單元(更嚴(yán)格地說(shuō)，是指單元中存儲(chǔ)的關(guān)鍵字)置空碟渺。
②空單元的表示與具體的應(yīng)用相關(guān)鲜锚。
按照形成探查序列的方法不同，可將開(kāi)放定址法區(qū)分為線性探查法苫拍、線性補(bǔ)償探測(cè)法芜繁、隨機(jī)探測(cè)等。
該方法的基本思想是：
將散列表T[0..m-1]看成是一個(gè)循環(huán)向量骏令，若初始探查的地址為d(即h(key)=d)，則最長(zhǎng)的探查序列為
d垄提，d+l榔袋，d+2，…塔淤，m-1摘昌，0，1高蜂，…聪黎，d-
即:探查時(shí)從地址d開(kāi)始，首先探查T[d]，然后依次探查T[d+1]稿饰，…锦秒，直到T[m-1]，此后又循環(huán)到T[0]喉镰，T[1]旅择，…，直到探查到T[d-1]為止侣姆。
探查過(guò)程終止于三種情況：
(1)若當(dāng)前探查的單元為空生真，則表示查找失敗（若是插入則將key寫入其中）捺宗；
(2)若當(dāng)前探查的單元中含有key柱蟀，則查找成功，但對(duì)于插入意味著失斞晾鳌长已；
(3)若探查到T[d-1]時(shí)仍未發(fā)現(xiàn)空單元也未找到key，則無(wú)論是查找還是插入均意味著失敗(此時(shí)表滿)昼牛。
利用開(kāi)放地址法的一般形式术瓮，線性探查法的探查序列為：
hi=(h(key)+i)％m 0≤i≤m-1//即di=i
用線性探測(cè)法處理沖突，思路清晰贰健，算法簡(jiǎn)單胞四，但存在下列缺點(diǎn)：
① 處理溢出需另編程序。一般可另外設(shè)立一個(gè)溢出表伶椿，專門用來(lái)存放上述哈希表中放不下的記錄撬讽。此溢出表最簡(jiǎn)
單的結(jié)構(gòu)是順序表，查找方法可用順序查找悬垃。
② 按上述算法建立起來(lái)的哈希表，刪除工作非常困難甘苍。假如要從哈希表 HT 中刪除一個(gè)記錄尝蠕，按理應(yīng)將這個(gè)記錄所
在位置置為空，但我們不能這樣做载庭，而只能標(biāo)上已被刪除的標(biāo)記看彼，否則，將會(huì)影響以后的查找囚聚。
③ 線性探測(cè)法很容易產(chǎn)生堆聚現(xiàn)象靖榕。所謂堆聚現(xiàn)象，就是存入哈希表的記錄在表中連成一片顽铸。按照線性探測(cè)法處
理沖突茁计，如果生成哈希地址的連續(xù)序列愈長(zhǎng) ( 即不同關(guān)鍵字值的哈希地址相鄰在一起愈長(zhǎng) ) ，則當(dāng)新的記錄加入該
表時(shí)谓松，與這個(gè)序列發(fā)生沖突的可能性愈大星压。因此践剂，哈希地址的較長(zhǎng)連續(xù)序列比較短連續(xù)序列生長(zhǎng)得快，這就意味
著娜膘，一旦出現(xiàn)堆聚 ( 伴隨著沖突 ) 逊脯，就將引起進(jìn)一步的堆聚。
線性補(bǔ)償探測(cè)法的基本思想是：
將線性探測(cè)的步長(zhǎng)從 1 改為 Q 军洼，即將上述算法中的 j ＝ (j ＋ 1) % m 改為： j ＝ (j ＋ Q) % m ，而且要求 Q 與
m 是互質(zhì)的演怎，以便能探測(cè)到哈希表中的所有單元匕争。
【例】 PDP-11 小型計(jì)算機(jī)中的匯編程序所用的符合表，就采用此方法來(lái)解決沖突颤枪，所用表長(zhǎng) m ＝ 1321 汗捡，選用
Q ＝ 25 。
隨機(jī)探測(cè)的基本思想是：
將線性探測(cè)的步長(zhǎng)從常數(shù)改為隨機(jī)數(shù)扇住，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一個(gè)隨機(jī)數(shù)盗胀。在實(shí)際程序中應(yīng)預(yù)先
用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)隨機(jī)序列艘蹋，將此序列作為依次探測(cè)的步長(zhǎng)。這樣就能使不同的關(guān)鍵字具有不同的探測(cè)次
序票灰，從而可以避 免或減少堆聚女阀。基于與線性探測(cè)法相同的理由屑迂，在線性補(bǔ)償探測(cè)法和隨機(jī)探測(cè)法中浸策，刪除一個(gè)記
錄后也要打上刪除標(biāo)記。
