數(shù)據(jù)結(jié)構(gòu)-第9章-查找4-哈希表

第9章查找數(shù)據(jù)結(jié)構(gòu)講義

-哈希表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）54819762121110354819762728519645281976412115281117641291052811176412910（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）54819762121110367811521412910367811521412910前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。理想的情況是希望不經(jīng)過(guò)任何比較，一次便能得到所查記錄。哈希表它既是一種查找方法，又是一種存貯方法9.4哈希查找表哈希表：即散列存儲(chǔ)結(jié)構(gòu)。

散列法存儲(chǔ)的基本思想：建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，或者說(shuō)，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無(wú)關(guān)！例1：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。欲查找學(xué)號(hào)為2001011810216的信息，便可直接訪問(wèn)V[16]！一、哈希表的概念例2：

有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）＝k，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖。（注：H（k）＝k稱為散列函數(shù)）解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，……，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：討論：如何進(jìn)行散列查找？根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式，迅即可查到結(jié)果！例如，查找key=9,則訪問(wèn)H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。

地址…9…11…14…232425…39…內(nèi)點(diǎn)：空間效率低！選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比較，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。若干術(shù)語(yǔ)哈希方法(雜湊法)哈希函數(shù)(雜湊函數(shù))哈希表(雜湊表)

沖突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表)

有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過(guò)哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！

0123456所以，哈希方法必須解決以下兩個(gè)問(wèn)題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。二、哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法除留余數(shù)法

乘余取整法數(shù)字分析法平方取中法折疊法隨機(jī)數(shù)法要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。要求二：無(wú)論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免沖突。Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。例：關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：01234567899008007005003001001、直接定址法Hash(key)=

B*(A*keymod1)

(A、B均為常數(shù)，且0<A<1，B為整數(shù))特點(diǎn)：以關(guān)鍵碼key乘以A，取其小數(shù)部分，然后再放大B倍并取整，作為哈希地址。Hash(key)=keymodp(p是一個(gè)整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取p≤m且為質(zhì)數(shù)

（也可以是不包含小于20質(zhì)因子的合數(shù)）。3、乘余取整法2、除留余數(shù)法（A*keymod1）就是取A*key的小數(shù)部分例：欲以學(xué)號(hào)最后兩位作為地址，則哈希函數(shù)應(yīng)為：

H(k)=100*(0.01*k%1)其實(shí)也可以用法2實(shí)現(xiàn)：H(k)=k%100特點(diǎn)：某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：4、數(shù)字分析法討論：①第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號(hào)：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅80個(gè)），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。特點(diǎn)：對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。6、折疊法特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長(zhǎng)，取后幾位作為哈希地址。適用于：每一位上各符號(hào)出現(xiàn)概率大致相同的情況。法1：移位法──將各部分的最后一位對(duì)齊相加。法2：間界疊加法──從一端向另一端沿分割界來(lái)回折疊后，最后一位對(duì)齊相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13115、平方取中法7、隨機(jī)數(shù)法Hash(key)=random(key)(random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。①執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；②關(guān)鍵字的長(zhǎng)度；③哈希表的大?。虎荜P(guān)鍵字的分布情況；⑤查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：三、沖突處理方法常見的沖突處理方法有：開放定址法（開地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數(shù)法）建立一個(gè)公共溢出區(qū)1、開放定址法（開地址法）設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。具體實(shí)現(xiàn)：Hi=(Hash(key)+di)modm(1≤i<m)

其中：

Hash(key)為哈希函數(shù)

m為哈希表長(zhǎng)度

di

為增量序列1，2，…m-1，且di=i

1.線性探測(cè)法含義：一旦沖突，就找附近（下一個(gè)）空地址存入。關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長(zhǎng)為m=11；

哈希函數(shù)為Hash(key)=keymod11；

擬用線性探測(cè)法處理沖突。建哈希表如下：解釋：①47、7（以及11、16、92）均是由哈希函數(shù)得到的沒有沖突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入。③另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3

還連續(xù)移動(dòng)了兩次（二次聚集）線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。解決方案：可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問(wèn)題。討論：仍舉上例，改用二次探測(cè)法處理沖突，建表如下：012345678910112234792167298△▲△△注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。

2.二次探測(cè)法Hi=(Hash(key)±di)modm其中：Hash(key)為哈希函數(shù)

m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3的質(zhì)數(shù)；

di為增量序列

12，-12，22，-22，…，q2

3.若di＝偽隨機(jī)序列，就稱為偽隨機(jī)探測(cè)法2、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來(lái)，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。設(shè){47,7,29,11,16,92,22,8,3,50,37,89

}的哈希函數(shù)為：Hash(key)=keymod11，用拉鏈法處理沖突，則建表如右圖所示。

例：

01234567891022118934737922971650810

注：有沖突的元素可以插在表尾,也可以插在表頭3、再哈希法（雙哈希函數(shù)法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時(shí)就計(jì)算另一個(gè)哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點(diǎn)：不易產(chǎn)生聚集；缺點(diǎn)：增加了計(jì)算時(shí)間。4.建立一個(gè)公共溢出區(qū)思路：除設(shè)立哈?；颈硗?，另設(shè)立一個(gè)溢出向量表。 所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。四、哈希表的查找及分析明確：散列函數(shù)沒有“萬(wàn)能”通式，要根據(jù)元素集合的特性而分別構(gòu)造。算法：見教材P259討論：哈希查找的速度是否為真正的O（1）？不是。由于沖突的產(chǎn)生，使得哈希表的查找過(guò)程仍然要進(jìn)行比較，仍然要以平均查找長(zhǎng)度ASL來(lái)衡量。一般地，ASL依賴于哈希表的裝填因子

,它標(biāo)志著哈希表的裝滿程度。

越大，表中記錄數(shù)越多，說(shuō)明表裝得越滿，發(fā)生沖突的可能性就越大，查找時(shí)比較次數(shù)就越多。0≤≤1討論：2）“沖突”是不是特別討厭？答：不一定！正因?yàn)橛袥_突，使得文件加密后無(wú)法破譯（不可逆，是單向散列函數(shù)，可用于數(shù)字簽名）。利用了哈希表性質(zhì)：源文件稍稍改動(dòng)，會(huì)導(dǎo)致哈希表變動(dòng)很大。1）散列存儲(chǔ)的查找效率到底是多少？答：ASL與裝填因子有關(guān)！既不是嚴(yán)格的O(1)，也不是O(n)應(yīng)盡量選擇一個(gè)合適的，以降低ASL的長(zhǎng)度練習(xí):給定關(guān)鍵字序列11，78，10，1，3，2，4，21，試分別用順序查找、二分查找、二叉排序樹查找、散列查找(用線性探查法和拉鏈法)來(lái)實(shí)現(xiàn)查找，試畫出它們的對(duì)應(yīng)存儲(chǔ)形式(順序查找的順序表，二分查找的判定樹，二叉排序樹查找的二叉排序樹及兩種散列查找的散列表)，并求出每一種查找的成功平均查找長(zhǎng)度。散列函數(shù)H(k)=k%11。順序查找的成功平均查找長(zhǎng)度為：ASL=(1+2+3+4+5+6+