一稚茅、散列的概念

散列方法的主要思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵碼值來(lái)確定其存儲(chǔ)地址：以關(guān)鍵碼值K為自變量，通過(guò)一定的函數(shù)關(guān)系h(K)(稱為散列函數(shù))，計(jì)算出對(duì)應(yīng)的函數(shù)值來(lái)谷暮，把這個(gè)值解釋為結(jié)點(diǎn)的存儲(chǔ)地址，將結(jié)點(diǎn)存入到此存儲(chǔ)單元中盛垦。檢索時(shí)湿弦，用同樣的方法計(jì)算地址，然后到相應(yīng)的單元里去取要找的結(jié)點(diǎn)腾夯。通過(guò)散列方法可以對(duì)結(jié)點(diǎn)進(jìn)行快速檢索颊埃。散列（hash，也稱“哈系悖”）是一種重要的存儲(chǔ)方式班利，也是一種常見(jiàn)的檢索方法。

按散列存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱為散列表（hash table）榨呆。散列表中的一個(gè)位置稱為槽(slot)罗标。散列技術(shù)的核心是散列函數(shù)(hash function)。 對(duì)任意給定的動(dòng)態(tài)查找表DL积蜻，如果選定了某個(gè)“理想的”散列函數(shù)h及相應(yīng)的散列表HT闯割，則對(duì)DL中的每個(gè)數(shù)據(jù)元素X。函數(shù)值h（X.key）就是X在散列表HT中的存儲(chǔ)位置浅侨。插入（或建表）時(shí)數(shù)據(jù)元素X將被安置在該位置上纽谒，并且檢索X時(shí)也到該位置上去查找。由散列函數(shù)決定的存儲(chǔ)位置稱為散列地址如输。 因此鼓黔，散列的核心就是：由散列函數(shù)決定關(guān)鍵碼值(X.key)與散列地址h(X.key)之間的對(duì)應(yīng)關(guān)系，通過(guò)這種關(guān)系來(lái)實(shí)現(xiàn)組織存儲(chǔ)并進(jìn)行檢索不见。

一般情況下澳化，散列表的存儲(chǔ)空間是一個(gè)一維數(shù)組HT[M]，散列地址是數(shù)組的下標(biāo)稳吮。設(shè)計(jì)散列方法的目標(biāo)缎谷，就是設(shè)計(jì)某個(gè)散列函數(shù)h，0<=h( K ) < M灶似；對(duì)于關(guān)鍵碼值K列林，得到HT[i] = K。 在一般情況下酪惭，散列表的空間必須比結(jié)點(diǎn)的集合大希痴，此時(shí)雖然浪費(fèi)了一定的空間，但換取的是檢索效率春感。設(shè)散列表的空間大小為M逸月，填入表中的結(jié)點(diǎn)數(shù)為N，則稱為散列表的負(fù)載因子（load factor捂蕴，也有人翻譯為“裝填因子”）悔捶。建立散列表時(shí)，若關(guān)鍵碼與散列地址是一對(duì)一的關(guān)系，則在檢索時(shí)只需根據(jù)散列函數(shù)對(duì)給定值進(jìn)行某種運(yùn)算，即可得到待查結(jié)點(diǎn)的存儲(chǔ)位置。但是宰缤，散列函數(shù)可能對(duì)于不相等的關(guān)鍵碼計(jì)算出相同的散列地址，我們稱該現(xiàn)象為沖突（collision）竟纳，發(fā)生沖突的兩個(gè)關(guān)鍵碼稱為該散列函數(shù)的同義詞撵溃。在實(shí)際應(yīng)用中，很少存在不產(chǎn)生沖突的散列函數(shù)锥累，我們必須考慮在沖突發(fā)生時(shí)的處理辦法缘挑。

二、散列函數(shù)

