湘潭大學(xué)-數(shù)據(jù)結(jié)構(gòu)-課件-ppt-Ch05-Hashing

1、 Preview一種用于以常數(shù)平均時(shí)間執(zhí)行插入、刪除和查找的技術(shù)不支持需要元素間任何排序信息的操作散 列 表第五章 散列1 一般想法一般想法已有已有幾種查找方法：幾種查找方法：h)(log2NO已經(jīng)已經(jīng)是相當(dāng)不錯(cuò)的時(shí)間復(fù)雜度是相當(dāng)不錯(cuò)的時(shí)間復(fù)雜度!順序查找順序查找二分查找（靜態(tài)查找）二分查找（靜態(tài)查找）二叉查找樹(shù)二叉查找樹(shù))(NO)(log2NO)(hO為二叉查找樹(shù)的高度到底還有沒(méi)有其他到底還有沒(méi)有其他適應(yīng)性廣適應(yīng)性廣而而速度又快速度又快的查找方法呢？的查找方法呢？1 一般想法一般想法例例1在登錄在登錄QQ的時(shí)候，的時(shí)候，QQ服務(wù)器如何服務(wù)器如何核對(duì)你核對(duì)你的身份的身份，以確定你就是該號(hào)碼的主

2、人？，以確定你就是該號(hào)碼的主人？【分析分析】看看是否可以用看看是否可以用二分法二分法查找。查找。 十億十億（109 230）有效用戶(hù)，用二分查找有效用戶(hù)，用二分查找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？1 一般想法一般想法例例2查英文字典的過(guò)程查英文字典的過(guò)程查詢(xún)英文單詞查詢(xún)英文單詞“zoo”，你為什么不用二分法，而直接從字典的

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

4、候）等幾種查找方法。幾種查找方法。1 一般想法一般想法例例3網(wǎng)上搜索。網(wǎng)上搜索。搜索引擎搜索引擎是如何如此是如何如此神速地神速地把我們把我們需要的需要的有關(guān)信息有關(guān)信息找到的？找到的？【分析分析】主要數(shù)據(jù)結(jié)構(gòu)是主要數(shù)據(jù)結(jié)構(gòu)是“倒排索引倒排索引” - “單詞到文檔單詞到文檔”的映射關(guān)系。的映射關(guān)系。如何在這個(gè)巨大無(wú)比的表格如何在這個(gè)巨大無(wú)比的表格中查找特定的關(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,224: 9,20,32,655: 5,9,10,32

5、,35關(guān)鍵詞關(guān)鍵詞n1005: 3,9,10,32,56 10: 5,6,19,.,44關(guān)鍵詞關(guān)鍵詞n5: 1,9,20,22,55001: 7【問(wèn)題問(wèn)題】如何能夠在極短的時(shí)間內(nèi)（比如如何能夠在極短的時(shí)間內(nèi)（比如1秒內(nèi)）搜索到需要的關(guān)鍵詞？秒內(nèi)）搜索到需要的關(guān)鍵詞？ 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í)的解決方法?！敬鸢复鸢浮可⒘胁檎曳ㄉ⒘胁檎曳ㄊ鞘呛芎煤芎梅椒ㄖ?/p>

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

7、me)-屬性屬性(Attribute)”對(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)度為T(mén)ableSize的符號(hào)表；的符號(hào)表；2、Boolean IsIn( SymbolTable Table, NameType Name)： 查

8、找特定的名字查找特定的名字Name是否在符號(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, A

9、ttributeType Attr)： 向向Table中插入一個(gè)新名字中插入一個(gè)新名字Name及其屬性及其屬性Attr；6、 SymbolTable Delete(SymbolTable Table, NameType Name)： 從從Table中刪除一個(gè)名字中刪除一個(gè)名字Name及其屬性。及其屬性。1 一般想法一般想法“散列（散列（Hashing）” 的基本思想是：以數(shù)據(jù)對(duì)象的關(guān)鍵字的基本思想是：以數(shù)據(jù)對(duì)象的關(guān)鍵字key為自變量，通過(guò)一個(gè)確定的為自變量，通過(guò)一個(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ǔ)地址，并按此存放，即，

