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

…

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

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

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

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

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

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

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

m(1≤i<m)其中：

Hash(k)為哈希函數

m為哈希表長度

di

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

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

012345678910111213143925411568440623381251優點：只要哈希表未被填滿，一定能找到一個空地址單元存放沖突元素；缺點：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞。因此，可能出現很多元素在相鄰的哈希地址上“堆積”起來，降低查找效率。解決方案：采用二次探測法或偽隨機探測法。線性探測法優缺點二次探測法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）按哈希函數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

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

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

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

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

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

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

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

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

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