在以下的討論中桶略，我們假設(shè)處理的是值為整型的關(guān)鍵碼语淘，否則我們總可以建立一種關(guān)鍵碼與正整數(shù)之間的一一對(duì)應(yīng)關(guān)系，從而把該關(guān)鍵碼的檢索轉(zhuǎn)化為對(duì)與其對(duì)應(yīng)的正整數(shù)的檢索际歼；同時(shí)惶翻，進(jìn)一步假定散列函數(shù)的值落在0到M－1之間。散列函數(shù)的選取原則是：運(yùn)算盡可能簡(jiǎn)單鹅心；函數(shù)的值域必須在散列表的范圍內(nèi)吕粗；盡可能使得結(jié)點(diǎn)均勻分布，也就是盡量讓不同的關(guān)鍵碼具有不同的散列函數(shù)值旭愧。需要考慮各種因素：關(guān)鍵碼長(zhǎng)度颅筋、散列表大小、關(guān)鍵碼分布情況输枯、記錄的檢索頻率等等议泵。下面我們介紹幾種常用的散列函數(shù)。

1.除余法

顧名思義桃熄，除余法就是用關(guān)鍵碼x除以M（往往取散列表長(zhǎng)度）先口，并取余數(shù)作為散列地址。除余法幾乎是最簡(jiǎn)單的散列方法瞳收，散列函數(shù)為： h(x) ＝ x mod M碉京。

2.乘余取整法

使用此方法時(shí)，先讓關(guān)鍵碼key乘上一個(gè)常數(shù)A (0< A < 1)螟深，提取乘積的小數(shù)部分谐宙。然后，再用整數(shù)n乘以這個(gè)值血崭，對(duì)結(jié)果向下取整卧惜，把它做為散列的地址。散列函數(shù)為： hash ( key ) = _LOW( n × ( A × key % 1 ) )夹纫。 其中咽瓷，“A × key % 1”表示取 A × key 小數(shù)部分，即： A × key % 1 = A × key - _LOW(A × key), 而_LOW(X)是表示對(duì)X取下整

3.平方取中法

由于整數(shù)相除的運(yùn)行速度通常比相乘要慢舰讹，所以有意識(shí)地避免使用除余法運(yùn)算可以提高散列算法的運(yùn)行時(shí)間茅姜。平方取中法的具體實(shí)現(xiàn)是：先通過(guò)求關(guān)鍵碼的平方值，從而擴(kuò)大相近數(shù)的差別月匣，然后根據(jù)表長(zhǎng)度取中間的幾位數(shù)（往往取二進(jìn)制的比特位）作為散列函數(shù)值钻洒。因?yàn)橐粋€(gè)乘積的中間幾位數(shù)與乘數(shù)的每一數(shù)位都相關(guān)，所以由此產(chǎn)生的散列地址較為均勻锄开。

4.數(shù)字分析法

假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, …, us)素标，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址萍悴。數(shù)字分析法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法头遭。即當(dāng)關(guān)鍵字的位數(shù)很多時(shí)，可以通過(guò)對(duì)關(guān)鍵字的各位進(jìn)行分析癣诱，丟掉分布不均勻的位计维，作為哈希值。它只適合于所有關(guān)鍵字值已知的情況撕予。通過(guò)分析分布情況把關(guān)鍵字取值區(qū)間轉(zhuǎn)化為一個(gè)較小的關(guān)鍵字取值區(qū)間鲫惶。

舉個(gè)例子：要構(gòu)造一個(gè)數(shù)據(jù)元素個(gè)數(shù)n=80,哈希長(zhǎng)度m=100的哈希表。不失一般性实抡，我們這里只給出其中8個(gè)關(guān)鍵字進(jìn)行分析欠母，8個(gè)關(guān)鍵字如下所示：

K1=61317602 K2=61326875 K3=62739628 K4=61343634

K5=62706815 K6=62774638 K7=61381262 K8=61394220

分析上述8個(gè)關(guān)鍵字可知，關(guān)鍵字從左到右的第1澜术、2艺蝴、3、6位取值比較集中鸟废，不宜作為哈希地址猜敢，剩余的第4、5盒延、7缩擂、8位取值較均勻，可選取其中的兩位作為哈希地址添寺。設(shè)選取最后兩位作為哈希地址胯盯，則這8個(gè)關(guān)鍵字的哈希地址分別為：2，75计露，28博脑，34憎乙，15，38叉趣，62泞边，20。

