數(shù)據(jù)結(jié)構(gòu) 課件 11-4散列查找

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)領(lǐng)域本科教育教學(xué)改革試點(diǎn)工作計(jì)劃（“101計(jì)劃”）研究成果10111.4散列查找第11章

查找11.4.1散列函數(shù)11.4.2散列沖突解決方法11.4.3散列查找算法11.4.4查找性能分析11.4.5分布式散列表11.4.6作業(yè)11.4.1散列函數(shù)11.4散列查找順序查找：O(n),平均約比較500次索引查找：由索引表決定4有沒有效率更高的算法？取給定學(xué)號(hào)的后三位，不需要經(jīng)過比較，便可直接從查找表中找到給定學(xué)生的記錄。關(guān)鍵字存儲(chǔ)地址映射關(guān)系11.4散列查找一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以H(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個(gè)函數(shù)h(key)為散列函數(shù)。散列函數(shù)定義11.4散列查找11.4散列查找71)散列函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可；11.4散列查找81)散列函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可；2)由于散列函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1

key2，而h(key1)=h(key2)。H(key)=key%103)很難找到一個(gè)不產(chǎn)生沖突的散列函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)纳⒘泻瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，散列查找需要做兩方面事情：選擇一個(gè)“好”的散列函數(shù)；提供一種“處理沖突”的方法。1)散列函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可；2)由于散列函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1

key2，而h(key1)=h(key2)。11.4散列查找11.4散列查找散列表10根據(jù)設(shè)定的散列函數(shù)H(key)

和提供的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)地址連續(xù)的地址空間上，并以關(guān)鍵字在地址空間中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之為散列表。沖突處理C(key)地址空間存儲(chǔ)的數(shù)據(jù)集合稱為散列表11.4散列查找好的散列函數(shù)？11.4.1常見的散列函數(shù)散列函數(shù)11.4散列查找一般來說，一個(gè)好的散列函數(shù)應(yīng)滿足下列兩個(gè)條件：（1）計(jì)算簡單（2）沖突少12散列函數(shù)11.4散列查找常見的散列函數(shù)構(gòu)造方法有：直接散列函數(shù)數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機(jī)數(shù)法1311.4散列查找散列地址010203……22……出生年份194919501951……1970……出生人數(shù)××××××××××××……××××……14H（key）=key+（-1948）解放后每年出生人數(shù)的統(tǒng)計(jì)：11.4散列查找散列地址010203……22……出生年份194919501951……1970……出生人數(shù)××××××××××××……××××……1）直接散列函數(shù)：H（key）=key+（-1948）解放后每年出生人數(shù)的統(tǒng)計(jì)：取關(guān)鍵字本身或關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址，即：H（key）=key或H（key）=a*key+b（a，b為常數(shù)）。11.4散列查找n=80,d=8,r=10,s=21，2，3，8位分布不均勻，不能取?？扇〉?、6兩位組成的2位十進(jìn)制數(shù)作為每個(gè)數(shù)據(jù)的散列地址，則圖中列出的關(guān)鍵字的散列地址分別為：45，72，84，03，28，39，51，65，1311.4散列查找設(shè)ｎ個(gè)ｄ位數(shù)的關(guān)鍵字，由ｒ個(gè)不同的符號(hào)組成，此ｒ個(gè)符號(hào)在關(guān)鍵字各位出現(xiàn)的頻率不一定相同，可能在某些位上均勻分布，即每個(gè)符號(hào)出現(xiàn)的次數(shù)都接近于ｎ／ｒ次，而在另一些位上分布不均勻。則選擇其中分布均勻的s位作為散列地址，即H（key）=“key中數(shù)字均勻分布的s位”172）

