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

…

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

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

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

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

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

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

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

m(1≤i<m)其中：

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

m為哈希表長度

di

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

=i線性探測法例題已知哈希表的空間為0-14，將關鍵字序列（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函數(shù)H(k)=k%13和線性探測法處理沖突構造哈希表。（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練習

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

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

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

m其中：di為偽隨機序列。

已知哈希表的空間為0-14，將關鍵字序列（19,14,23,01,68,20,84,27,55,11,10）按哈希函數(shù)H(k)=k%13和二次探測法處理沖突構造哈希表。例題（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

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

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

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

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

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

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

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

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

已知哈希表的空間為0-14，將關鍵字序列（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函數(shù)H(key)=key%13和線性探測法處理沖突構造哈希表，并求出在等概率情況下的查找成功和查找不成功的平均查找長度。練習：（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