第六章哈希表

6.5哈希表6.5哈希表(Hashtable)哈希又稱散列，是一種重要的存儲方法。如何體現(xiàn)記錄在表中的位置與關(guān)鍵字之間的關(guān)系？應(yīng)用搜索引擎中的查找編譯器中的符號表圖論中頂點(diǎn)的非數(shù)值表示與查找在線拼寫檢查

…

為今年招收的<=1000名新生建立查找表，關(guān)鍵字為學(xué)號，值的范圍為j2005000~j2005999。

若以下標(biāo)為000~999的順序表表示。則查找過程可以簡單進(jìn)行：取給定值（學(xué)號）的后三位，便可直接從順序表中找到待查關(guān)鍵字。基本思想以結(jié)點(diǎn)的關(guān)鍵字k為自變量，通過一個確定的哈希函數(shù)H，計算出對應(yīng)的函數(shù)值H(k)，作為結(jié)點(diǎn)的存儲位置并將結(jié)點(diǎn)存入。順序查找、折半查找、樹的查找是建立在比較基礎(chǔ)上的查找，而哈希查找是直接查找。6.5哈希表(Hashtable)沖突和同義詞若某個哈希函數(shù)H對于不同的關(guān)鍵字得到相同的哈希地址，稱為沖突。發(fā)生沖突的這兩個關(guān)鍵字則稱為該哈希函數(shù)的同義詞。6.5哈希表(Hashtable)已知關(guān)鍵字序列為（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k

mod7通過哈希函數(shù)對6個元素建立哈希表：253923914沖突舉例：H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4沖突！0123456在哈希查找方法中，沖突無法完全避免。構(gòu)造好的哈希函數(shù)所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度；所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。制定好的解決沖突的方案查找時，如果從哈希函數(shù)計算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢相關(guān)單元。6.5.1哈希函數(shù)的構(gòu)造方法(1)直接定址法(2)除留余數(shù)法(3)數(shù)字分析法(4)平方取中法(5)折疊法(6)隨機(jī)數(shù)法Hash(k)=a·k+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵字的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突；缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。例：關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(k)=k/100，則存儲結(jié)構(gòu)（哈希表）如下：0123456789900800700500300100（1）直接定址法Hash(k)=kmodp

