理學(xué)哈希表查找PPT學(xué)習(xí)教案

1、會計學(xué)1 理學(xué)哈希表查找理學(xué)哈希表查找 理想的情況是希望不經(jīng)過任何比較，一次理想的情況是希望不經(jīng)過任何比較，一次 存取便能夠得到所查記錄，那就必須在記錄的存取便能夠得到所查記錄，那就必須在記錄的 存儲位置上和它的關(guān)鍵字之間建立一個確定的存儲位置上和它的關(guān)鍵字之間建立一個確定的 對應(yīng)關(guān)系對應(yīng)關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一 的存儲位置相對應(yīng)。因而在查找時，只要根據(jù)的存儲位置相對應(yīng)。因而在查找時，只要根據(jù) 第1頁/共55頁 第2頁/共55頁 而而使用哈希表進(jìn)行查找的方法稱為哈希查找。使用哈希表進(jìn)行查找的方法稱為哈希查找。 因此，其查找時間與計算地址的函數(shù)有關(guān)。因此，

2、其查找時間與計算地址的函數(shù)有關(guān)。 假設(shè)假設(shè)table是一個包含是一個包含n個元素的線性表，個元素的線性表，Ri 為表中的某個元素（為表中的某個元素（1=i=n），），keyi是其關(guān)鍵是其關(guān)鍵 字值，若在關(guān)鍵字值字值，若在關(guān)鍵字值keyi與元素與元素Ri的地址（即的地址（即 在線性表中的位置）之間建立某種函數(shù)關(guān)系，在線性表中的位置）之間建立某種函數(shù)關(guān)系， 第3頁/共55頁 則可以通過這個函數(shù)，把關(guān)鍵字值轉(zhuǎn)換成相應(yīng)則可以通過這個函數(shù)，把關(guān)鍵字值轉(zhuǎn)換成相應(yīng) 元素在表中的地址，即元素在表中的地址，即 Addr(Ri)=H(keyi) 其中，其中，Addr(Ri)為為Ri的地址，函數(shù)的地址，函數(shù) H 稱

3、為哈希稱為哈希 （Hash）函數(shù)（散列函數(shù)），函數(shù)（散列函數(shù)）， 稱稱H(keyi) 的值的值 為哈希地址（散列地址）。為哈希地址（散列地址）。 第4頁/共55頁 第5頁/共55頁 在進(jìn)行查找之前，我們先來了解如何構(gòu)造哈在進(jìn)行查找之前，我們先來了解如何構(gòu)造哈 希表。希表。例如：假定一個線性表為例如：假定一個線性表為 S=18S=18，7575，6060，4343，5454，9090，4646，6767 將其存儲到數(shù)組將其存儲到數(shù)組H13中，如下圖所示：中，如下圖所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 545467 4318 4660 7590 H 表一表一 哈希表哈希

4、表H13 第6頁/共55頁 若哈希函數(shù)定義為若哈希函數(shù)定義為H（key）=key%13,則查則查 找找 過程就是一個求過程就是一個求H（key）的值的過程，如查找的值的過程，如查找 75，則，則H（75）=75%13=10，說明說明H10存放存放 著著 75。若查找。若查找90， H（90）=90%13=12，說明說明 H12存放著存放著90。 第7頁/共55頁 若根據(jù)哈希函數(shù)，把元素存放到線性表中相若根據(jù)哈希函數(shù)，把元素存放到線性表中相 應(yīng)的位置上，這樣形成的表便稱為應(yīng)的位置上，這樣形成的表便稱為哈希表哈希表，又，又 叫叫散列表。散列表。哈希表的查找是以同樣的方式進(jìn)行哈希表的查找是以同樣的方

5、式進(jìn)行 的。的。 若某個哈希函數(shù)對于不同的關(guān)鍵字值若某個哈希函數(shù)對于不同的關(guān)鍵字值keykey1 1和和 keykey2 2，得到相同的散列地址，得到相同的散列地址， 第8頁/共55頁 第9頁/共55頁 解決沖突就是為對應(yīng)到同一地址的多個同解決沖突就是為對應(yīng)到同一地址的多個同 義詞安排存儲位置，因此，在選定哈希函數(shù)時義詞安排存儲位置，因此，在選定哈希函數(shù)時 應(yīng)考慮避免沖突，也就是說，一個好的哈希函應(yīng)考慮避免沖突，也就是說，一個好的哈希函 數(shù)能將關(guān)鍵字值均勻地分布在整個地址空間，數(shù)能將關(guān)鍵字值均勻地分布在整個地址空間， 使產(chǎn)生沖突機會盡量減少，同時，選定一個解使產(chǎn)生沖突機會盡量減少，同時，選定一

