數(shù)據(jù)結(jié)構(gòu)與算法課件：DS10_查找23

1、2022/7/18第23講 散列檢索本講主要內(nèi)容10.3.0 散列中的基本問(wèn)題10.3.1 散列函數(shù)10.3.2 開(kāi)散列方法10.3.3 閉散列方法10.3.4 閉散列表的算法實(shí)現(xiàn)10.3.5 散列方法的效率分析碰撞的處理2022/7/1810.3.0 散列中的基本問(wèn)題基于關(guān)鍵碼比較的檢索 順序檢索，=, !=二分法、樹(shù)型 , = , 檢索是直接面向用戶(hù)的操作當(dāng)問(wèn)題規(guī)模n很大時(shí)，上述檢索的時(shí)間效率可能使得用戶(hù)無(wú)法忍受最理想的情況根據(jù)關(guān)鍵碼值，直接找到記錄的存儲(chǔ)地址不需要把待查關(guān)鍵碼與候選記錄集合的某些記錄進(jìn)行逐個(gè)比較2022/7/18由數(shù)組的直接尋址想到的例如，讀取指定下標(biāo)的數(shù)組元素根據(jù)數(shù)組的

2、起始存儲(chǔ)地址、以及數(shù)組下標(biāo)值而直接計(jì)算出來(lái)的，所花費(fèi)的時(shí)間是O(1)與數(shù)組元素個(gè)數(shù)的規(guī)模n無(wú)關(guān)受此啟發(fā)，計(jì)算機(jī)科學(xué)家發(fā)明了散列方法（Hash, 有人稱(chēng)“哈?！?，還有稱(chēng)“雜湊”）散列是一種重要的存儲(chǔ)方法也是一種常見(jiàn)的檢索方法2022/7/18散列基本思想一個(gè)確定的函數(shù)關(guān)系h以結(jié)點(diǎn)的關(guān)鍵碼K為自變量函數(shù)值h(K)作為結(jié)點(diǎn)的存儲(chǔ)地址檢索時(shí)也是根據(jù)這個(gè)函數(shù)計(jì)算其存儲(chǔ)位置通常散列表的存儲(chǔ)空間是一個(gè)一維數(shù)組散列地址是數(shù)組的下標(biāo)2022/7/18例子1已知線性表關(guān)鍵碼集合為：S = and, array, begin, do, else, end, for, go, if, repeat, then, un

3、til, while, with可設(shè)散列表為：char HT2268;散列函數(shù)H(key)的值，取為關(guān)鍵碼key中的第一個(gè)字母在字母表a, b, c, ., z中的序號(hào)，即：H(key)=key0 a2022/7/18例子1（續(xù)）2022/7/18例子2修改散列函數(shù)：散列函數(shù)的值為key中首尾字母在字母表中序號(hào)的平均值，即：int H3(char key) int i = 0; while (i8) & (keyi!=0) i+; return(key0 + key(i-1) 2*a) /2 )2022/7/18例子2（續(xù)）2022/7/18幾個(gè)重要概念負(fù)載因子 =n/m散列表的空間大小為m填

4、入表中的結(jié)點(diǎn)數(shù)為n沖突某個(gè)散列函數(shù)對(duì)于不相等的關(guān)鍵碼計(jì)算出了相同的散列地址在實(shí)際應(yīng)用中，不產(chǎn)生沖突的散列函數(shù)極少存在同義詞發(fā)生沖突的兩個(gè)關(guān)鍵碼2022/7/182022/7/1810“生日悖論”1939年，H.Davenport提出“生日悖論”斷言：房間內(nèi)有23人，其兩人生日不同的概率為:0.4927若增加17人，則兩人生日不同的概率降低:10倍（降低為原先的1/10）2022/7/182022/7/1811“生日悖論”當(dāng)n=23發(fā)生的概率大約是0.507。 其他數(shù)字的概率見(jiàn)下表：2022/7/18要選定“好”的散列函數(shù)能將關(guān)鍵字均勻影射到哈?？臻g上計(jì)算哈希函數(shù)簡(jiǎn)單高效有好的解決沖突的方法要設(shè)

5、定處理沖突的方法 2022/7/18構(gòu)造散列函數(shù)的方法 直接定址法 數(shù)值分析法 平方取中法 折疊法 基數(shù)轉(zhuǎn)換法除留余數(shù)法 2022/7/18直接定址法取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。H(key)key或H(key)akey+b 其中，a和b為常數(shù)，調(diào)整 a與b的值可以使哈希地址取值范圍與存儲(chǔ)空間范圍一致。 地址 0 1 51年份 1949 1950 2000人數(shù) 關(guān)鍵字是年份，散列函數(shù)取關(guān)鍵字的線性函數(shù)： H(key)=key+(-1949) 優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低2022/7/18特征位抽取法（數(shù)值分析法

