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

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

2、人？，以確定你就是該號碼的主人？【分析分析】看看是否可以用看看是否可以用二分法二分法查找。查找。 十億十億（109 230）有效用戶，用二分查找有效用戶，用二分查找30次次。 十億十億（109 230） 1K 1024G，1T連續(xù)空間。連續(xù)空間。 按有效按有效QQ號大小號大小有有序存儲序存儲：在連續(xù)存儲空間中，在連續(xù)存儲空間中，插插入和刪除入和刪除一個新一個新QQ號碼將需要號碼將需要移動大量數(shù)據(jù)移動大量數(shù)據(jù)。用不了二分查找，用不了二分查找，我們該怎么辦？我們該怎么辦？1 一般想法一般想法例例2查英文字典的過程查英文字典的過程查詢英文單詞查詢英文單詞“zoo”，你為什么不用二分法，而直接從字典的

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

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)系。如何在這個巨大無比的表格如何在這個巨大無比的表格中查找特定的關(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【問題問題】如何能夠在極短的時間內(nèi)（比如如何能夠在極短的時間內(nèi)（比如1秒內(nèi)）搜索到需要的關(guān)鍵詞？秒內(nèi)）搜索到需要的關(guān)鍵詞？ 1 一般想法一般想法 散列查找法的兩項基本工作：散列查找法的兩項基本工作：構(gòu)造散列函數(shù)：構(gòu)造散列函數(shù)：確定關(guān)鍵詞所在的存儲位置的確定關(guān)鍵詞所在的存儲位置的計算方法計算方法； 解決沖突：解決沖突：當(dāng)多個關(guān)鍵詞所在的存儲位置相同時的解決方法。當(dāng)多個關(guān)鍵詞所在的存儲位置相同時的解決方法?！敬鸢复鸢浮可⒘胁檎曳ㄉ⒘胁檎曳ㄊ鞘呛芎煤芎梅椒ㄖ?/p>

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

7、me)-屬性屬性(Attribute)”對的集合。對的集合。操作集：操作集：對于一個符號表對于一個符號表Table SymbolTable，一個給定名字，一個給定名字Name NameType，屬性，屬性Attr AttributeType，以及正整數(shù)，以及正整數(shù)TableSize，符號表的基本操作主要有：，符號表的基本操作主要有：1、SymbolTable InitializeTable( int TableSize )：創(chuàng)建一個長度為：創(chuàng)建一個長度為TableSize的符號表；的符號表；2、Boolean IsIn( SymbolTable Table, NameType Name)： 查