6、個解 決沖突的方法，即對同義詞再次找到一個空間決沖突的方法，即對同義詞再次找到一個空間 地址，存放該元素。地址，存放該元素。 第10頁/共55頁 綜上所述，綜上所述，哈希表是根據(jù)設(shè)定的哈希函哈希表是根據(jù)設(shè)定的哈希函 數(shù)和解決沖突的方法，為一組元素建立一張數(shù)和解決沖突的方法，為一組元素建立一張 表，每個元素在表中的位置依賴于設(shè)定的哈表，每個元素在表中的位置依賴于設(shè)定的哈 希函數(shù)和解決沖突的方法。希函數(shù)和解決沖突的方法。 第11頁/共55頁 8.3.2 8.3.2 哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法 構(gòu)造哈希函數(shù)的方法很多，在講述各種構(gòu)造哈希函數(shù)的方法很多，在講述各種 方法之前，首先需要明確什么

7、是方法之前，首先需要明確什么是“好好”的哈的哈 希希 函數(shù)。函數(shù)。 若對于關(guān)鍵字集合中的任一個關(guān)鍵字，若對于關(guān)鍵字集合中的任一個關(guān)鍵字， 經(jīng)哈希函數(shù)映像到地址集合中任何一個地址經(jīng)哈希函數(shù)映像到地址集合中任何一個地址 的概率是相等的，則稱此類哈希函數(shù)為均勻的概率是相等的，則稱此類哈希函數(shù)為均勻 第12頁/共55頁 第13頁/共55頁 1 1、直接地址法（這種哈希函數(shù)叫做自身函數(shù)）、直接地址法（這種哈希函數(shù)叫做自身函數(shù)） 哈希函數(shù)哈希函數(shù)H對于關(guān)鍵字是數(shù)字類型的元素，對于關(guān)鍵字是數(shù)字類型的元素， 直接利用關(guān)鍵字求得哈希地址。直接利用關(guān)鍵字求得哈希地址。 H（key）=key 或或 H（key）=a

8、key+b 在使用時，為了使哈希地址與存儲空間吻合在使用時，為了使哈希地址與存儲空間吻合 ，可以調(diào)整，可以調(diào)整a和和b的值，的值，a,b為常數(shù)。為常數(shù)。 第14頁/共55頁 地 址12.23. 年 份19491950.1971 人 數(shù) 例如：對解放后出生的人口調(diào)查，關(guān)鍵字作為例如：對解放后出生的人口調(diào)查，關(guān)鍵字作為 出生年份，可以構(gòu)造哈希函數(shù)為出生年份，可以構(gòu)造哈希函數(shù)為 H（K）=k-1948。 則哈希表如下圖所示：則哈希表如下圖所示： 圖一圖一 直接地址法構(gòu)造哈希函數(shù)直接地址法構(gòu)造哈希函數(shù) 第15頁/共55頁 分析：分析：該方法計算簡單，一個關(guān)鍵字對應(yīng)一該方法計算簡單，一個關(guān)鍵字對應(yīng)一 個

9、個 存儲地址，不會產(chǎn)生沖突，這種方法適用于存儲地址，不會產(chǎn)生沖突，這種方法適用于 關(guān)關(guān) 鍵字分布連續(xù)的情況，但在實際應(yīng)用中有一鍵字分布連續(xù)的情況，但在實際應(yīng)用中有一 定定 的局限性。的局限性。 2、數(shù)字分析法、數(shù)字分析法 數(shù)字分析法是先分析關(guān)鍵字中每一位數(shù)碼數(shù)字分析法是先分析關(guān)鍵字中每一位數(shù)碼 的分布情況，取關(guān)鍵字中某些數(shù)碼分布均勻的的分布情況，取關(guān)鍵字中某些數(shù)碼分布均勻的 第16頁/共55頁 若干位作為哈希地址，它要求可能出現(xiàn)的關(guān)鍵若干位作為哈希地址，它要求可能出現(xiàn)的關(guān)鍵 字事先知道的情況。字事先知道的情況。 例如：以下一組關(guān)鍵字由例如：以下一組關(guān)鍵字由7位十進(jìn)制構(gòu)成。位十進(jìn)制構(gòu)成。 第17