6、） 構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例 有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù) 8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析： 只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位 與另兩位的疊加作哈希地址假設(shè)表長(zhǎng)為l00，則可取兩位十進(jìn)制數(shù)(0099)組

7、成散列地址，取哪兩位?原則是使得到的散列地址盡量避免產(chǎn)生沖突2022/7/18數(shù)字分析法（續(xù)1）計(jì)算各位數(shù)字中符號(hào)分布的均勻度 k 的公式其中， 表示第 i 個(gè)符號(hào)在第 k 位上出現(xiàn)的次數(shù)n/r 表示各種符號(hào)在 n 個(gè)數(shù)中均勻出現(xiàn)的期望值計(jì)算出的 k 值越小，表明在該位 (第k 位)各種符號(hào)分布得越均勻2022/7/18數(shù)字分析法（續(xù)2）位，僅9出現(xiàn)8次， 1 =(8-8/10)21+(0-8/10)2 9=57.6位，僅9出現(xiàn)8次， 2 =(8-8/10)21+(0-8/10)2 9=57.6 位，0和2各出現(xiàn)兩次，1出現(xiàn)4次 3 =(2-8/10)22+(4-8/10)2 1+ (0-8/

8、10)2 7 =17.6位，0和5各出現(xiàn)兩次，1、2、6、8各出現(xiàn)1次位，0和4各出現(xiàn)兩次，2、3、5、6各出現(xiàn)1次位，7和8各出現(xiàn)兩次，0、1、5、9各出現(xiàn)1次 4 = 5 = 6 = (2-8/10)22+(1-8/10)2 4+(0-8/10)2 4 =5.62022/7/18數(shù)字分析法（續(xù)3）若散列表地址范圍有 3 位數(shù)字, 取各關(guān)鍵碼的位做為記錄的散列地址也可以把第，和第位相加，舍去進(jìn)位，變成一位數(shù)，與第，位合起來(lái)作為散列地址。還可以用其它方法 9 9 2 1 4 8 位， 1 = 57.60 9 9 1 2 6 9位， 2 = 57.60 9 9 0 5 2 7位， 3 = 17.

9、60 9 9 1 6 3 0位， 4 = 5.60 9 9 1 8 0 5位， 5 = 5.60 9 9 1 5 5 8位， 6 = 5.60 9 9 2 0 4 7 9 9 0 0 0 1 符號(hào)分布的均勻度2022/7/18數(shù)字分析法（續(xù)4）數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況它完全依賴(lài)于關(guān)鍵碼集合如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位數(shù)據(jù)要重新決定2022/7/18平方取中法 特點(diǎn)：對(duì)關(guān)鍵碼平方后，按哈希表大小(即長(zhǎng)度為散列表表長(zhǎng)) ，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。 例：2589的平方值為6702921，可以取中間的029為地址。

10、2022/7/18折疊法 折疊法是將較長(zhǎng)的關(guān)鍵字從左到右分割成位數(shù)相同的幾段(最后一段的位數(shù)可以少一些)，然后把這幾段疊加并舍去進(jìn)位，得到的結(jié)果作為散列地址。這種方法適用于關(guān)鍵字位數(shù)很多，而且每一位的數(shù)字分布大致均勻的情況。 種類(lèi)：1）移位疊加：將分割后的幾部分低位對(duì)齊相加2）間界疊加：從一端沿分割界來(lái)回折送，然后對(duì)齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況2022/7/18例1.關(guān)鍵字為 ：0442205864，哈希地址位數(shù)為45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=609

11、2間界疊加例2.關(guān)鍵字為 ：x=12320324111220，哈希地址位數(shù)為3從左到右按3個(gè)位數(shù)段分割，共得到5個(gè)段：123、203、241、112、20。采用移位疊加得到： A(x)123+203+241+112+20699若采用間界疊加，則從左到右來(lái)回折疊中，第二、四段反轉(zhuǎn)為302和211得到： B(x)123+302+241+211+20897 2022/7/18基數(shù)轉(zhuǎn)換法把關(guān)鍵碼看成是另一進(jìn)制上的數(shù)后再把它轉(zhuǎn)換成原來(lái)進(jìn)制上的數(shù)取其中若干位作為散列地址一般取大于原來(lái)基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)要互素2022/7/18例：基數(shù)轉(zhuǎn)換法例如，給定一個(gè)十進(jìn)制數(shù)的關(guān)鍵碼是(210485)1