10、把這個(gè)值解釋為數(shù)據(jù)對(duì)象的存儲(chǔ)地址，并按此存放，即“存儲(chǔ)位置存儲(chǔ)位置 = h（key）”。 散列方法中使用的計(jì)算函數(shù)稱(chēng)為散列方法中使用的計(jì)算函數(shù)稱(chēng)為“散列函數(shù)散列函數(shù)” （也稱(chēng)哈希函數(shù)），（也稱(chēng)哈希函數(shù)），按這個(gè)思想構(gòu)造的表稱(chēng)為按這個(gè)思想構(gòu)造的表稱(chēng)為“散列表散列表”，所以它也是一種存儲(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)大于表空間的地址地址集集，所以說(shuō)，所以說(shuō)，沖突不可能避免，只能盡可能減少?zèng)_突不可能避免，只能盡可能減少。 可能將可能將不同的關(guān)鍵字映射到同一個(gè)散列地址不同的關(guān)鍵字映射到同一個(gè)散列地址上，即上，即h(keyi) = h(keyj)（當(dāng)（當(dāng)keyi keyj），這種現(xiàn)象稱(chēng)為），這種現(xiàn)象稱(chēng)為“沖突沖突(Collision)”， keyi 和和keyj稱(chēng)為稱(chēng)為“同義詞（同義詞（synonym）”。1 一般想法一般想法散列表散列表0 1 s 1 ht 0 ht 1 ht b 1 b bucketss slots 對(duì)每一個(gè)標(biāo)識(shí)符對(duì)每一個(gè)標(biāo)識(shí)符key,

12、我們我們定義一個(gè)定義一個(gè)hash函數(shù)（散列函數(shù)）函數(shù)（散列函數(shù)） h ( key ) = key 在在 ht 中的位置中的位置 (如：包含如：包含 key 的桶的索引號(hào)）的桶的索引號(hào)）1 一般想法一般想法例例4有有n = 11個(gè)數(shù)據(jù)對(duì)象的集合，關(guān)鍵詞是正整數(shù)，分別為個(gè)數(shù)據(jù)對(duì)象的集合，關(guān)鍵詞是正整數(shù)，分別為 18，23，11，20，2，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）其中其中m

13、od 是求余運(yùn)算，相當(dāng)于是求余運(yùn)算，相當(dāng)于C語(yǔ)言中的語(yǔ)言中的%運(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)鍵詞沒(méi)有沖突）如下：）如下： 查找時(shí)，對(duì)給定關(guān)鍵詞查找時(shí)，對(duì)給定關(guān)鍵詞keyi依然通過(guò)公式依然通過(guò)公式5.1計(jì)算出地址，再計(jì)算出地址，再將將keyi與該地址單元中關(guān)鍵詞比較，若相等，則查找成功。與該地址單元中關(guān)鍵詞比較，若相等，則查找成功。 比如查找：比如查找：key = 22, 地址是地址是22%17 = 5，該地址空表示表中，該地址空表示表中沒(méi)有關(guān)鍵詞沒(méi)有關(guān)鍵詞22的信息。的信息。比如查找：比如查找：k

14、ey = 40, 地址是地址是40%17 = 6，該地址存的是，該地址存的是23，40 23，故還要采用后面介紹的，故還要采用后面介紹的解決沖突解決沖突的策略才能確定。的策略才能確定。地址地址0123456789 10 11 12 13 14 15 16關(guān)鍵詞關(guān)鍵詞 34 18 2 2023 7 4227 113015【定義定義】 設(shè)散列表空間大小為設(shè)散列表空間大小為m，填入表中的元素個(gè)數(shù)是，填入表中的元素個(gè)數(shù)是n，則稱(chēng)，則稱(chēng) n / m為散列表的為散列表的“裝填因子（裝填因子（Loaf(i)ng Factor）”。 裝填因子裝填因子 11 / 17 0.65。 實(shí)用時(shí)，常將散列表大小設(shè)計(jì)使得

15、實(shí)用時(shí)，常將散列表大小設(shè)計(jì)使得 0.50.8為宜為宜。1 一般想法一般想法例例5將給定的將給定的10個(gè)個(gè)C語(yǔ)言中的關(guān)鍵詞語(yǔ)言中的關(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、floor、clock、ctime。散列表設(shè)計(jì)為一個(gè)散列表設(shè)計(jì)為一個(gè)二維數(shù)組二維數(shù)組Table262，2列分別代表列分別代表 2個(gè)槽。個(gè)槽。 槽槽 1槽槽 0012345625裝填因子裝填因子 ?10 / 52 = 0.19為了把字母為了把字母 a z 映射到映射到 0 25,

16、如何設(shè)計(jì)散列如何設(shè)計(jì)散列函數(shù)函數(shù)h (key ) = ? h(key) = key0 aacosacosdefinedefinefloatfloatexpexpcharcharatanatanceilceilfloorfloorclockctime如何設(shè)計(jì)如何設(shè)計(jì)散列函數(shù)散列函數(shù)，使得，使得發(fā)生發(fā)生沖突的概率沖突的概率盡可能?。勘M可能?。慨?dāng)當(dāng)沖突或溢出沖突或溢出不可避免時(shí)，不可避免時(shí)，如如何處理何處理使得表中沒(méi)有空單元被使得表中沒(méi)有空單元被浪費(fèi)，同時(shí)浪費(fèi)，同時(shí)插入、刪除、查找插入、刪除、查找等操作都能正確完成？等操作都能正確完成？1 一般想法一般想法h的特征的特征: h ( key ) 應(yīng)當(dāng)應(yīng)

17、當(dāng)易于易于計(jì)算，且使計(jì)算，且使沖突最少化沖突最少化。 h(key)應(yīng)當(dāng)是均勻的，也就是說(shuō)，對(duì)任意的應(yīng)當(dāng)是均勻的，也就是說(shuō)，對(duì)任意的key和任意的和任意的i，Probability( h(key)= i ) = 1 / b。這種類(lèi)型的散列函數(shù)被稱(chēng)。這種類(lèi)型的散列函數(shù)被稱(chēng)為為均勻哈希函數(shù)（均勻哈希函數(shù)（uniform hash function）。）。2 散列函數(shù)散列函數(shù)h(key)= key % TableSize ; /* 若若x是整數(shù)是整數(shù)*/ 如果如果 TableSize = 10 且且 key 都以都以0為個(gè)位，會(huì)怎樣呢為個(gè)位，會(huì)怎樣呢? TableSize = 素?cái)?shù)素?cái)?shù)- 當(dāng)關(guān)鍵字是隨