數(shù)字分析法n=80,d=8,r=10,s=21，2，3，8位分布不均勻，不能取?？扇〉?、6兩位組成的2位十進(jìn)制數(shù)作為每個(gè)數(shù)據(jù)的散列地址，則圖中列出的關(guān)鍵字的散列地址分別為：45，72，84，03，28，39，51，65，1311.4散列查找數(shù)據(jù)關(guān)鍵字(關(guān)鍵字)2散列地址(217~29)A01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314Q121614734741734Q221624741304741Q321634745651745183）平方取中法其中，所取的位數(shù)由散列表的大小確定取關(guān)鍵字平方后的中間幾位作為散列地址，即散列函數(shù)為：H（key）=“key2的中間幾位”11.4散列查找19以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”和“貢獻(xiàn)均衡”。即：關(guān)鍵字的各位都在平方值的中間幾位有所貢獻(xiàn)，Hash值中應(yīng)該有各位影子。平方取中法思想11.4散列查找關(guān)鍵字位數(shù)特別多，怎么辦？11.4散列查找關(guān)鍵字位數(shù)較長時(shí)，可將關(guān)鍵字分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以不同），取這幾部分的疊加和（舍去高位的進(jìn)位）作為散列地址。位數(shù)由存儲(chǔ)地址的位數(shù)確定。疊加時(shí)有兩種方法：移位疊加法，即將每部分的最后一位對(duì)齊，然后相加；邊界疊加法，即把關(guān)鍵字看作一紙條，從一端向另一端沿邊界逐次折疊，然后對(duì)齊相加。4）折疊法此方法適合于:關(guān)鍵字的數(shù)字位數(shù)特別多。11.4散列查找取關(guān)鍵字被某個(gè)不大于散列表長度m的數(shù)p除后的余數(shù)作為散列地址，即：H（key）=keyMODp(p≤m)22其中p的選擇很重要，如果選得不好會(huì)產(chǎn)生很多沖突。比如關(guān)鍵字都是10的倍數(shù)，而p=10一般取小于表長的最大質(zhì)數(shù)5）除留余數(shù)法例p=2111.4散列查找選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值作為散列地址，即：H（key）=random（key）其中random為隨機(jī)函數(shù)。236）

隨機(jī)數(shù)法實(shí)際工作中需根據(jù)不同的情況采用不同的散列函數(shù)。通常需要考慮的因素有：計(jì)算散列函數(shù)所需時(shí)間；關(guān)鍵字的長度；散列表的大??；關(guān)鍵字的分布情況；記錄的查找頻率。11.4散列查找建立散列表如果遇到兩個(gè)相同關(guān)鍵字的情況怎么辦？有可能有兩個(gè)相同關(guān)鍵字嗎？11.4.2沖突處理11.4散列查找沖突：是指由關(guān)鍵字得到的Hash地址上已有其他記錄。好的散列函數(shù)可以減少?zèng)_突，但很難避免沖突。沖突處理：為出現(xiàn)散列地址沖突的關(guān)鍵字尋找下一個(gè)散列地址。11.4散列函數(shù)常見的沖突處理方法有：開放地址法再散列法鏈地址法公共溢出區(qū)法11.4散列函數(shù)為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODm

i=1,2,…,s其中:Hi為第i次沖突的地址，i=1,2,…,s

H（key）為Hash函數(shù)值

m為Hash表表長

di

為增量序列1）開放地址法對(duì)增量di

有三種取法：1)線性探測再散列

di=c

i

最簡單的情況c=12)平方探測再散列

di=12,-12,22,-22,…,或者di=12,22,32,…3)隨機(jī)探測再散列

di

是一組偽隨機(jī)數(shù)列1）開放地址法11.4散列查找11.4散列查找29例表長為11的散列表中已填有關(guān)鍵字為17，60，29的記錄，