12、0，把它看成以13為基數(shù)的十三進(jìn)制數(shù)(210485)13 ，再把它轉(zhuǎn)換為十進(jìn)制 (210485)13 = 2135 + 1134 + 4132 + 813 + 5 = (771932)10假設(shè)散列表長(zhǎng)度是10000，則可取低4位1932作為散列地址2022/7/18除留余數(shù)法 除留余數(shù)法采用取模運(yùn)算(%)，把關(guān)鍵字除以某個(gè)不大于散列表表長(zhǎng)的整數(shù)得到的余數(shù)作為散列地址。散列函數(shù)形式為：H(key)=keyp pm注意：如果p選不好，就容易產(chǎn)生同義詞。特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取pm的最大質(zhì)數(shù)2022/7/18散列函數(shù)的應(yīng)用在

13、實(shí)際應(yīng)用中應(yīng)根據(jù)關(guān)鍵碼的特點(diǎn)，選用適當(dāng)?shù)纳⒘泻瘮?shù)有人曾用“輪盤(pán)賭”的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析，結(jié)論是平方取中法最接近于“隨機(jī)化”若關(guān)鍵碼不是整數(shù)而是字符串時(shí)，可以把每個(gè)字符串轉(zhuǎn)換成整數(shù)，再應(yīng)用平方取中法2022/7/18有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7通過(guò)哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！ 0 1 2 3 4 5 62022/7/18哈希沖突的解決方法 主要介紹：閉

14、散列法（開(kāi)放地址法）當(dāng)發(fā)生沖突時(shí)，在沖突位置的前后附近尋找可以存放記錄的空閑單元。 開(kāi)散列法（鏈地址法） 2022/7/18閉散列法 基本思想：所有元素存儲(chǔ)在散列表數(shù)組中。元素經(jīng)散列函數(shù)計(jì)算出來(lái)的地址稱(chēng)為基地址。若插入元素x，而x的基地址已被某個(gè)同義詞占用，則根據(jù)某種策略將x存儲(chǔ)在數(shù)組的另一個(gè)位置。探測(cè)：尋找“下一個(gè)”空位的過(guò)程稱(chēng)為探測(cè)探測(cè)地址：Hi( H(key)+di) m i=1,2,k (km-1) m為表長(zhǎng)， di為增量線性探測(cè)再散列 (di=1,2,3,m-1)二次探測(cè)再散列 (di=12，-12，22，-22，k2 km/2) 雙重散列法（隨機(jī)數(shù)法） 2022/7/18線性探測(cè)法

15、基本思想：當(dāng)發(fā)生沖突時(shí)，從沖突位置的下一個(gè)單元順序?qū)ふ铱纱娣庞涗浀目諉卧?，只要找到一個(gè)空位，就把元素放入此空位中。順序查找時(shí)，我們把散列表看成一個(gè)循環(huán)表，即如果到最后一個(gè)位置也沒(méi)有找到空單元，則回到表頭開(kāi)始繼續(xù)查找。此時(shí)，如果仍然未找到空位，則說(shuō)明散列表已滿(mǎn)，需要進(jìn)行溢出處理。 2022/7/18線性探測(cè)法示例關(guān)鍵字為(13,19,39,24,28,57,76,51,84)，散列表長(zhǎng)m=13，散列函數(shù)為H(key)=key%11 0 1 2 3 4 5 6 7 8 9 10 11 121339191111324391912111324392819121212022/7/18線性探測(cè)法示例(續(xù))

16、繼續(xù)插入 57,76,51,841324573928191231210 1 2 3 4 5 6 7 8 9 10 11 121324573928197612312111324573928195176123121311324573928195176841231213152022/7/18線性探測(cè)法的ASLASLSUCC=1/9*(4*1+2*2+2*3+1*5)=19/9ASLUNSUCC =1/13*(1+1+4+3+2+1+7+6+5+4+3+2+1) =40/132022/7/18關(guān)于探查序列插入和檢索函數(shù)都假定每個(gè)關(guān)鍵碼的探查序列中至少有一個(gè)存儲(chǔ)位置是空的否則可能會(huì)進(jìn)入一個(gè)無(wú)限循環(huán)中也可

