DS08_散列查找a__陳越主編_數(shù)據(jù)結(jié)構(gòu)

1、1第5章 散列查找 5.1 引子已有已有幾種查找方法：幾種查找方法：h)(log2NO已經(jīng)已經(jīng)是相當(dāng)不錯(cuò)的時(shí)間復(fù)雜度是相當(dāng)不錯(cuò)的時(shí)間復(fù)雜度!順序查找順序查找二分查找（靜態(tài)查找）二分查找（靜態(tài)查找）二叉搜索樹二叉搜索樹)(NO)(log2NO)(hO為二叉查找樹的高度到底還有沒有其他到底還有沒有其他適應(yīng)性廣適應(yīng)性廣而而速度又快速度又快的查找方法呢？的查找方法呢？2第5章 散列查找 5.1 引子例例5.1 在登錄在登錄QQ的時(shí)候，的時(shí)候，QQ服務(wù)器如何服務(wù)器如何核對(duì)你核對(duì)你的身份的身份，以確定你就是該號(hào)碼的主人？，以確定你就是該號(hào)碼的主人？【分析分析】看看是否可以用看看是否可以用二分法二分法查找。

2、查找。 十億十億（109 230）有效用戶，用二分查找有效用戶，用二分查找30次次。 十億十億（109 230） 1K 1024G，1T連續(xù)空間。連續(xù)空間。 按有效按有效QQ號(hào)大小號(hào)大小有有序存儲(chǔ)序存儲(chǔ)：在連續(xù)存儲(chǔ)空間中，在連續(xù)存儲(chǔ)空間中，插插入和刪除入和刪除一個(gè)新一個(gè)新QQ號(hào)碼將需要號(hào)碼將需要移動(dòng)大量數(shù)據(jù)移動(dòng)大量數(shù)據(jù)。用不了二分查找，用不了二分查找，我們?cè)撛趺崔k？我們?cè)撛趺崔k？3第5章 散列查找 5.1 引子例例5.2 查英文字典的過程查英文字典的過程查詢英文單詞查詢英文單詞“zoo”，你為什么不用二分法，而直接從字典的后面找？你為什么不用二分法，而直接從字典的后面找？ 我們已經(jīng)根據(jù)要查找的

3、關(guān)鍵詞我們已經(jīng)根據(jù)要查找的關(guān)鍵詞“zoo”在腦子里經(jīng)過了在腦子里經(jīng)過了“計(jì)計(jì)算算”，得出該關(guān)鍵詞所在的，得出該關(guān)鍵詞所在的大致位置大致位置，這樣就能，這樣就能更快地更快地找到它。找到它。這個(gè)這個(gè)“計(jì)算計(jì)算”過程非常類似于本章將要介紹的散列查找中的過程非常類似于本章將要介紹的散列查找中的“散列函數(shù)計(jì)算散列函數(shù)計(jì)算”。 查字典的過程結(jié)合了查字典的過程結(jié)合了散列查找散列查找（用于初步定位）、（用于初步定位）、二分查找二分查找（一般不是準(zhǔn)確二分）和（一般不是準(zhǔn)確二分）和順序查找順序查找（當(dāng)很接近關(guān)鍵詞的時(shí)候）等（當(dāng)很接近關(guān)鍵詞的時(shí)候）等幾種查找方法。幾種查找方法。4第5章 散列查找 5.1 引子例例5

4、.3 網(wǎng)上搜索。網(wǎng)上搜索。搜索引擎搜索引擎是如何如此是如何如此神速地神速地把我們把我們需要的需要的有關(guān)信息有關(guān)信息找到的？找到的？【分析分析】主要數(shù)據(jù)結(jié)構(gòu)是主要數(shù)據(jù)結(jié)構(gòu)是“倒排索引倒排索引” - “單詞到文檔單詞到文檔”的映射關(guān)系。的映射關(guān)系。如何在這個(gè)巨大無比的表格如何在這個(gè)巨大無比的表格中查找特定的關(guān)鍵詞中查找特定的關(guān)鍵詞？ DocsTerms文檔文檔1文檔文檔2文檔文檔m1文檔文檔m關(guān)鍵詞關(guān)鍵詞13: 1,12,2002: 1, 223: 9,40,52關(guān)鍵詞關(guān)鍵詞202: 11,22 4: 9,20,32,655: 5,9,10,32,35關(guān)鍵詞關(guān)鍵詞n1005: 3,9,10,32,