H(key)=keyMOD11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突38(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6沖突

H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設(shè)偽隨機(jī)數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突382）再散列法將n個(gè)不同散列函數(shù)排成一個(gè)序列,當(dāng)發(fā)生沖突時(shí),由RHi確定第i次沖突的地址Hi。即：Hi=RHi(key)i=1,2,…,n其中：RHi為不同散列函數(shù)這種方法不會(huì)產(chǎn)生“聚類”，但會(huì)增加計(jì)算時(shí)間。11.4散列查找11.4散列查找31將所有散列地址相同的記錄都鏈接在同一鏈表中。01234560119822311685514

36

關(guān)鍵字集合為{19,01,23,14,55,68,11,82,36}，散列函數(shù)為H(key)=keyMOD73）鏈地址法：假設(shè)某散列函數(shù)的值域[0,m-1]，向量HashTable[0,m-1]為基本表，每個(gè)分量存放一個(gè)記錄，另設(shè)一個(gè)向量OverTable[0,v]為溢出表。將與基本表中的關(guān)鍵字發(fā)生沖突的所有記錄都填入溢出表中。如一組關(guān)鍵字序列為{19，14，23，01，68，20，84，27，55，11，10，79}，散列函數(shù)為H（key）=keymod13，采用公共溢出區(qū)法得到的結(jié)果為：4)公共溢出區(qū)法11.4散列查找11.4.3散列表查找算法11.4散列查找在散列表上查找的過程和散列造表的構(gòu)造過程基本一致。1）給定K值，根據(jù)構(gòu)造表時(shí)所用的散列函數(shù)求散列地址j，2）若此位置無記錄,則查找不成功；否則比較關(guān)鍵字，若和給定的關(guān)鍵字相等則成功；否則根據(jù)構(gòu)造表時(shí)設(shè)定的沖突處理的方法計(jì)算“下一地址”，重復(fù)2）3311.4散列查找存在沖突檢測與處理的散列查找流程圖InputkPos=H(k)Pos==NULL?key==kfailsuccesscollisionYNYN沖突處理11.4散列查找關(guān)鍵字序列為：{19，14，23，01，68，20，84，27，55，11，10，79}散列函數(shù)為H（key）=keymod13采用線性探測處理沖突35Key=84散列地址H(84)=6，因?yàn)閑.data[6]不空，且e.data[6].key=19≠84，沖突沖突處理H1=(6+1)MOD13=7，e.data[7]不空，且e.data[7].key=20≠84,沖突沖突處理H2=(6+2)MOD13=8，e.data[8]不空，且e.elem[8].key=84，查找成功，返回?cái)?shù)據(jù)在散列表中的序號(hào)8。建立散列查找表如下：請(qǐng)查找關(guān)鍵字為84的記錄散列表查找與插入算法舉例11.4散列查找關(guān)鍵字序列為：{19，14，23，01，68，20，84，27，55，11，10，79}散列函數(shù)為H（key）=keymod13采用線性探測處理沖突36Key=38散列地址H(38)=12，因?yàn)閑.data[12]不空，且e.data[12].key=10≠38,沖突沖突處理H1=(12+1)MOD13=0，由于e.data[0]沒有存放數(shù)據(jù)，表明散列表中不存在關(guān)鍵字為38的記錄，查找失敗。建立散列查找表如下：請(qǐng)查找關(guān)鍵字為38的記錄散列表查找與插入算法舉例例題:關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)190123145568若采用線性探測再散列處理沖突118236112136251請(qǐng)求出解決沖突的查找成功的ASL和查找失敗的ASL11.4散列查找例題:關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)190123145568若采用線性探測再散列處理沖突118236112136251ASL(成功)=(1+1+2+1+3+6+2+5+1)/9=22/911.4散列查找例題:關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)190123145568若采用線性探測再散列處理沖突118236112136251ASL(失敗)=？ASL(失?。?（9+8+7+6+5+4+3+2+1）/11=45/1111.4散列查找1901231468若采用二次探測再散列處理沖突55118236112131441例題:關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)11.4散列查找1901231468若采用二次探測再散列處理沖突55118236112131441課堂練習(xí):關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)ASL(成功)=？ASL(成功）=（1+1+2+1+3+1+4+4+1）/9=211.4散列查找ASL(失敗)=？437654321001901231468若采用二次探測再散列處理沖突55118236112131441課堂練習(xí):關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)11.4散列查找190123145568若采用隨機(jī)數(shù)處理沖突，隨機(jī)數(shù)假設(shè)為9118236111115122課堂練習(xí):關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)11.4散列查找190123145568若采用隨機(jī)數(shù)處理沖突，隨機(jī)數(shù)假設(shè)為9118236111115122課堂練習(xí):關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)ASL(成功)=？ASL(成功）=（1+1+1+1+1+5+1+2+2）/9=5/311.4散列查找190123145568若采用隨機(jī)數(shù)處理沖突，隨機(jī)數(shù)假設(shè)為9118236111115122課堂練習(xí):關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定散列函數(shù)H(key)=keyMOD11(表長=11)35461521324ASL(失敗)=？ASL(失?。?（3+5+4+6+1+5+2+1+3+2+4）/11=36/1111.4散列查找將所有散列地址相同的記錄都鏈接在同一鏈表中。01234560119822311685514

36

鏈地址法：ASL(成功)=(6×1+2×2+3)/9=13/9ASL(失敗)=(4×1+2+3)/7=9/7關(guān)鍵字集合為{19,01,23,14,55,68,11,82,36}，散列函數(shù)為H(key)=keyMOD711.4散列查找11.4散列查找查找性能分析一般情況下，可以認(rèn)為選用的散列函數(shù)是“均勻”的，則在討論ASL時(shí)，可以不考慮散列函數(shù)的因素。例如：關(guān)