10、頁/共55頁 K1 7 2 0 5 1 6 1 K2 7 2 1 1 2 4 2 K3 7 2 0 2 0 3 2 K4 7 2 1 2 3 0 2 K5 7 2 0 3 1 5 1 K6 7 2 0 4 2 1 2 K7 7 2 0 7 0 2 1 K8 7 2 0 6 0 8 1 第18頁/共55頁 我們對關(guān)鍵字的每一位數(shù)字分析發(fā)現(xiàn)，第我們對關(guān)鍵字的每一位數(shù)字分析發(fā)現(xiàn)，第 位都是數(shù)字位都是數(shù)字7和和2；第；第位的數(shù)字只取位的數(shù)字只取0和和1 ；第；第位的數(shù)字取位的數(shù)字取0，1，2和和3；第；第位的數(shù)字位的數(shù)字 取取1和和2，因此第，因此第幾位都不取，而第幾位都不取，而第 位的數(shù)字分布均勻。

11、我們?nèi)∥坏臄?shù)字分布均勻。我們?nèi)?兩位數(shù)字兩位數(shù)字 為哈希地址。所有元素的哈希地址得出的結(jié)果為哈希地址。所有元素的哈希地址得出的結(jié)果 如下：如下： H（k1）=56 H（k2）=14 H（k3） =23 第19頁/共55頁 H（k4）=20 H（k5）=35 H（k6） =41 H（k7）=72 H（k8）=68 當(dāng)均勻分布的位數(shù)較多時，可取其中任意當(dāng)均勻分布的位數(shù)較多時，可取其中任意 兩位或其中兩位與另外兩位的疊加求和，并舍兩位或其中兩位與另外兩位的疊加求和，并舍 去進(jìn)位來作為哈希地址，但是如果某些數(shù)字重去進(jìn)位來作為哈希地址，但是如果某些數(shù)字重 復(fù)頻度都很高，無法使用數(shù)字選擇法得到均勻復(fù)頻度都

12、很高，無法使用數(shù)字選擇法得到均勻 的哈希函數(shù)。的哈希函數(shù)。 第20頁/共55頁 3、平方取中法、平方取中法 平方取中法是指取關(guān)鍵字平方后的中間幾平方取中法是指取關(guān)鍵字平方后的中間幾 位為哈希地址，一個數(shù)的平方數(shù)與該數(shù)的每一位為哈希地址，一個數(shù)的平方數(shù)與該數(shù)的每一 位數(shù)都有關(guān)，所選取的位數(shù)與表長有關(guān)。例如位數(shù)都有關(guān)，所選取的位數(shù)與表長有關(guān)。例如 哈希表長哈希表長1000，如下圖所示：，如下圖所示： 第21頁/共55頁 分析：分析：平方取中法適用于關(guān)鍵字中每一位的取值平方取中法適用于關(guān)鍵字中每一位的取值 都不夠分散或分散的位數(shù)小于哈希地址所需要的都不夠分散或分散的位數(shù)小于哈希地址所需要的 位數(shù)的情

13、況。位數(shù)的情況。 關(guān)鍵字平方數(shù)哈希地址 1324 2541 1436 . 1752976 6456681 2062096 . 529 566 620 第22頁/共55頁 去最高進(jìn)去最高進(jìn) 位）作為哈希地址。位）作為哈希地址。 第23頁/共55頁 折疊法中進(jìn)行疊加有兩種方法：一種為移位疊折疊法中進(jìn)行疊加有兩種方法：一種為移位疊 加，指分割后的每一段最低位對齊相加，最高加，指分割后的每一段最低位對齊相加，最高 位舍去；一種為間界疊加，指從一端向另一端位舍去；一種為間界疊加，指從一端向另一端 沿分割界來回折疊后對齊相加。沿分割界來回折疊后對齊相加。 例如：哈希表長為例如：哈希表長為1000時，關(guān)鍵字

14、時，關(guān)鍵字 k=230203700904121,則則15位數(shù)字以每段位數(shù)字以每段3位分成位分成 5 段，每段數(shù)字為段，每段數(shù)字為230，203，700，904，121。 第24頁/共55頁 這兩種疊加的過程如下圖所示：這兩種疊加的過程如下圖所示： 移位疊加移位疊加間界疊加間界疊加 230 203 700 904 +） 121 （2）158 230 302 700 409 +） 121 （1）762 第25頁/共55頁 其中高位舍去后，對應(yīng)的哈希地址為其中高位舍去后，對應(yīng)的哈希地址為158和和762 。 折疊法適用于關(guān)鍵字位數(shù)多，而對應(yīng)的哈希地折疊法適用于關(guān)鍵字位數(shù)多，而對應(yīng)的哈希地 址的位數(shù)要