5、5610: 5,6,19,.,44關(guān)鍵詞關(guān)鍵詞n5: 1,9,20,22,55001: 75【問題問題】如何能夠在極短的時(shí)間內(nèi)（比如如何能夠在極短的時(shí)間內(nèi)（比如1秒內(nèi)）搜索到需要的關(guān)鍵詞？秒內(nèi)）搜索到需要的關(guān)鍵詞？ 第5章 散列查找 5.1 引子 散列查找法的兩項(xiàng)基本工作：散列查找法的兩項(xiàng)基本工作：構(gòu)造散列函數(shù)：構(gòu)造散列函數(shù)：確定關(guān)鍵詞所在的存儲(chǔ)位置的確定關(guān)鍵詞所在的存儲(chǔ)位置的計(jì)算方法計(jì)算方法； 解決沖突：解決沖突：當(dāng)多個(gè)關(guān)鍵詞所在的存儲(chǔ)位置相同時(shí)的解決方法。當(dāng)多個(gè)關(guān)鍵詞所在的存儲(chǔ)位置相同時(shí)的解決方法。【答案答案】散列查找法散列查找法是是很好很好方法之一！方法之一！)(log2NO 并且，期望

6、查找的并且，期望查找的時(shí)間復(fù)雜度時(shí)間復(fù)雜度好于好于 ，幾乎是常量：幾乎是常量：O（1），即查找時(shí)間與問題規(guī)模無關(guān)！），即查找時(shí)間與問題規(guī)模無關(guān)！ 當(dāng)然，散列查找法也有當(dāng)然，散列查找法也有缺點(diǎn)和局限性缺點(diǎn)和局限性6散列表散列表的定義的定義 形如形如“名字名字(Name)-屬性屬性(Attribute)”對(duì)的集合的對(duì)的集合的“符號(hào)表符號(hào)表(Symbol Table)”也叫做也叫做“散列表散列表” （Hash Table，即，即哈希表哈希表）。）。類型名稱類型名稱:符號(hào)表（符號(hào)表（SymbolTable）數(shù)據(jù)對(duì)象集：數(shù)據(jù)對(duì)象集：符號(hào)表是符號(hào)表是“名字名字(Name)-屬性屬性(Attribute)”

7、對(duì)的集合。對(duì)的集合。操作集：操作集：對(duì)于一個(gè)符號(hào)表對(duì)于一個(gè)符號(hào)表Table SymbolTable，一個(gè)給定名字，一個(gè)給定名字Name NameType，屬性屬性Attr AttributeType，以及正整數(shù)，以及正整數(shù)TableSize，符號(hào)表的基本操作主要有：，符號(hào)表的基本操作主要有：1、SymbolTable InitializeTable( int TableSize )：創(chuàng)建一個(gè)長(zhǎng)度為：創(chuàng)建一個(gè)長(zhǎng)度為TableSize的符號(hào)表；的符號(hào)表；2、Boolean IsIn( SymbolTable Table, NameType Name)： 查找特定的名字查找特定的名字Name是否在符

8、號(hào)表是否在符號(hào)表Table中；中；3、AttributeType Find( SymbolTable Table, NameType Name)： 獲取獲取Table中指定名字中指定名字Name對(duì)應(yīng)的屬性；對(duì)應(yīng)的屬性；4、SymbolTable Modefy(SymbolTable Table, NameType Name, AttributeType Attr)： 將將Table中指定名字中指定名字Name的屬性修改為的屬性修改為Attr；5、SymbolTable Insert(SymbolTable Table, NameType Name, AttributeType Attr)： 向

9、向Table中插入一個(gè)新名字中插入一個(gè)新名字Name及其屬性及其屬性Attr；6、 SymbolTable Delete(SymbolTable Table, NameType Name)： 從從Table中刪除一個(gè)名字中刪除一個(gè)名字Name及其屬性。及其屬性。3/225.2 基本概念第5章 散列查找 7“散列（散列（Hashing）” 的基本思想是：以數(shù)據(jù)對(duì)象的關(guān)鍵字的基本思想是：以數(shù)據(jù)對(duì)象的關(guān)鍵字key為自變量，通過一個(gè)確定的為自變量，通過一個(gè)確定的函數(shù)關(guān)系函數(shù)關(guān)系 h，計(jì)算出對(duì)應(yīng)的函數(shù)值，計(jì)算出對(duì)應(yīng)的函數(shù)值h(key)，把這個(gè)值解釋為數(shù)據(jù)對(duì)象的存儲(chǔ)地址，并按此存放，即，把這個(gè)值解釋為數(shù)據(jù)

10、對(duì)象的存儲(chǔ)地址，并按此存放，即“存儲(chǔ)位置存儲(chǔ)位置 = h（key）”。第5章 散列查找 5.2 基本概念 散列方法中使用的計(jì)算函數(shù)稱為散列方法中使用的計(jì)算函數(shù)稱為“散列函數(shù)散列函數(shù)” （也稱哈希函數(shù)），（也稱哈希函數(shù)），按這個(gè)思想構(gòu)造的表稱為按這個(gè)思想構(gòu)造的表稱為“散列表散列表”，所以它也是一種存儲(chǔ)方法。，所以它也是一種存儲(chǔ)方法。 在查找某數(shù)據(jù)對(duì)象時(shí)，用同樣的方法在查找某數(shù)據(jù)對(duì)象時(shí)，用同樣的方法“存儲(chǔ)位置存儲(chǔ)位置 = h（key）”計(jì)計(jì)算出地址，將算出地址，將key與該地址單元中數(shù)據(jù)對(duì)象關(guān)鍵字進(jìn)行比較，確定查與該地址單元中數(shù)據(jù)對(duì)象關(guān)鍵字進(jìn)行比較，確定查找是否成功。找是否成功。通常關(guān)鍵詞的通常關(guān)

11、鍵詞的值域值域（允許取值的范圍）遠(yuǎn)遠(yuǎn)大于表空間的（允許取值的范圍）遠(yuǎn)遠(yuǎn)大于表空間的地址地址集集，所以說，所以說，沖突不可能避免，只能盡可能減少?zèng)_突不可能避免，只能盡可能減少。 可能將可能將不同的關(guān)鍵字映射到同一個(gè)散列地址不同的關(guān)鍵字映射到同一個(gè)散列地址上，即上，即h(keyi) = h(keyj)（當(dāng)（當(dāng)keyi keyj），這種現(xiàn)象稱為），這種現(xiàn)象稱為“沖突沖突(Collision)”， keyi 和和keyj稱為稱為“同義詞（同義詞（synonym）”。8例例5.4 有有n = 11個(gè)數(shù)據(jù)對(duì)象的集合，關(guān)鍵詞是正整數(shù)，分別為個(gè)數(shù)據(jù)對(duì)象的集合，關(guān)鍵詞是正整數(shù)，分別為 18，23，11，20，2