此法適于:能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度疗杉。

5.基數(shù)轉(zhuǎn)換法

將關(guān)鍵碼值看成另一種進(jìn)制的數(shù)再轉(zhuǎn)換成原來(lái)進(jìn)制的數(shù)阵谚，然后選其中幾位作為散列地址。

例Hash(80127429)=(80127429)13=8137+0136+1135+2134+7133+4132+2*131+9=(502432641)10如果取中間三位作為哈希值烟具，得Hash（80127429）=432
為了獲得良好的哈希函數(shù)梢什，可以將幾種方法聯(lián)合起來(lái)使用，比如先變基朝聋，再折疊或平方取中等等嗡午，只要散列均勻，就可以隨意拼湊冀痕。

6.折疊法

有時(shí)關(guān)鍵碼所含的位數(shù)很多翼馆，采用平方取中法計(jì)算太復(fù)雜，則可將關(guān)鍵碼分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）金度，然后取這幾部分的疊加和（舍去進(jìn)位）作為散列地址应媚，這方法稱為折疊法。

分為：

• 移位疊加：將分割后的幾部分低位對(duì)齊相加猜极。
• 邊界疊加:從一端沿分割界來(lái)回折疊中姜，然后對(duì)齊相加。

三跟伏、沖突解決的策略

盡管散列函數(shù)的目標(biāo)是使得沖突最少丢胚，但實(shí)際上沖突是無(wú)法避免的。因此受扳，我們必須研究沖突解決策略携龟。沖突解決技術(shù)可以分為兩類：開(kāi)散列方法( open hashing，也稱為拉鏈法勘高，separate chaining )和閉散列方法( closed hashing峡蟋，也稱為開(kāi)地址方法，open addressing )华望。這兩種方法的不同之處在于：開(kāi)散列法把發(fā)生沖突的關(guān)鍵碼存儲(chǔ)在散列表主表之外蕊蝗，而閉散列法把發(fā)生沖突的關(guān)鍵碼存儲(chǔ)在表中另一個(gè)槽內(nèi)。

1.分離鏈表法

(1)拉鏈法

開(kāi)散列方法的一種簡(jiǎn)單形式是把散列表中的每個(gè)槽定義為一個(gè)鏈表的表頭赖舟。散列到一個(gè)特定槽的所有記錄都放到這個(gè)槽的鏈表中蓬戚。圖9-5說(shuō)明了一個(gè)開(kāi)散列的散列表，這個(gè)表中每一個(gè)槽存儲(chǔ)一個(gè)記錄和一個(gè)指向鏈表其余部分的指針宾抓。這7個(gè)數(shù)存儲(chǔ)在有11個(gè)槽的散列表中子漩，使用的散列函數(shù)是h(K) = K mod 11豫喧。數(shù)的插入順序是77、7幢泼、110嘿棘、95、14旭绒、75和62。有2個(gè)值散列到第0個(gè)槽焦人，1個(gè)值散列到第3個(gè)槽挥吵，3個(gè)值散列到第7個(gè)槽，1個(gè)值散列到第9個(gè)槽花椭。

image

2.閉散列方法(開(kāi)放地址法)

閉散列方法把所有記錄直接存儲(chǔ)在散列表中忽匈。每個(gè)記錄關(guān)鍵碼key有一個(gè)由散列函數(shù)計(jì)算出來(lái)的基位置，即h(key)矿辽。如果要插入一個(gè)關(guān)鍵碼丹允，而另一個(gè)記錄已經(jīng)占據(jù)了R的基位置(發(fā)生碰撞)，那么就把R存儲(chǔ)在表中的其它地址內(nèi)袋倔，由沖突解決策略確定是哪個(gè)地址雕蔽。