15、求較少的情況。址的位數(shù)要求較少的情況。 第26頁/共55頁 等運算之后等運算之后 取模。取模。 第27頁/共55頁 一般地，一般地，m是哈希表的長度，它的取值在是哈希表的長度，它的取值在 1.1n1.7n之間。之間。 注意：在使用此種方法時，對注意：在使用此種方法時，對m的選擇很重要的選擇很重要 。 若選擇不好，容易產(chǎn)生同義詞，從而產(chǎn)生沖突若選擇不好，容易產(chǎn)生同義詞，從而產(chǎn)生沖突 。 第28頁/共55頁 第29頁/共55頁 以上介紹了建立哈希函數(shù)產(chǎn)生哈希地址的方以上介紹了建立哈希函數(shù)產(chǎn)生哈希地址的方 法，在實際應(yīng)用中，應(yīng)根據(jù)關(guān)鍵字的特點，確定法，在實際應(yīng)用中，應(yīng)根據(jù)關(guān)鍵字的特點，確定 適當(dāng)?shù)姆?/p>

16、法，還可以根據(jù)具體情況構(gòu)造出滿足需適當(dāng)?shù)姆椒?，還可以根據(jù)具體情況構(gòu)造出滿足需 要的隨機性能好的哈希函數(shù)。要的隨機性能好的哈希函數(shù)。 第30頁/共55頁 9.3.3 處理沖突的方法處理沖突的方法 在前面已經(jīng)講過，均勻的哈希函數(shù)可以在前面已經(jīng)講過，均勻的哈希函數(shù)可以 減少沖突，但不能夠避免，因而解決沖突的減少沖突，但不能夠避免，因而解決沖突的 問題尤為重要。問題尤為重要。 假設(shè)哈希表的地址范圍為假設(shè)哈希表的地址范圍為0.m-1,沖突是沖突是 指由關(guān)鍵字得到的哈希地址為指由關(guān)鍵字得到的哈希地址為j（0=j=m-1） 的位置上已有關(guān)鍵字記錄，則的位置上已有關(guān)鍵字記錄，則“處理沖突處理沖突”就就 第31

17、頁/共55頁 是為該關(guān)鍵字的記錄找到另一個空的哈希地址。是為該關(guān)鍵字的記錄找到另一個空的哈希地址。 在處理沖突的過程中可能得到一個地址序列在處理沖突的過程中可能得到一個地址序列Hi i=1,2,3,k(Hi屬于屬于0，m-1),即在處理哈希地即在處理哈希地 址的沖突時，若得到的另一個哈希地址址的沖突時，若得到的另一個哈希地址H1仍然仍然 發(fā)發(fā) 生沖突，則在求下一個地址生沖突，則在求下一個地址H2，若仍然沖突，若仍然沖突， 在在 求求H3。依次類推，直至不發(fā)生沖突為止。依次類推，直至不發(fā)生沖突為止。 解決沖突的方法有兩大類：開放地址法和解決沖突的方法有兩大類：開放地址法和 鏈地址法。鏈地址法。

18、第32頁/共55頁 一、開放地址法一、開放地址法 開放地址法指當(dāng)發(fā)生沖突時，使用某種方開放地址法指當(dāng)發(fā)生沖突時，使用某種方 法在沖突位置前后尋找可存放記錄的空單元。法在沖突位置前后尋找可存放記錄的空單元。 我們利用下列公式來求得用來存放該記錄我們利用下列公式來求得用來存放該記錄 的下一個地址單元的地址：的下一個地址單元的地址： Hi=(H(k)+di)%m 其中，其中，H(k)關(guān)鍵字為關(guān)鍵字為 k的記錄所對應(yīng)的哈希地的記錄所對應(yīng)的哈希地 址（即發(fā)生沖突的地址）；址（即發(fā)生沖突的地址）； di為增量序列；為增量序列； 第33頁/共55頁 m為哈希表的長度。根據(jù)為哈希表的長度。根據(jù)di的取法，開放

