哈希表查找課件

知識回顧：上堂課我們學(xué)習(xí)了三種查找方法：新課引入：理想的情況是依據(jù)關(guān)鍵碼直接得到其對應(yīng)的數(shù)據(jù)元素存儲位置，本堂課要講的哈希表查找方法就屬于此情況。順序查找：折半查找：上述三種查找方法都是建立在比較基礎(chǔ)之上的，查找效率由比較一次后縮小的查找范圍決定。分塊查找：什么是哈希表9.3.19.3哈希表

主要內(nèi)容

哈希函數(shù)的構(gòu)造方法9.3.2處理沖突的方法9.3.3哈希表的查找及其分析9.3.49.3.1什么是哈希表【例】關(guān)鍵碼序列為{18，27，1，20，22，6，10，13，41，15，25}。設(shè)關(guān)鍵碼與元素存儲位置的函數(shù)為f(key)=keymod11。

選取某個函數(shù)f(key)

，依該函數(shù)關(guān)鍵碼計算元素的存儲位置，并按此存放；查找時，用同一個函數(shù)對給定值kx計算地址，將kx與地址單元中元素關(guān)鍵字進(jìn)行比較，確定查找是否成功，這就是哈希方法，哈希方法中使用的轉(zhuǎn)換函數(shù)f(key)稱為哈希函數(shù)，按這個思想構(gòu)造的表稱為哈希表。則這11個元素通過f(key)函數(shù)映射可建立如下的查找表：22113251527618412010012345678910“沖突”現(xiàn)象：即key1≠key2，而f(key1)=f(key2)。同義詞：產(chǎn)生“沖突”現(xiàn)象的詞。由于改進(jìn)哈希函數(shù)只能減少沖突，不能避免沖突，因此，哈希方法需解決以下二個問題：2）選擇一種好的處理沖突方法1）構(gòu)造“好”的哈希函數(shù)所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換效率。所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址中大致均勻分布，以減少空間浪費(fèi)。9.3.2哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)有：1.直接定址法5.除留余數(shù)法2.數(shù)字分析法(略)

3.平方取中法

(略)4.折疊法

(略)

6.隨機(jī)數(shù)法(略)

1.直接定址法哈希函數(shù)為關(guān)鍵碼的線性函數(shù)，即：H(key)=a×key+b(a，b為常數(shù))?！纠?-6】若key={100,300,500,700,800,900}H(key)=key/100，1003005007008009000123456789則關(guān)鍵碼存儲格式如下：5.除留余數(shù)法H(key)=keyMODp(p是一個整數(shù))關(guān)鍵問題是：如何選取p?一般情況?？梢赃xp為不大于表長m

的質(zhì)數(shù)，或者是不包含小于20的質(zhì)因子的合數(shù)。例如：關(guān)鍵碼key=12,39,18,24,33,21時，若取p=9。則關(guān)鍵碼的地址如下所示：出現(xiàn)的問題：使所有含質(zhì)因子3的關(guān)鍵字均映射到地址3,6上，從而增加了“沖突”現(xiàn)象。1812,39,2124,3301234567899.3.3處理沖突的方法處理沖突：是指為產(chǎn)生沖突的地址尋找下一個空的哈希地址。方法有：開放定址法、再哈希法、拉鏈法、建立一個公共溢出區(qū)。開放定址法：為產(chǎn)生沖突的地址H(key)求得一個探測地址序列：

H0,H1,H2,…,Hs（1≤s≤m-1）。其中：

H0=H(key)，Hi=(H(key)+di)MODmi=1,2,…,s。增量di有四種取法：（1）線性探測法（2）二次（平方）探測法（3）哈希函數(shù)探測法（略）（4）隨機(jī)函數(shù)探測法（略）（1）線性探測法：di=c*i最簡單的情況c=1【例9-7】

key={47,7,29,11,16,92,22,8,3}，哈希表長度為11，H(key)=keymod11，用線性探測法處理沖突，建表如下：012345678910112247921637298（2）二次（平方）探測法：di=12,-12,22,-22,…,【例9-8】仍以上述例子用二次探測法處理沖突，建表如下：01234567891011223479216

72983.鏈地址法

將所有哈希地址相同的關(guān)鍵碼都鏈接在同一鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間[0，m-1]上，則設(shè)立一個指針型向量DataType*Hash[m]其每一個分量的初始狀態(tài)都是空指針。凡哈希地址為i的記錄都插入到頭指針為Hash[i]的鏈表中。插入位置可以在表尾、表頭、或表中，以保持同義詞在同一線性鏈表中按關(guān)鍵碼有序。2.再哈希法Hi=RHi(key)i=1,2,…,kRHi為不同的哈希函數(shù)，即在同義詞發(fā)生地址沖突時計算另一個哈希函數(shù)地址，直至沖突不再發(fā)生?？偨Y(jié)：線性探測容易產(chǎn)生二次聚集，鏈地址肯定不會產(chǎn)生二次聚集。一次聚集的產(chǎn)生主要取決于哈希函數(shù)，在哈希函數(shù)均勻的前提下，可以認(rèn)為沒有一次聚集?！纠?-3】設(shè)

key={19,14,23,01,68,20,84,27,55,11,10,79}按哈希函數(shù)為：H(key)=keymod13和鏈地址法處理沖突構(gòu)造所得的哈希表如下：解：由已知條件可得每個關(guān)鍵碼的哈希地址為：6,1,10,1,3,7,6,1,3,11,10,1。0∧01142779556819111023∧∧∧∧∧∧∧∧∧∧∧∧12345679810111284209.3.4哈希表的查找及其分析

查找過程和造表過程一致。由于“沖突”的產(chǎn)生，使得哈希表的查找過程仍然是一個給定值和關(guān)鍵字進(jìn)行比較的過程。因此，仍需以ASL作為衡量哈希表查找效率的量度。決定哈希表查找的ASL的因素：1.選用的哈希函數(shù);2.選用的處理沖突的方法;3.哈希表飽和的程度，裝載因子α=n/m值的大小

一般情況，可認(rèn)為選用的哈希函數(shù)是“均勻”的，則在討論ASL時，可以不考慮它的因素。哈希表的ASL是處理沖突方法和裝載因子的函數(shù)。

可以證明查找成功時有下列結(jié)果（見P261）

線性探測再散列平均查找長度為Snl=

隨機(jī)探測再散列