數(shù)據(jù)結(jié)構(gòu)563.教學(xué)課件_第09章查找b

1、9.1 基本概念9.2 靜態(tài)查找表9.3 動(dòng)態(tài)查找表9.4 哈希查找表第9章 查找教材第8、11和12章省略，因操作系統(tǒng)課程會(huì)涉及。1、順序查找（線性查找）2、折半查找（二分或?qū)Ψ植檎遥?、分塊查找（索引順序查找）4、靜態(tài)樹表的查找（次優(yōu)樹）二叉排序樹19.4 哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析是一種查找效率高達(dá)O(1)的算法！23一、哈希表的概念哈希表：即散列存儲(chǔ)結(jié)構(gòu)。 散列法存儲(chǔ)的基本思想：建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。 優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無關(guān)！例1：若將學(xué)生

2、信息按如下方式存入計(jì)算機(jī)，如：將2001011810201的所有信息存入V01單元；將2001011810202的所有信息存入V02單元；將2001011810231的所有信息存入V31單元。欲查找學(xué)號(hào)為2001011810216的信息，便可直接訪問V16！4例2 ： 有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）k，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖。解：根據(jù)散列函數(shù)H（k）k ，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：討論：如何進(jìn)行散列查找？根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式，迅即可查到結(jié)果！例如，查找