8、找特定的名字查找特定的名字Name是否在符號表是否在符號表Table中；中；3、AttributeType Find( SymbolTable Table, NameType Name)： 獲取獲取Table中指定名字中指定名字Name對應(yīng)的屬性；對應(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中插入一個新名字中插入一個新名字Name及其屬性及其屬性Attr；6、 SymbolTable Delete(SymbolTable Table, NameType Name)： 從從Table中刪除一個名字中刪除一個名字Name及其屬性。及其屬性。1 一般想法一般想法“散列（散列（Hashing）” 的基本思想是：以數(shù)據(jù)對象的關(guān)鍵字的基本思想是：以數(shù)據(jù)對象的關(guān)鍵字key為自變量，通過一個確定的為自變量，通過一個確定的函數(shù)關(guān)系函數(shù)關(guān)系 h，計算出對應(yīng)的函數(shù)值，計算出對應(yīng)的函數(shù)值h(key)，把這個值解釋為數(shù)據(jù)對象的存儲地址，并按此存放，即，

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

11、允許取值的范圍）遠遠大于表空間的（允許取值的范圍）遠遠大于表空間的地址地址集集，所以說，所以說，沖突不可能避免，只能盡可能減少沖突不可能避免，只能盡可能減少。 可能將可能將不同的關(guān)鍵字映射到同一個散列地址不同的關(guān)鍵字映射到同一個散列地址上，即上，即h(keyi) = h(keyj)（當(dāng)（當(dāng)keyi keyj），這種現(xiàn)象稱為），這種現(xiàn)象稱為“沖突沖突(Collision)”， keyi 和和keyj稱為稱為“同義詞（同義詞（synonym）”。1 一般想法一般想法散列表散列表0 1 s 1 ht 0 ht 1 ht b 1 b bucketss slots 對每一個標(biāo)識符對每一個標(biāo)識符key,

12、我們我們定義一個定義一個hash函數(shù)（散列函數(shù)）函數(shù)（散列函數(shù)） h ( key ) = key 在在 ht 中的位置中的位置 (如：包含如：包含 key 的桶的索引號）的桶的索引號）1 一般想法一般想法例例4有有n = 11個數(shù)據(jù)對象的集合，關(guān)鍵詞是正整數(shù)，分別為個數(shù)據(jù)對象的集合，關(guān)鍵詞是正整數(shù)，分別為 18，23，11，20，2，7，27，30，42，15，34。如果符號表的。如果符號表的大小用大小用TableSize = 17（通常用一個素數(shù)），選取散列函數(shù)（通常用一個素數(shù)），選取散列函數(shù)h如下：如下：h(key) = key mod TableSize （公式（公式 5.1）其中其中m

13、od 是求余運算，相當(dāng)于是求余運算，相當(dāng)于C語言中的語言中的%運算。運算。用這個散列函數(shù)對用這個散列函數(shù)對11個數(shù)據(jù)對象建立查找表（個數(shù)據(jù)對象建立查找表（忽略各關(guān)鍵詞對應(yīng)的屬性部分，該例的關(guān)鍵詞沒有沖突）如下：）如下： 查找時，對給定關(guān)鍵詞查找時，對給定關(guān)鍵詞keyi依然通過公式依然通過公式5.1計算出地址，再計算出地址，再將將keyi與該地址單元中關(guān)鍵詞比較，若相等，則查找成功。與該地址單元中關(guān)鍵詞比較，若相等，則查找成功。 比如查找：比如查找：key = 22, 地址是地址是22%17 = 5，該地址空表示表中，該地址空表示表中沒有關(guān)鍵詞沒有關(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，填入表中的元素個數(shù)是，填入表中的元素個數(shù)是n，則稱，則稱 n / m為散列表的為散列表的“裝填因子（裝填因子（Loaf(i)ng Factor）”。 裝填因子裝填因子 11 / 17 0.65。 實用時，常將散列表大小設(shè)計使得

15、實用時，常將散列表大小設(shè)計使得 0.50.8為宜為宜。1 一般想法一般想法例例5將給定的將給定的10個個C語言中的關(guān)鍵詞語言中的關(guān)鍵詞(保留字或標(biāo)準(zhǔn)函數(shù)名保留字或標(biāo)準(zhǔn)函數(shù)名)順次存入一張散列表。這順次存入一張散列表。這10個關(guān)鍵詞為：個關(guān)鍵詞為：acos、define、float、exp、char、atan、ceil、floor、clock、ctime。散列表設(shè)計為一個散列表設(shè)計為一個二維數(shù)組二維數(shù)組Table262，2列分別代表列分別代表 2個槽。個槽。 槽槽 1槽槽 0012345625裝填因子裝填因子 ?10 / 52 = 0.19為了把字母為了把字母 a z 映射到映射到 0 25,

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

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

18、機整數(shù)時，是個當(dāng)關(guān)鍵字是隨機整數(shù)時，是個好的散列函數(shù)好的散列函數(shù)2 散列函數(shù)散列函數(shù)h(key)= ( keyi) % TableSize ; /* 若若x是字符串是字符串 */例例6 TableSize = 10,007 ，字符串長度，字符串長度 8. 如果如果 keyi 0, 127, 那么那么 h(key) 0, ? 1016h(key)= (key0+ key1*27 + key2*272) % TableSize ;總的組合數(shù)總的組合數(shù) （理論上）（理論上）= 263 = 17,576 實際組合數(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 太長太長 (如：街道地址如：街道地址), 前面的字符會左移出前面的字符會左移出界。界。 選擇關(guān)鍵字選擇關(guān)鍵字中的部分字中的部分字符。符。2

20、散列函數(shù)散列函數(shù) 處理沖突的方法處理沖突的方法常用的處理沖突的方法有兩種：常用的處理沖突的方法有兩種：分離鏈接法；分離鏈接法；開放定址法開放定址法。分離鏈接法分離鏈接法（Separate Chaining）【定義定義】分離鏈接法是解決沖突的一種方法，其做法是將所有關(guān)分離鏈接法是解決沖突的一種方法，其做法是將所有關(guān)鍵詞為鍵詞為同義詞同義詞的數(shù)據(jù)對象通過結(jié)點鏈接存儲的數(shù)據(jù)對象通過結(jié)點鏈接存儲在同一個單鏈表中在同一個單鏈表中。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). 開放定址法（開放定址

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

28、裝滿的散列表中，的散列表中，空的散列地址空的散列地址是否總能找到是否總能找到？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個個C的庫函數(shù)映射到一個散列表的庫函數(shù)映射到一個散列表 ht ，其中，其中b = 26 buckets ， s = 1.1. 線性探測法線性探測法（Linear Probing） 以以增量序列增量序列 1，2，（，（TableSize -1）循環(huán)試探下一個存儲地址。循環(huán)試探下一個存儲地址。4 開放定址法開放定址法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 不大不大,但最壞情形可能會但最壞情形可能會很大很大.使用線性探測的使用線性探測的預(yù)期探測次數(shù)：預(yù)期探測次數(shù)： 對對成成功功的的查查找找 ) )1 1( (對對插插入入和和不不成成功功的的查查找找 )

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， 散列表表長散列表表長TableSize =13， 裝填因子裝填因子 = 9/13 0.69； 散列函數(shù)為：散列函數(shù)為：h(key) = key mod 11。 用用線性探

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

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

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

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

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

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

38、任意。即對任意 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* 是移位操作是移位操作如果這兩個條件如果這兩個條件交換會怎樣？交換會怎

39、樣？4 開放定址法開放定址法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ù)過多，插入會明顯變慢。次數(shù)過多，插入會明顯變慢。 即使一次聚集問題解決了，即使一次聚集問題解決了，二次聚集二次聚集問題仍然存在。問題仍然存在。3. 雙散列探測法雙散列探測