19、地址的取法，開放地址 法又可以分為線性探測法、二次探測法和隨機法又可以分為線性探測法、二次探測法和隨機 探測法。下面就這幾種方法作一介紹。探測法。下面就這幾種方法作一介紹。 第34頁/共55頁 第35頁/共55頁 0的表頭單元依次探測），直到碰到一空閑地址的表頭單元依次探測），直到碰到一空閑地址 或探測完所有地址為止。或探測完所有地址為止。 假設(shè)哈希表大小為假設(shè)哈希表大小為Tm，哈希函數(shù)為哈希函數(shù)為H （key）那么，公式如下：那么，公式如下： H1=H（key） Hi+1= (Hi+1)%m 其中其中i=1，2. 第36頁/共55頁 例如：假設(shè)一組記錄關(guān)鍵字為例如：假設(shè)一組記錄關(guān)鍵字為4，1

20、7，29，38， 48，53，60，76，82，試對這組關(guān)鍵字構(gòu)造哈，試對這組關(guān)鍵字構(gòu)造哈 希表。希表。 取哈希表表長取哈希表表長m=11 ，用除留余數(shù)法構(gòu)造哈希函用除留余數(shù)法構(gòu)造哈希函 數(shù)數(shù)H(k)=k%11,用開放地址法處理沖突，處理過用開放地址法處理沖突，處理過 程如下：程如下： H(4)=4%11=4 H(17)=17%11=6 H(29)=29%11=7 H(38)=38%11=6 H(48)=48%11=4與與H(4)=4發(fā)生沖突，由線性探測發(fā)生沖突，由線性探測 第37頁/共55頁 法，探測下標(biāo)為法，探測下標(biāo)為5的單元，仍然沖突，直到下標(biāo)的單元，仍然沖突，直到下標(biāo) 為為8的單元為空

21、，此時將的單元為空，此時將48防入該單元。防入該單元。 H(53)=53%11=9 H(60)=60%11=5與與H(38) 發(fā)生沖突，由線性探測法依次推測，最后放在發(fā)生沖突，由線性探測法依次推測，最后放在 地址為地址為10 的單元中。的單元中。H(76)=76%11=10，此時此時 與與H(60)發(fā)生沖突，將其最后放在地址為發(fā)生沖突，將其最后放在地址為0的單的單 元中。元中。 H(82)=82%11=5， 第38頁/共55頁 此時與此時與H(38)發(fā)生沖突，將其最后放入地址為發(fā)生沖突，將其最后放入地址為1 的單元中。構(gòu)造結(jié)果如下圖所示：的單元中。構(gòu)造結(jié)果如下圖所示： 012345678910

22、 76824381748295360 線性探測法解決沖突示例線性探測法解決沖突示例 由該例可以看出，線性探測法處理沖突容易造由該例可以看出，線性探測法處理沖突容易造 成元素的聚集，從而大大增加了下一個空閑單成元素的聚集，從而大大增加了下一個空閑單 元的長度。元的長度。 第39頁/共55頁 2 2、二次探測法、二次探測法 此法可以較好的避免堆積現(xiàn)象，能較好的解決沖此法可以較好的避免堆積現(xiàn)象，能較好的解決沖 突。此時突。此時d di i的取值依次為的取值依次為d di i=1=12 2，-1-12 2，2 22 2，-2-22 2。 二次探測解決沖突的公式如下：二次探測解決沖突的公式如下： H H

23、1 1=H=H（keykey） H H2i 2i=(H =(H1 1+i+i2 2)% m)% m H H2i+1 2i+1 =(H =(H1 1 -i -i2 2)%m)%m 第40頁/共55頁 如上例子中，如上例子中，H H（4848）=48%11=4=48%11=4與關(guān)鍵字為與關(guān)鍵字為4 4的的 元素發(fā)生沖突時，由二次探測法可得元素發(fā)生沖突時，由二次探測法可得 H H1 1（4848）= =（4+14+1）%11=5%11=5， 仍然沖突又得仍然沖突又得H H2 2（4848）= =（4-14-1）%11=3%11=3，此時此時 該單元空閑。該單元空閑。 這與線性探測法相比，避免了沖突的

24、再次發(fā)生這與線性探測法相比，避免了沖突的再次發(fā)生 ，因為第二次，因為第二次d d2 2=-1,=-1,將所占單元向前分散開。將所占單元向前分散開。 由此依次可得：由此依次可得：H H（5353）=9=9 H H（6060）=5=5時，發(fā)生沖突，以二次探測法得：時，發(fā)生沖突，以二次探測法得： 第41頁/共55頁 H H1 1（6060）= =（5+15+1）%11=6 %11=6 H H2 2（6060）= =（5-15-1）%11=4 %11=4 H H3 3（6060）= =（5+25+22 2）%11=9%11=9 H H3 3（6060）= =（5-25-22 2）%11=1%11=1此