12、，7，27，30，42，15，34。如果符號(hào)表的。如果符號(hào)表的大小用大小用TableSize = 17（通常用一個(gè)素?cái)?shù)），選取散列函數(shù)（通常用一個(gè)素?cái)?shù)），選取散列函數(shù)h如下：如下：h(key) = key mod TableSize （公式（公式 5.1）其中其中mod 是求余運(yùn)算，相當(dāng)于是求余運(yùn)算，相當(dāng)于C語言中的語言中的%運(yùn)算。運(yùn)算。用這個(gè)散列函數(shù)對(duì)用這個(gè)散列函數(shù)對(duì)11個(gè)數(shù)據(jù)對(duì)象建立查找表（個(gè)數(shù)據(jù)對(duì)象建立查找表（忽略各關(guān)鍵詞對(duì)應(yīng)的屬性部分，該例的關(guān)鍵詞沒有沖突）如下：）如下：第5章 散列查找 5.2 基本概念 查找時(shí)，對(duì)給定關(guān)鍵詞查找時(shí)，對(duì)給定關(guān)鍵詞keyi依然通過公式依然通過公式5.1計(jì)

13、算出地址，再計(jì)算出地址，再將將keyi與該地址單元中關(guān)鍵詞比較，若相等，則查找成功。與該地址單元中關(guān)鍵詞比較，若相等，則查找成功。 比如查找：比如查找：key = 22, 地址是地址是22%17 = 5，該地址空表示表中，該地址空表示表中沒有關(guān)鍵詞沒有關(guān)鍵詞22的信息。的信息。比如查找：比如查找：key = 40, 地址是地址是40%17 = 6，該地址存的是，該地址存的是23，40 23，故還要采用后面介紹的，故還要采用后面介紹的解決沖突解決沖突的策略才能確定。的策略才能確定。地址地址0123456789 10 11 12 13 14 15 16關(guān)鍵詞關(guān)鍵詞 34 18 2 2023 7 4