閉散列表解決沖突的基本思想是：當(dāng)沖突發(fā)生時(shí)，使用某種方法為關(guān)鍵碼K生成一個(gè)散列地址序列d0宾娜，d1批狐，d2，... di 前塔，...dm-1嚣艇。其中d0=h（K）稱為K的基地址地置( home position )；所有di(0< i< m)是后繼散列地址华弓。當(dāng)插入K時(shí)食零，若基地址上的結(jié)點(diǎn)已被別的數(shù)據(jù)元素占用，則按上述地址序列依次探查寂屏，將找到的第一個(gè)開(kāi)放的空閑位置di作為K的存儲(chǔ)位置贰谣；若所有后繼散列地址都不空閑，說(shuō)明該閉散列表已滿迁霎，報(bào)告溢出冈爹。相應(yīng)地，檢索K時(shí)欧引，將按同值的后繼地址序列依次查找频伤，檢索成功時(shí)返回該位置di ；如果沿著探查序列檢索時(shí)芝此，遇到了開(kāi)放的空閑地址憋肖，則說(shuō)明表中沒(méi)有待查的關(guān)鍵碼因痛。刪除K時(shí)，也按同值的后繼地址序列依次查找岸更，查找到某個(gè)位置di具有該K值鸵膏，則刪除該位置di上的數(shù)據(jù)元素（刪除操作實(shí)際上只是對(duì)該結(jié)點(diǎn)加以刪除標(biāo)記）；如果遇到了開(kāi)放的空閑地址怎炊，則說(shuō)明表中沒(méi)有待刪除的關(guān)鍵碼谭企。因此，對(duì)于閉散列表來(lái)說(shuō)评肆，構(gòu)造后繼散列地址序列的方法债查，也就是處理沖突的方法。

形成探查的方法不同瓜挽，所得到的解決沖突的方法也不同盹廷。下面是幾種常見(jiàn)的構(gòu)造方法。

(1)線性探測(cè)法

將散列表看成是一個(gè)環(huán)形表久橙，若在基地址d（即h(K)=d）發(fā)生沖突俄占，則依次探查下述地址單元：d+1，d+2淆衷，......缸榄，M-1，0祝拯，1碰凶，......，d-1直到找到一個(gè)空閑地址或查找到關(guān)鍵碼為key的結(jié)點(diǎn)為止鹿驼。當(dāng)然欲低，若沿著該探查序列檢索一遍之后，又回到了地址d畜晰，則無(wú)論是做插入操作還是做檢索操作砾莱，都意味著失敗。 用于簡(jiǎn)單線性探查的探查函數(shù)是： p(K凄鼻，i) = i

例9.7 已知一組關(guān)鍵碼為（26腊瑟，36，41块蚌，38闰非，44，15峭范，68财松，12，06，51辆毡，25）菜秦，散列表長(zhǎng)度M= 15，用線性探查法解決沖突構(gòu)造這組關(guān)鍵碼的散列表舶掖。 因?yàn)閚=11球昨，利用除余法構(gòu)造散列函數(shù)，選取小于Ｍ的最大質(zhì)數(shù)P=13眨攘，則散列函數(shù)為：h(key) = key%13主慰。按順序插入各個(gè)結(jié)點(diǎn)： 26: h(26) = 0，36: h(36) = 10鲫售， 41: h(41) = 2共螺，38: h(38) = 12， 44: h(44) = 5龟虎。 插入15時(shí)，其散列地址為2沙庐，由于2已被關(guān)鍵碼為41的元素占用鲤妥，故需進(jìn)行探查。按順序探查法拱雏，顯然3為開(kāi)放的空閑地址棉安，故可將其放在3單元。類似地铸抑，68和12可分別放在4和13單元中.

(2)二次探查法

二次探查法的基本思想是：生成的后繼散列地址不是連續(xù)的贡耽，而是跳躍式的，以便為后續(xù)數(shù)據(jù)元素留下空間從而減少聚集鹊汛。二次探查法的探查序列依次為：12蒲赂，-12，22 刁憋，-22滥嘴，...等，也就是說(shuō)至耻，發(fā)生沖突時(shí)若皱，將同義詞來(lái)回散列在第一個(gè)地址的兩端。求下一個(gè)開(kāi)放地址的公式為：

image

image

(3)隨機(jī)探查法