17、以限制探查序列長(zhǎng)度2022/7/18線性探測(cè)法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單，只要有空位，就可將元素存入缺點(diǎn)：容易產(chǎn)生“二次聚集”：不同基地址的元素爭(zhēng)奪同一個(gè)單元的現(xiàn)象叫作“二次聚集”。平均查找長(zhǎng)度大。 2022/7/18二次探測(cè)法 加大探測(cè)序列的步長(zhǎng)，使發(fā)生沖突的元素的位置比較分散 ,步長(zhǎng) di=12，-12，22，-22，k2（km/2） ,在地址i產(chǎn)生沖突，不是探測(cè)i+l地址，而是探測(cè)i+12，i-12，i+22，i-22的地址 2022/7/18雙重散列法(隨機(jī)數(shù)法） 以關(guān)鍵字的另一個(gè)散列函數(shù)值作為增量。設(shè)兩個(gè)散列函數(shù)為：H1和H2，則得到的探測(cè)序列為：(d+H2(key)%m ，(d+2H2

18、(key)%m ，(d+3H2(key)%m ， 其中d=H1(key)由此可知，雙重散列法探測(cè)下一個(gè)開(kāi)放地址的公式為：di=(d+i*H2(key)%m (1im-1)使H2的值和m互素 2022/7/18鏈地址法 基本思想：開(kāi)散列法的一種簡(jiǎn)單形式是把散列表的每個(gè)地址空間定義為一個(gè)單鏈表的表頭指針，單鏈表中每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和一個(gè)指針域，數(shù)據(jù)域存儲(chǔ)查找表中的元素。散列地址相同的所有元素存儲(chǔ)在以該散列地址為表頭指針的單鏈表里 2022/7/18鏈地址法示例關(guān)鍵字為(13,19,39,24,28,57,76,51,84)，散列表長(zhǎng)m=13，散列函數(shù)為H(key)=key%11 0123456

19、789101112245713281939845176ASLss=1/9*(5*1+3*2+1*3)=14/9ASLun=1/11*(6*1+2*2+2*3+1*4)=20/11對(duì)查找失敗時(shí)的平均查找長(zhǎng)度有兩種觀點(diǎn) 2022/7/18關(guān)于閉散列法和開(kāi)放地址法閉散列法在有的教材上稱(chēng)為“開(kāi)放地址法”。閉散列法中“閉”的含義是散列表的長(zhǎng)度是確定的，定義后不能增加；開(kāi)放地址法中“開(kāi)放”，是指數(shù)組的每一個(gè)地址有可能被任何基地址的元素占用，即每個(gè)地址對(duì)所有元素都是開(kāi)放的。 2022/7/18關(guān)于開(kāi)散列法和鏈地址法開(kāi)散列法在有的教材上稱(chēng)為“鏈地址法”。開(kāi)散列法中“開(kāi)”的含義是散列表的元素的個(gè)數(shù)不受限制（只受

20、內(nèi)存大小限制），即具有相同哈希函數(shù)值的關(guān)鍵字都可鏈到同一鏈表中；由于用鏈表解決沖突，所以這種解決沖突的方法有時(shí)稱(chēng)鏈地址法。 2022/7/18散列表的查找散列表查找過(guò)程和散列表的生成相似：首先根據(jù)選定的哈希函數(shù)，計(jì)算出給定關(guān)鍵字的哈希地址：若該地址為空，則查找失敗。若該地址不空，且所存關(guān)鍵字的值恰好等于所查關(guān)鍵字，則查找成功。若該地址不空，但所存關(guān)鍵字的值不等于所查關(guān)鍵字，則按著造表時(shí)使用的解決沖突的方法，繼續(xù)查找，直到成功或失敗。2022/7/18哈希查找過(guò)程及分析1. 哈希查找過(guò)程給定k值計(jì)算H(k)此地址為空關(guān)鍵字=k查找失敗查找成功按處理沖突方法計(jì)算HiYNYN2022/7/18裝填因

21、子裝填因子越小，發(fā)生沖突的可能性越小，裝填因子越大，發(fā)生的沖突的可能性越大2022/7/18散列表的查找及分析 散列表的平均查找長(zhǎng)度是的函數(shù)，不是記錄數(shù)n的函數(shù)。線性探測(cè)法查找成功時(shí)的平均查找長(zhǎng)度為： 鏈地址法查找成功時(shí)的平均查找長(zhǎng)度為： 對(duì)關(guān)鍵字集不大且頻繁使用的關(guān)鍵字，也能找到“完美函數(shù)”2022/7/18散列表小結(jié)平均查找長(zhǎng)度(ASL)最小。缺點(diǎn)有：占用存儲(chǔ)空間大開(kāi)放定址法刪除元素只能作標(biāo)記，不能物理的刪除，浪費(fèi)了空間只能按關(guān)鍵字隨機(jī)查找，不能按非關(guān)鍵字查找仍有比較2022/7/182022/7/1847下面關(guān)于哈希(Hash，雜湊)查找的說(shuō)法正確的是( )A哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小 B除留余數(shù)法是所有哈希函數(shù)中最好的 C不存在特別好與壞的哈希函數(shù)，要視情況而定D若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡(jiǎn)單的將該元素刪去即可 C自測(cè)題 2022/7/182022/7/1848 假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入哈希表中，至少要進(jìn)行多少次探測(cè)？( ) A. k-1次 B. k次 C.