18、機(jī)整數(shù)時(shí)，是個(gè)當(dāng)關(guān)鍵字是隨機(jī)整數(shù)時(shí)，是個(gè)好的散列函數(shù)好的散列函數(shù)2 散列函數(shù)散列函數(shù)h(key)= ( keyi) % TableSize ; /* 若若x是字符串是字符串 */例例6 TableSize = 10,007 ，字符串長(zhǎng)度，字符串長(zhǎng)度 8. 如果如果 keyi 0, 127, 那么那么 h(key) 0, ? 1016h(key)= (key0+ key1*27 + key2*272) % TableSize ;總的組合數(shù)總的組合數(shù) （理論上）（理論上）= 263 = 17,576 實(shí)際組合數(shù)實(shí)際組合數(shù) 3000h(key)= ( keyN i 1 * 32i ) % Table

19、Size ;key0 key1keyN-2 keyN-1Index Hash3( const char *x, int TableSize ) unsigned int HashVal = 0; /* 1*/ while( *x != 0 ) /* 2*/ HashVal = ( HashVal 5 ) + *x+; /* 3*/ return HashVal % TableSize; 比比*27要快要快你能讓它更你能讓它更快嗎？快嗎？ 如果如果 key 太長(zhǎng)太長(zhǎng) (如：街道地址如：街道地址), 前面的字符會(huì)左移出前面的字符會(huì)左移出界。界。 選擇關(guān)鍵字選擇關(guān)鍵字中的部分字中的部分字符。符。2

20、散列函數(shù)散列函數(shù) 處理沖突的方法處理沖突的方法常用的處理沖突的方法有兩種：常用的處理沖突的方法有兩種：分離鏈接法；分離鏈接法；開(kāi)放定址法開(kāi)放定址法。分離鏈接法分離鏈接法（Separate Chaining）【定義定義】分離鏈接法是解決沖突的一種方法，其做法是將所有關(guān)分離鏈接法是解決沖突的一種方法，其做法是將所有關(guān)鍵詞為鍵詞為同義詞同義詞的數(shù)據(jù)對(duì)象通過(guò)結(jié)點(diǎn)鏈接存儲(chǔ)的數(shù)據(jù)對(duì)象通過(guò)結(jié)點(diǎn)鏈接存儲(chǔ)在同一個(gè)單鏈表中在同一個(gè)單鏈表中。struct ListNode; typedef struct ListNode *Position; struct HashTbl; typedef struct HashT

21、bl *HashTable; struct ListNode ElementType Element; Position Next; ; typedef Position List; /* List *TheList will be an array of lists, allocated later */ /* The lists use headers (for simplicity), */ /* though this wastes space */ struct HashTbl int TableSize; List *TheLists; ; 3 分離鏈接法分離鏈接法例例7設(shè)關(guān)鍵字序