(p是整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計的哈希表長為m，則一般取p≤m且為質(zhì)數(shù)。（2）除留余數(shù)法用某關(guān)鍵字的某幾位組合成哈希地址。34705243491487348269634852703486305349805834796713473919例：80個關(guān)鍵字。（3）數(shù)字分析法①

第1、2位均是“3和4”，第3位只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅80個），則可取這四位中的任意兩位組合成哈希地址；也可取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。特點(diǎn)：對關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。

例：2589的平方值為6702921，可以取中間的029為地址。（4）平方取中法（5）折疊法特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分，然后疊加求和，并按哈希表表長，取后幾位作為哈希地址。例：元素42751896。用法1：427＋518＋96=1041

用法2：42751896→724+518+69=1311（6）隨機(jī)數(shù)法Hash(k)=random(k)(random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長度不等的情況。優(yōu)點(diǎn)：造表和查找都很方便。6.5.2沖突處理方法（1）開放定址法（開地址法）（2）鏈地址法（拉鏈法）（3）再哈希法（雙哈希函數(shù)法）（4）建立一個公共溢出區(qū)（1）開放定址法（開地址法）線性探測法二次探測法偽隨機(jī)探測法Hi=(Hash(k)+di)mod

m(1≤i<m)其中：

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

m為哈希表長度

di

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

=i線性探測法例題已知哈希表的空間為0-14，將關(guān)鍵字序列（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函數(shù)H(k)=k%13和線性探測法處理沖突構(gòu)造哈希表。（19,14,23,01,68,20,84,27,55,11,10,79）01234567891011121314H(19)=19%13=619H(14)=14%13=114H(23)=23%13=1023H(01)=01%13=1H1=(1+1)%15=21H(68)=68%13=368H(20)=20%13=720H(84)=84%13=6H1=(6+1)%15=7H2=(6+2)%15=884H(27)=27%13=1H1=(1+1)%15=2H2=(1+2)%15=3H3=(1+3)%15=427H(55)=55%13=3H1=(3+1)%15=4H2=(3+2)%15=555H(11)=11%13=1111H1=(10+1)%15=11H2=(10+2)%15=12H(10)=10%13=1010H3=(1+3)%15=4H1=(1+1)%15=2H2=(1+2)%15=3H(79)=79%13=1H4=(1+4)%15=5H5=(1+5)%15=6H6=(1+6)%15=7H7=(1+7)%15=8H8=(1+8)%15=979練習(xí)

已知一組關(guān)鍵字為（39,23,41,38,44,15,68,12,06,51,25），求按哈希函數(shù)H(k)=k%13和線性探測法處理沖突構(gòu)造所得的哈希表HT[0..14]。

012345678910111213143925411568440623381251優(yōu)點(diǎn)：只要哈希表未被填滿，一定能找到一個空地址單元存放沖突元素；缺點(diǎn)：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞。因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，降低查找效率。解決方案：采用二次探測法或偽隨機(jī)探測法。線性探測法優(yōu)缺點(diǎn)二次探測法Hi=(Hash(k)±di)mod

m其中：di為增量序列：12，-12，22，-22，…，q2。偽隨機(jī)探測法Hi=(Hash(k)±di)mod

m其中：di為偽隨機(jī)序列。

已知哈希表的空間為0-14，將關(guān)鍵字序列（19,14,23,01,68,20,84,27,55,11,10）按哈希函數(shù)H(k)=k%13和二次探測法處理沖突構(gòu)造哈希表。例題（19,14,23,01,68,20,84,27,55,11,10）01234567891011121314H(19)=19%13=619H(14)=14%13=114H(23)=23%13=1023H(01)=01%13=1H1=(1+1)%15=201H(68)=68%13=368H(20)=20%13=720H1=(6+1)%15=7H(84)=84%13=6H2=(6-1)%15=584H1=(1+1)%15=2H(27)=27%13=1H2=(1-1)%15=027H1=(3+1)%15=4H(55)=27%13=355H(11)=11%13=1111H2=(10-1)%15=9H1=(10+1)%15=11H(10)=10%13=1010

將所有同義詞結(jié)點(diǎn)鏈接在同一個單鏈表中。若哈希函數(shù)的值域?yàn)?到m-1，將散列表定義為一個由m個頭指針組成的指針數(shù)組HT[m]，凡是散列地址為i的結(jié)點(diǎn)，均插入到以HT[i]為頭指針的單鏈表中。（2）鏈地址法已知哈希表的空間為0-14，將關(guān)鍵字序列（19,14,23,01,68,20,84,27,55,11,10）按哈希函數(shù)H(key)=key%13和鏈地址法處理沖突構(gòu)造所得的哈希表。例題（19,14,23,01,68,20,84,27,55,11,10）0123456789101112H(19)=19%13=6H(14)=14%13=1H(23)=23%13=10H(01)=01%13=1H(68)=68%13=3H(20)=20%13=7H(84)=84%13=6H(27)=27%13=1H(55)=55%13=3H(11)=11%13=11H(10)=10%13=101914230168208427551110^^^^^^^^^^^^^Hi=RHi(k)i=1,2,…,kRHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時就計算另一個哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點(diǎn)：不易產(chǎn)生聚集；缺點(diǎn)：增加了計算時間。（3）再哈希法（雙哈希函數(shù)法）

除設(shè)立哈希基本表外，另設(shè)立一個溢出向量表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。（4）建立一個公共溢出區(qū)6.5.3哈希表的查找及分析

（1）散列函數(shù)沒有“萬能”公式，要根據(jù)元素集合的特性而分別構(gòu)造。

（2）哈希查找的速度是否為真正的O(1)?

不是。由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進(jìn)行比較，用平均查找長度ASL和裝填因子α來衡量。6.5.3哈希表的查找及分析

（1）散列函數(shù)沒有“萬能”公式，要根據(jù)元素集合的特性而分別構(gòu)造。

（2）哈希查找的速度是否為真正的O(1)?

不是。由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進(jìn)行比較，用平均查找長度ASL和裝填因子α來衡量。

已知哈希表的空間為0-14，將關(guān)鍵字序列（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函數(shù)H(key)=key%13和線性探測法處理沖突構(gòu)造哈希表，并求出在等概率情況下的查找成功和查找不成功的平均查找長度。練習(xí)：（19,14,23,01,68,20,84,27,55,11,10,79）1234567891011121314比較次數(shù)H(19)=19%13=619H(14)=14%13=114H(23)=23%13=1023H(01)=01%13=1H1=(1+1)%15=21H(68)=68%13=368H(20)=20%13=720H(84)=84%13=6H1=(6+1)%15=7H2=(6+2)%15=884H(27)=27%13=1H3=(1+3)%15=427H(55)=55%13=3H1=(3+1)%15=4H2=(3+2)%15=555H(11)=11%13=1111H1=(10+1)%15=11H2=(10+2)%15=12H(10)=10%13=1010H2=(1+2)%15=3H(79)=79%13=1H4=(1+4)%15=5H5=(1+5)%15=6H6=(1+6)%15=7H7=(1+7)%15=8H8=(1+8)%15=9791112113431390查找成功時的平均查找長度：查找不成功時的平均查找長度：1234567