3、key=9,則訪問H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。 地址9111423242539內(nèi)顯缺點(diǎn)：空間效率低如何解決？H(k)稱為散列函數(shù)5選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置并按此存放；查找時(shí)也由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址中內(nèi)容進(jìn)行比較，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。Hash查找法哈希方法(雜湊法)哈希函數(shù)(雜湊函數(shù))哈希表(雜湊表) 沖 突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(

4、雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表) 用盡量少的冗余空間實(shí)現(xiàn)O(1)的查找效率有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7通過哈希函數(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 66所以，哈希方法必須解決以下兩個(gè)問題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址內(nèi)集中并大致均勻分布，以減少空間浪費(fèi)

5、。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。7二、哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法 除留余數(shù)法 乘余取整法數(shù)字分析法 平方取中法 折疊法 隨機(jī)數(shù)法 要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。要求二：無論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免沖突。8Hash(key) = akey + b (a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)

6、：要占用連續(xù)地址空間，空間效率低。 例：關(guān)鍵碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為Hash(key)=key/100， 則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：0 1 2 3 4 5 6 7 8 99008007005003001001、直接定址法9Hash(key)=key mod p (p是一個(gè)整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計(jì)的哈希表長為m，則一般取pm且為質(zhì)數(shù) （也可以是合數(shù)，但不能包含小于20的質(zhì)因子）。2、除留余數(shù)法為什么要對(duì) p 加限制？例如：給定一組關(guān)鍵字為:12, 39, 18, 24, 33, 21，若取

7、p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為： 3, 3, 0, 6, 6, 3可見，若 p 中含質(zhì)因子 3， 則所有含質(zhì)因子 3 的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，從而增加了“沖突”的可能。10特點(diǎn)：選用關(guān)鍵字的某幾位組合成哈希地址。選用原則應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。 3 4 7 0 5 2 4 3 4 9 1 4 8 73 4 8 2 6 9 63 4 8 5 2 7 03 4 8 6 3 0 53 4 9 8 0 5 83 4 7 9 6 7 13 4 7 3 9 1 9例：有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：3、數(shù)字分析法討論： 第1、2位均是“3和4”，第3位也只

8、有“ 7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號(hào)： 若哈希地址取兩位（因元素僅80個(gè)），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。11特點(diǎn)：對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。 例：2589的平方值為6702921，可以取中間的029為地址。 5、折疊法 特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長，取后幾位作為哈希地址。適用于：每一位上各符號(hào)出現(xiàn)概率大致相同的情況。法1：移位法

9、 將各部分的最后一位對(duì)齊相加。法2：間界疊加法從一端向另一端沿分割界來回折疊后，最后一位對(duì)齊相加。 例：元素42751896, 用法1： 42751896=1041 用法2： 427 518 96 724+518+69 =13114、平方取中法126、隨機(jī)數(shù)法Hash(key) = random ( key ) (random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）； 關(guān)鍵字的長度； 哈希表的大??； 關(guān)鍵字的分布情況； 查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：13三、沖突處理方法常見的沖突處理方法有：開放定址法（開地址法） 鏈地址法（拉鏈

10、法） 再哈希法（雙哈希函數(shù)法）建立一個(gè)公共溢出區(qū) 141、開放定址法（開地址法） 設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 具體實(shí)現(xiàn)：Hi=(Hash(key)+di) mod m ( 1i m ) 其中： Hash(key)為哈希函數(shù) m為哈希表長度 di 為增量序列 1，2，m-1，且di=i 1）線性探測(cè)法含義：一旦沖突，就找附近（下一個(gè)）空地址存入。15關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：哈希表表長為m=11； 哈希函數(shù)為Hash(key)=key mod 11； 擬用線性探測(cè)法處理沖突。建哈希

11、表如下：解釋： 47、7是由哈希函數(shù)得到的沒有沖突的哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：291116922283 Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8為空，因此將29存入。 另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3 還連續(xù)移動(dòng)了兩次（二次聚集）16線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第

12、i+2個(gè)哈希地址的同義詞， 因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問題。 討論：17仍舉上例，改用二次探測(cè)法處理沖突，建表如下： 0 1 2 3 4 5 6 7 8 9 10112234792167298 注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。 2） 二次探測(cè)法Hi=(Hash(key)di) mod m其中：Hash(key)為

13、哈希函數(shù) m為哈希表長度，m要求是某個(gè)4k+3的質(zhì)數(shù)； di為增量序列 12，-12，22，-22，q2 3） 若di偽隨機(jī)序列，就稱為偽隨機(jī)探測(cè)法182、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。 設(shè) 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函數(shù)為：Hash(key)=key mod 11，用拉鏈法處理沖突，則建表如右圖所示。 例： 0 1 2 3 4 5 6 7 8 91022118934737922971650810

14、有沖突的元素可以插在表尾,也可以插在表頭。ASL=(1*9 + 2*4)/13 = 17/131.31920嚴(yán)蔚敏習(xí)題集9.45 假設(shè)哈希表長為m,哈希函數(shù)為H(x),用鏈地址法處理沖突。試編寫輸入一組關(guān)鍵字并建造哈希表的算法。Typedef*LNodeMAXSIZECHashTable;/鏈地址Hash表類型StatusBuild_Hash (CHashTable&T, intm)/輸入一組關(guān)鍵字,建立Hash表，表長為m，用鏈地址法處理沖突if(m1)returnERROR; T=malloc(m*sizeof(LNode*); /開空間建立表頭指針向量 for(i=0; idata=ke

15、y; q-next=NULL; n=H(key); if(!Tn)Tn=q;/若無沖突，則作為鏈表的第一個(gè)結(jié)點(diǎn) elsefor( p=Tn; p-next; p=p-next);p-next=q; /有沖突則插入鏈表尾部 /while returnOK;/Build_Hash若當(dāng)前結(jié)點(diǎn)不是末結(jié)點(diǎn)則繼續(xù)“摸瓜”3、再哈希法（雙哈希函數(shù)法）Hi=RHi(key) i=1, 2, ，kRHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時(shí)就計(jì)算另一個(gè)哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點(diǎn)：不易產(chǎn)生聚集；缺點(diǎn)：增加了計(jì)算時(shí)間。4. 建立一個(gè)公共溢出區(qū) 思路：除設(shè)立哈?；颈硗猓碓O(shè)立一個(gè)溢出向量表。所有關(guān)鍵字和基本表中關(guān)鍵

16、字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。22int hashsize = 997, . ; /哈希表容量 typedef struct ElemType *elem; / 數(shù)據(jù)元素存儲(chǔ)基址，動(dòng)態(tài)分配數(shù)組 int count; / 當(dāng)前數(shù)據(jù)元素個(gè)數(shù) int sizeindex; / hashsizesizeindex為當(dāng)前容量 HashTable;/- 開放定址哈希表的存儲(chǔ)結(jié)構(gòu) -四、哈希表的查找及分析23Status SearchHash (HashTable H, KeyType K, int &p, int &c) / 在開放定址哈希表H中查找關(guān)鍵

17、碼為K的記錄。若查找成功，/ 以p指示待查數(shù)據(jù)在表中位置；否則，以p指示插入位置 / SearchHashp = Hash(K); / 求得哈希地址while ( H.elemp.key != NULLKEY & / 該位置有記錄 !EQ(K, H.elemp.key)） / 并且關(guān)鍵字不相等 collision(p, +c); / 求得下一探查地址 pif (EQ(K, H.elemp.key) return SUCCESS; / 查找成功，返回待查數(shù)據(jù)元素位置 pelse return UNSUCCESS； / 查找不成功24教材p259算法9.17.Status InsertHash (

18、HashTable &H, Elemtype e)c = 0; / 表中已有與 e 有相同關(guān)鍵字的元素if ( HashSearch ( H, e.key, p, c ) = SUCCESS ) return DUPLICATE; / 沖突次數(shù) c 未達(dá)到上限，（閥值 c可調(diào)）else if ( c hashsizeH.sizeindex/2 ) H.elemp = e; +H.count; return OK; / 插入eelse RecreateHashTable(H); / 重建哈希表 / InsertHash25教材p259算法9.18.明確：散列函數(shù)沒有“萬能”通式（雜湊法），要根據(jù)

19、元素集合的特性而分別構(gòu)造。 討論：哈希查找的速度是否為真正的O（1）？不是。由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進(jìn)行比較，仍然要以平均查找長度ASL來衡量。一般地，ASL依賴于哈希表的裝填因子,它標(biāo)志著哈希表的裝滿程度。 越大，表中記錄數(shù)越多，說明表裝得越滿，發(fā)生沖突的可能性就越大，查找時(shí)比較次數(shù)就越多。0126討論：2）“沖突”是不是特別討厭？答：不一定！正因?yàn)橛袥_突，使得文件加密后無法破譯?。▎蜗蛏⒘泻瘮?shù)不可逆，常用于數(shù)字簽名和間接加密）。利用了哈希表性質(zhì)：源文件稍稍改動(dòng)，會(huì)導(dǎo)致哈希表變動(dòng)很大。1） 散列存儲(chǔ)的查找效率到底是多少？答：ASL與裝填因子有關(guān)！既不是嚴(yán)格的O(1)，也不是

20、O(n)應(yīng)盡量選擇一個(gè)合適的，以降低ASL的長度典型應(yīng)用：md5散列算法2728md5散列算法信息-摘要算法（1991年）md5的典型應(yīng)用是對(duì)一段信息（message）產(chǎn)生一個(gè)128位的信息摘要（message-digest），以防止被篡改。message-digest algorithm）用于加/解密和數(shù)字簽名例： md5用于網(wǎng)絡(luò)（如BBS）登錄時(shí)的身份認(rèn)證在BBS服務(wù)器上，用戶的密碼都是以md5（或其它類似的算法）經(jīng)加密后存儲(chǔ)在文件系統(tǒng)中。當(dāng)用戶登錄的時(shí)候，系統(tǒng)把用戶輸入的密碼計(jì)算成md5值，然后再去和預(yù)存在服務(wù)器中的md5值進(jìn)行比較，進(jìn)而確定輸入的密碼是否正確。優(yōu)點(diǎn)：系統(tǒng)在不知用戶Password明碼的情況下就可以確定其登錄的合法性。這不但可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道，而且還在一定程度上增加了密碼被破解的難度。 29科普小知識(shí)：Hash函數(shù)與數(shù)字簽名（數(shù)字手?。?HASH函數(shù)，又稱雜湊函數(shù)，是在信息安全領(lǐng)域有廣泛和重要應(yīng)用的密碼算法，它有一種類似于指紋的應(yīng)用。在網(wǎng)絡(luò)安全協(xié)議中，雜湊函數(shù)用來處理電子簽名，將冗長的簽名文件壓縮為一段獨(dú)特的數(shù)字信息，像指紋鑒別身份一樣保證原來數(shù)字簽名文件的合法性和安全性。例如SHA-1