25、時解決沖突。此時解決沖突。 H H（7676）=10=10 H H（8282）=5=5時沖突發(fā)生，用二次探測法最后得時沖突發(fā)生，用二次探測法最后得 出出 H H8 8（8282）=0=0構(gòu)造結(jié)果如下圖所示：構(gòu)造結(jié)果如下圖所示： 012345678910 82604843817295376 二次探測法解決沖突示例二次探測法解決沖突示例 第42頁/共55頁 二次探測法的缺點是不能探測到哈希表上所有的二次探測法的缺點是不能探測到哈希表上所有的 單元，在實際應(yīng)用中，若探測一半仍未找到空閑單元，在實際應(yīng)用中，若探測一半仍未找到空閑 單元，說明該哈希表太滿，應(yīng)重新建立。單元，說明該哈希表太滿，應(yīng)重新建立。

26、 3、隨機探測法、隨機探測法 是指選擇一個隨機函數(shù)產(chǎn)生隨機序列，并建立和是指選擇一個隨機函數(shù)產(chǎn)生隨機序列，并建立和 查找時使用同一隨機生成序列。查找時使用同一隨機生成序列。 隨機探測解決沖突的公式是：隨機探測解決沖突的公式是： H1=H（key） Hi+1=(H1+R)% m 第43頁/共55頁 其中R=偽隨機數(shù)序列R1，R2， 二、鏈地址法二、鏈地址法 鏈地址法是指將所有的關(guān)鍵字為同義詞的鏈地址法是指將所有的關(guān)鍵字為同義詞的 記錄鏈接成一個線性表，而其鏈表頭存儲在相記錄鏈接成一個線性表，而其鏈表頭存儲在相 應(yīng)的哈希地址對應(yīng)的存儲單元中。如圖應(yīng)的哈希地址對應(yīng)的存儲單元中。如圖1 總之，哈希表的

27、建表過程中與查找過程所經(jīng)歷總之，哈希表的建表過程中與查找過程所經(jīng)歷 的沖突是一致的，只是在建表時把一個關(guān)鍵字的沖突是一致的，只是在建表時把一個關(guān)鍵字 通過哈希函數(shù)和解決沖突安排在一個空擋上，通過哈希函數(shù)和解決沖突安排在一個空擋上， 第44頁/共55頁 而查找時，是對一個給定的值的方法，使得而查找時，是對一個給定的值的方法，使得 某個位置通過哈希函數(shù)和找到解決沖突的方法某個位置通過哈希函數(shù)和找到解決沖突的方法 ，使得某個位置上的關(guān)鍵字等于給定的值。，使得某個位置上的關(guān)鍵字等于給定的值。 第45頁/共55頁 012345678910 4 48 38 60 82 17 29 53 76 圖圖 1 第

28、46頁/共55頁 哈希表舉例哈希表舉例 設(shè)有一組關(guān)鍵字（設(shè)有一組關(guān)鍵字（n=12） (19 , 01 , 23 , 14 , 55 , 20 , 84 , 27 , 68 , 11, 10, 77) 假設(shè)哈希表的空間大小為假設(shè)哈希表的空間大小為19（m=19），哈希函），哈希函 數(shù)數(shù)H(key)=key%13,若有沖突，試分別用線性探若有沖突，試分別用線性探 測、二次探測、隨機探測和鏈地址法解決沖測、二次探測、隨機探測和鏈地址法解決沖 突。突。 由哈希函數(shù)由哈希函數(shù) H(key)=key%13，可以計算出各個，可以計算出各個 第47頁/共55頁 關(guān)鍵字的哈希地址，若有沖突，按照用線性探關(guān)鍵字的

29、哈希地址，若有沖突，按照用線性探 測、二次探測來解決，得到下圖的測、二次探測來解決，得到下圖的 哈希表。哈希表。 01 14 55 27 68 19 208 4 23 11 10 77 0 1 2 3 4 5 6 7 8 9 10 11 12 13 比較次數(shù) 1 2 1 4 3 1 1 3 1 1 3 2 （a）線性探測）線性探測 第48頁/共55頁 27 01 14 55 68 84 19 2010 23 11 77 0 1 2 3 4 5 6 7 8 9 10 11 12 13 3 1 2 1 2 3 1 1 3 1 1 1 （b）二次探測）二次探測 統(tǒng)計平均查找長度統(tǒng)計平均查找長度ASL如下：如下： ASL線性探測 線性探測=1/12（ （1+2+1+4+3+1+1+3+1+1+3+2）=1.92 ASL二次探測 二