22、列為設(shè)關(guān)鍵字序列為 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21; 散列函數(shù)取為：散列函數(shù)取為：h(key) = key mod 11。 用用分離鏈接法分離鏈接法處理沖突。處理沖突。 94 50 16 22 3 89 11 47 37 92 29 7 8 21 01 23 4567 8910H11HashTable InitializeTable( int TableSize ) HashTable H; int i; if ( TableSize TableSize = NextPrime( TableSize ); /* Bette

23、r be prime */ H-TheLists = malloc( sizeof( List ) * H-TableSize ); /*Array of lists*/ if ( H-TheLists = NULL ) FatalError( Out of space! ); for( i = 0; i TableSize; i+ ) /* Allocate list headers */H-TheLists i = malloc( sizeof( struct ListNode ) ); /* Slow! */if ( H-TheLists i = NULL ) FatalError( O

24、ut of space! ); else H-TheLists i -Next = NULL; return H; 3 分離鏈接法分離鏈接法 創(chuàng)建空散列表創(chuàng)建空散列表HTheListsTableSize3 分離鏈接法分離鏈接法 在散列表中查找在散列表中查找keyPosition Find ( ElementType Key, HashTable H ) Position P; List L; L = H-TheLists Hash( Key, H-TableSize ) ; P = L-Next; while( P != NULL & P-Element != Key ) /* Pro

25、bably need strcmp */ P = P-Next; return P; 你的散列函數(shù)你的散列函數(shù)等同于第三章中給出的執(zhí)行等同于第三章中給出的執(zhí)行Find 的的程序程序 - List ADT3 分離鏈接法分離鏈接法 向散列表中插入向散列表中插入 key void Insert ( ElementType Key, HashTable H ) Position Pos, NewCell; List L; Pos = Find( Key, H ); if ( Pos = NULL ) /* Key is not found, then insert */NewCell = malloc

26、( sizeof( struct ListNode ) ); if ( NewCell = NULL ) FatalError( Out of space! ); else L = H-TheLists Hash( Key, H-TableSize ) ; NewCell-Next = L-Next; NewCell-Element = Key; /* Probably need strcpy! */ L-Next = NewCell; 再一次再一次?! Tip: 使表的大小與預(yù)期的使表的大小與預(yù)期的keys的數(shù)量大致相等的數(shù)量大致相等 (即使裝填因子即使裝填因子 1). 開(kāi)放定址法（開(kāi)放定址

27、法（Open Addressing）【定義定義】所謂開(kāi)放定址法，就是一旦產(chǎn)生了所謂開(kāi)放定址法，就是一旦產(chǎn)生了沖突沖突，即該地址，即該地址已經(jīng)存放了其它數(shù)據(jù)元素，就去已經(jīng)存放了其它數(shù)據(jù)元素，就去尋找另一個(gè)空的散列地址尋找另一個(gè)空的散列地址。 若發(fā)生了第若發(fā)生了第 i 次沖突，試探的下一個(gè)地址將增加次沖突，試探的下一個(gè)地址將增加f(i)，基本公式是：基本公式是：hi(key) = (h(key)+f(i) mod TableSize ( 1 i TableSize ) f(i)決定了不同的解決沖突方案：決定了不同的解決沖突方案：線性探測(cè)、二次探測(cè)、雙散列線性探測(cè)、二次探測(cè)、雙散列。在在沒(méi)有裝滿(mǎn)沒(méi)有

28、裝滿(mǎn)的散列表中，的散列表中，空的散列地址空的散列地址是否總能找到是否總能找到？f(i)= if(i) = i2f(i) = i*h2(key)Algorithm: insert key into an array of hash table index = hash(key); initialize i = 0 - the counter of probing; while ( collision at index ) index = ( hash(key) + f(i) ) % TableSize;if ( table is full ) break;else i +; if ( table

29、 is full )ERROR (“No space left”); elseinsert key at index;沖突解決函數(shù)沖突解決函數(shù)f(0) = 0. Tip: 平均平均 0.5.例例8 將將n = 11個(gè)個(gè)C的庫(kù)函數(shù)映射到一個(gè)散列表的庫(kù)函數(shù)映射到一個(gè)散列表 ht ，其中，其中b = 26 buckets ， s = 1.1. 線性探測(cè)法線性探測(cè)法（Linear Probing） 以以增量序列增量序列 1，2，（，（TableSize -1）循環(huán)試探下一個(gè)存儲(chǔ)地址。循環(huán)試探下一個(gè)存儲(chǔ)地址。4 開(kāi)放定址法開(kāi)放定址法f ( i ) = i ; /* 線性函數(shù)線性函數(shù) */acos ato

30、i char define exp ceil cos float atol floor ctimebucketx012345678910 25search timeacos1atoi2char1define1exp1ceil4cos5float3atol9floor5ctime9裝填因子裝填因子 = 11 / 26 = 0.42平均搜索次數(shù)平均搜索次數(shù) = 41 / 11 = 3.73雖然雖然 p 不大不大,但最壞情形可能會(huì)但最壞情形可能會(huì)很大很大.使用線性探測(cè)的使用線性探測(cè)的預(yù)期探測(cè)次數(shù)：預(yù)期探測(cè)次數(shù)： 對(duì)對(duì)成成功功的的查查找找 ) )1 1( (對(duì)對(duì)插插入入和和不不成成功功的的查查找找 )

31、 )1 1( (1 11 12 21 1) )1 1( (1 12 21 12 2 p p= 1.36造成一造成一次聚集次聚集( primary clustering): 散列到區(qū)塊中的任何散列到區(qū)塊中的任何key都需要多次都需要多次試選單元才能解決沖突，然后該關(guān)試選單元才能解決沖突，然后該關(guān)鍵字才被添加到相應(yīng)區(qū)塊中鍵字才被添加到相應(yīng)區(qū)塊中例例9設(shè)關(guān)鍵詞序列為設(shè)關(guān)鍵詞序列為 47，7，29，11，9，84，54，20，30， 散列表表長(zhǎng)散列表表長(zhǎng)TableSize =13， 裝填因子裝填因子 = 9/13 0.69； 散列函數(shù)為：散列函數(shù)為：h(key) = key mod 11。 用用線性探

32、測(cè)法線性探測(cè)法處理沖突，列出依次插入后的散列表，處理沖突，列出依次插入后的散列表， 并估算查找性能。并估算查找性能。關(guān)鍵詞關(guān)鍵詞 (key)4772911984542030散散列地址列地址 h(key)37709710984 開(kāi)放定址法開(kāi)放定址法地址地址操作操作0123456789101112說(shuō)說(shuō) 明明插入插入4747無(wú)沖突無(wú)沖突插入插入7477無(wú)沖突無(wú)沖突插入插入2947729d1 = 1插入插入111147729無(wú)沖突無(wú)沖突插入插入911477299無(wú)沖突無(wú)沖突插入插入841147729984d3 = 3插入插入54114772998454d1 = 1插入插入201147729984542

33、0d3 = 3插入插入30113047 7299845420d6 = 6“一次聚集一次聚集（Primary Clustering）”現(xiàn)象：需要經(jīng)過(guò)現(xiàn)象：需要經(jīng)過(guò)很很多次沖突多次沖突才找到空位置。才找到空位置。表表線性探測(cè)法構(gòu)建散列表的過(guò)程線性探測(cè)法構(gòu)建散列表的過(guò)程關(guān)鍵詞關(guān)鍵詞 (key)4772911984542030散散列地址列地址 h(key)3770971098沖突次數(shù)沖突次數(shù)0010031364 開(kāi)放定址法開(kāi)放定址法 圖圖5-12表示了期望探測(cè)次數(shù)與裝填因子表示了期望探測(cè)次數(shù)與裝填因子 的關(guān)系。的關(guān)系。圖圖5-12 線性探測(cè)法（虛線）、隨機(jī)方法（實(shí)線）線性探測(cè)法（虛線）、隨機(jī)方法（實(shí)線

34、）U表示不成功查找，表示不成功查找，I表示插入，表示插入，S表示成功查找表示成功查找當(dāng)裝填因子當(dāng)裝填因子 0.5的時(shí)候，各的時(shí)候，各種探測(cè)法的種探測(cè)法的期望探測(cè)次數(shù)都期望探測(cè)次數(shù)都不大不大，也比較接近。，也比較接近。隨著隨著 的增大，線性探測(cè)法的期望的增大，線性探測(cè)法的期望探測(cè)次數(shù)增加較快，探測(cè)次數(shù)增加較快，不成功查找和不成功查找和插入操作插入操作的期望探測(cè)次數(shù)比成功查的期望探測(cè)次數(shù)比成功查找的期望探測(cè)次數(shù)找的期望探測(cè)次數(shù)要大要大。合理的的最大裝入因子應(yīng)合理的的最大裝入因子應(yīng)該該不超過(guò)不超過(guò)0.85。2. 平方探測(cè)法平方探測(cè)法（Quadratic Probing） 即即平方探測(cè)法平方探測(cè)法以增

35、量序列以增量序列12，-12，22，-22，q2，-q2且且q TableSize/2 循環(huán)試探下一個(gè)存儲(chǔ)地址。循環(huán)試探下一個(gè)存儲(chǔ)地址。4 開(kāi)放定址法開(kāi)放定址法f ( i ) = i 2 ; /* 一個(gè)平方函數(shù)一個(gè)平方函數(shù)*/例例10設(shè)關(guān)鍵詞序列為設(shè)關(guān)鍵詞序列為 47，7，29，11，9，84，54，20，30 散列表表長(zhǎng)散列表表長(zhǎng)TableSize = 11（即滿(mǎn)足（即滿(mǎn)足42+3形式的素?cái)?shù)）形式的素?cái)?shù)） 裝填因子裝填因子 = 9/11 0.82 散列函數(shù)為：散列函數(shù)為：h(key) = key mod 11 用用平方探測(cè)法平方探測(cè)法處理沖突，列出依次插入后的散列表處理沖突，列出依次插入后的