14、227 113015【定義定義】 設(shè)散列表空間大小為設(shè)散列表空間大小為m，填入表中的元素個(gè)數(shù)是，填入表中的元素個(gè)數(shù)是n，則稱，則稱 n / m為散列表的為散列表的“裝填因子（裝填因子（Loading Factor）”。 裝填因子裝填因子11 / 17 0.65。 實(shí)用時(shí)，常將散列表大小設(shè)計(jì)使得實(shí)用時(shí)，常將散列表大小設(shè)計(jì)使得 0.50.8為宜為宜。9例例5.5 將給定的將給定的10個(gè)個(gè)C語言中的關(guān)鍵詞語言中的關(guān)鍵詞(保留字或標(biāo)準(zhǔn)函數(shù)名保留字或標(biāo)準(zhǔn)函數(shù)名)順次存入一張散列表。這順次存入一張散列表。這10個(gè)關(guān)鍵詞為：個(gè)關(guān)鍵詞為：acos、define、float、exp、char、atan、ceil

15、、floor、clock、ctime。散列表設(shè)計(jì)為一個(gè)散列表設(shè)計(jì)為一個(gè)二維數(shù)組二維數(shù)組Table262，2列分別代表列分別代表 2個(gè)槽。個(gè)槽。 第5章 散列查找 5.2 基本概念槽槽 1槽槽 0012345625裝填因子裝填因子 ?10 / 52 = 0.19為了把字母為了把字母 a z 映射到映射到 0 25, 如何設(shè)計(jì)散列如何設(shè)計(jì)散列函數(shù)函數(shù)h (key ) = ? h(key) = key0 aacosacosdefinedefinefloatfloatexpexpcharcharatanatanceilceilfloorfloorclockctime如何設(shè)計(jì)如何設(shè)計(jì)散列函數(shù)散列函數(shù)，使

16、得，使得發(fā)生發(fā)生沖突的概率沖突的概率盡可能小？盡可能小？當(dāng)當(dāng)沖突或溢出沖突或溢出不可避免時(shí)，不可避免時(shí)，如如何處理何處理使得表中沒有空單元被使得表中沒有空單元被浪費(fèi)，同時(shí)浪費(fèi)，同時(shí)插入、刪除、查找插入、刪除、查找等操作都能正確完成？等操作都能正確完成？10第5章 散列查找 5.3 散列函數(shù)的構(gòu)造方法 一個(gè)一個(gè)“好好”的散列函數(shù)一般應(yīng)考慮下列的散列函數(shù)一般應(yīng)考慮下列兩個(gè)因素兩個(gè)因素：1. 計(jì)算簡(jiǎn)單計(jì)算簡(jiǎn)單，以便提高轉(zhuǎn)換速度；，以便提高轉(zhuǎn)換速度；2. 關(guān)鍵詞對(duì)應(yīng)的關(guān)鍵詞對(duì)應(yīng)的地址空間分布均勻地址空間分布均勻，以盡量減少?zèng)_突。，以盡量減少?zèng)_突。 數(shù)字關(guān)鍵詞數(shù)字關(guān)鍵詞的散列函數(shù)構(gòu)造的散列函數(shù)構(gòu)造1直接