理想的探查函數(shù)應(yīng)當(dāng)在探查序列中隨機(jī)地從未訪問(wèn)過(guò)的槽中選擇下一個(gè)位置尘颓，即探查序列應(yīng)當(dāng)是散列表位置的一個(gè)隨機(jī)排列走触。但是，我們實(shí)際上不能隨機(jī)地從探查序列中選擇一個(gè)位置疤苹，因?yàn)樵跈z索關(guān)鍵碼的時(shí)候不能建立起同樣的探查序列互广。然而，我們可以做一些類似于偽隨機(jī)探查( pseudo-random probing )的事情卧土。在偽隨機(jī)探查中兜辞，探查序列中的第i個(gè)槽是(h(K) + ri) mod M迎瞧，其中ri是1到M - 1之間數(shù)的“隨機(jī)”數(shù)序列。所有插入和檢索都使用相同的“隨機(jī)”數(shù)逸吵。探查函數(shù)將是 p(K凶硅，i) = perm[i - 1]， 這里perm是一個(gè)長(zhǎng)度為M - 1的數(shù)組扫皱，它包含值從1到M – 1的隨機(jī)序列足绅。

例子：
例如，已知哈希表長(zhǎng)度m=11韩脑，哈希函數(shù)為：H（key）= key % 11氢妈，則H（47）=3，H（26）=4段多，H（60）=5首量，假設(shè)下一個(gè)關(guān)鍵字為69，則H（69）=3进苍，與47沖突加缘。如果用線性探測(cè)再散列處理沖突，下一個(gè)哈希地址為H1=（3 + 1）% 11 = 4觉啊，仍然沖突拣宏，再找下一個(gè)哈希地址為H2=（3 + 2）% 11 = 5，還是沖突杠人，繼續(xù)找下一個(gè)哈希地址為H3=（3 + 3）% 11 = 6勋乾，此時(shí)不再?zèng)_突，將69填入5號(hào)單元嗡善，參圖8.26 (a)辑莫。如果用二次探測(cè)再散列處理沖突，下一個(gè)哈希地址為H1=（3 + 12）% 11 = 4罩引，仍然沖突摆昧，再找下一個(gè)哈希地址為H2=（3 - 12）% 11 = 2，此時(shí)不再?zèng)_突蜒程，將69填入2號(hào)單元绅你，參圖8.26 (b)。如果用偽隨機(jī)探測(cè)再散列處理沖突昭躺，且偽隨機(jī)數(shù)序列為：2忌锯，5，9领炫，……..偶垮，則下一個(gè)哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個(gè)哈希地址為H2=（3 + 5）% 11 = 8似舵，此時(shí)不再?zèng)_突脚猾，將69填入8號(hào)單元，參圖8.26 (c)砚哗。

image

(4)雙散列探查法

偽隨機(jī)探查和二次探查都能消除基本聚集——即基地址不同的關(guān)鍵碼龙助，其探查序列的某些段重疊在一起——的問(wèn)題。然而蛛芥，如果兩個(gè)關(guān)鍵碼散列到同一個(gè)基地址提鸟，那么采用這兩種方法還是得到同樣的探查序列，仍然會(huì)產(chǎn)生聚集仅淑。這是因?yàn)閭坞S機(jī)探查和二次探查產(chǎn)生的探查序列只是基地址的函數(shù)称勋，而不是原來(lái)關(guān)鍵碼值的函數(shù)。這個(gè)問(wèn)題稱為二級(jí)聚集( secondary clustering )涯竟。

為了避免二級(jí)聚集赡鲜，我們需要使得探查序列是原來(lái)關(guān)鍵碼值的函數(shù)，而不是基位置的函數(shù)庐船。雙散列探查法利用第二個(gè)散列函數(shù)作為常數(shù)银酬，每次跳過(guò)常數(shù)項(xiàng)，做線性探查醉鳖。

完畢捡硅，感謝您閱讀至此哮内，您的閱讀是我更新的動(dòng)力盗棵！轉(zhuǎn)載請(qǐng)標(biāo)明出處。