36、散列表關(guān)鍵詞關(guān)鍵詞 key4772911984542030散散列地址列地址h(key)3770971098表平方探測(cè)法構(gòu)建散列表的過(guò)程表平方探測(cè)法構(gòu)建散列表的過(guò)程地址地址操作操作012345678910說(shuō)說(shuō) 明明插入插入4747無(wú)沖突無(wú)沖突插入插入7477無(wú)沖突無(wú)沖突插入插入2947729d1 = 1插入插入111147729無(wú)沖突無(wú)沖突插入插入911477299無(wú)沖突無(wú)沖突插入插入841147847299d2 = -1插入插入54114784729954無(wú)沖突無(wú)沖突插入插入2011204784729954d3 = 4插入插入3011302047 84729954d3 = 4“二次聚集二次聚集

37、（Secondary Clustering） ”現(xiàn)象：現(xiàn)象：散列到同一地址的那些數(shù)據(jù)對(duì)象散列到同一地址的那些數(shù)據(jù)對(duì)象將探測(cè)相同的備選單元將探測(cè)相同的備選單元。關(guān)鍵詞關(guān)鍵詞 key4772911984542030散散列地址列地址h(key)3770971098沖突次數(shù)沖突次數(shù)0010020334 開(kāi)放定址法開(kāi)放定址法30【定理定理】如果使用平方探測(cè)，且表的大小是如果使用平方探測(cè)，且表的大小是素?cái)?shù)素?cái)?shù)，那么當(dāng)表，那么當(dāng)表至少有一至少有一半是空半是空的時(shí)候，總能夠插入一個(gè)新元素。的時(shí)候，總能夠插入一個(gè)新元素。證明證明: 證明前證明前 TableSize/2 個(gè)備選位置是個(gè)備選位置是互異的互異的。即對(duì)