17、定址法直接定址法 取關(guān)鍵詞的某個(gè)線性函數(shù)值為散列地址取關(guān)鍵詞的某個(gè)線性函數(shù)值為散列地址，即，即 h(key) = a key + b (a、b為常數(shù)為常數(shù))地址地址h(key)出生年份出生年份(key)人數(shù)人數(shù)(attribute)0 01990199012851285萬萬1 11991199112811281萬萬2 21992199212801280萬萬10102000200012501250萬萬21212011201111801180萬萬11第5章 散列查找 5.3 散列函數(shù)的構(gòu)造方法2除留余數(shù)法除留余數(shù)法散列函數(shù)為：散列函數(shù)為：h(key) = key mod p例例5.4: h(key

18、) = key % 17 地址地址h(key)012345678910 11 12 13 14 15 16關(guān)鍵詞關(guān)鍵詞key34 182202374227 113015 這里：這里：p = Tablesize = 17。也可以采用。也可以采用 p TableSize； TableSize = n/；n-key集合的大小，集合的大小，裝填因子上限；裝填因子上限； p TableSize的某個(gè)最大的某個(gè)最大素?cái)?shù)素?cái)?shù)。TableSize81632641282565121024p7133161127251503101912第5章 散列查找 5.3 散列函數(shù)的構(gòu)造方法3數(shù)字分析法數(shù)字分析法 取取11位手

19、機(jī)號(hào)碼位手機(jī)號(hào)碼key的后的后4位作為地址：位作為地址： 散列函數(shù)為：散列函數(shù)為：h(key) = atoi(key+7) 若若key集合大小集合大小n 10000, 則比較合適。若取則比較合適。若取裝填因子上限裝填因子上限=0.8，那么地址空間（表長(zhǎng)），那么地址空間（表長(zhǎng)）TableSize = n/=12500 若若key集合大小集合大小n 100, 則可以作如下二選一：則可以作如下二選一：a、若取、若取裝填因子上限裝填因子上限=0.8，那么地址空間（表長(zhǎng)），那么地址空間（表長(zhǎng)）TableSize = n/128， 取取p=127，h(key) = atoi(key+7) % pb、直接、

20、直接取后取后2位作為地址：位作為地址： h(key) = atoi(key+9)，而表長(zhǎng)而表長(zhǎng)TableSize = n/ 127。13第5章 散列查找 5.3 散列函數(shù)的構(gòu)造方法3數(shù)字分析法數(shù)字分析法如果關(guān)鍵詞如果關(guān)鍵詞 key 是是18位的身份證號(hào)碼：位的身份證號(hào)碼： h1(key) = (key6-0) 104 + (key10-0) 103 + (key14-0) 102 + (key16-0) 10 + (key17-0)h(key) = h1(key) 10 + 10 （當(dāng)（當(dāng) key18 = x時(shí)）時(shí)）或或 h(key) = h1(key) 10 + key18-0 （當(dāng)（當(dāng) key18 為為0 9時(shí)）時(shí)）123456789101112131415161718330106199010080419省省市市區(qū)（縣）區(qū)（縣）下屬轄下屬轄區(qū)編號(hào)區(qū)編號(hào)（出生）年份（出生）年份月份月份日期日期該轄區(qū)中的該轄區(qū)中的序號(hào)序號(hào)校校驗(yàn)驗(yàn)14字符關(guān)鍵詞字符關(guān)鍵詞的散列函數(shù)構(gòu)造的散列函數(shù)構(gòu)造1一個(gè)簡(jiǎn)單的散列函數(shù)一個(gè)簡(jiǎn)單的散列函數(shù)ASCII碼加和法碼加和法對(duì)字符型關(guān)鍵詞對(duì)字符型關(guān)鍵詞key定義散列函數(shù)如下：定義散列函數(shù)如下：h(key) = (keyi) mod T