38、任意。即對(duì)任意 0 TableSize ); while( H-TheCells CurrentPos .Info != Empty & H-TheCells CurrentPos .Element != Key ) CurrentPos += 2 * +CollisionNum 1; if ( CurrentPos = H-TableSize ) CurrentPos = H-TableSize; return CurrentPos; 比比mod快快返回結(jié)果是什么返回結(jié)果是什么?f(i)=f(i 1)+2i 12* 是移位操作是移位操作如果這兩個(gè)條件如果這兩個(gè)條件交換會(huì)怎樣？交換會(huì)怎

39、樣？4 開(kāi)放定址法開(kāi)放定址法void Insert ( ElementType Key, HashTable H ) Position Pos; Pos = Find( Key, H ); if ( H-TheCells Pos .Info != Legitimate ) /* OK to insert here */ H-TheCells Pos .Info = Legitimate; H-TheCells Pos .Element = Key; /* Probably need strcpy */ Question: 怎樣刪除怎樣刪除key?Note: 如果如果插入和刪除混合的插入和刪除混合的次數(shù)過(guò)多，插入會(huì)明顯變慢。次數(shù)過(guò)多，插入會(huì)明顯變慢。 即使一次聚集問(wèn)題解決了，即使一次聚集問(wèn)題解決了，二次聚集二次聚集問(wèn)題仍然存在。問(wèn)題仍然存在。3. 雙散列探測(cè)法雙散列探測(cè)