哈希表技術(shù)沈磊137651536

1、3.2 哈希表技術(shù)哈希表技術(shù)137651536沈磊3.2.1 Hash表的基本概念表的基本概念1. 直接查找直接查找表表 設(shè)表的長度為n。如果存在一個函數(shù)ii(k)，對于表中的任意一個元素的關(guān)鍵字k，滿足以下條件：(1)1in；(2)對于任意的元素關(guān)鍵字k1k2，恒存在i(k1)i(k2)。 則稱此表為直接查找表。其中函數(shù)ii(k)稱為關(guān)鍵字k的映象函數(shù)。(1)直接查找表的填入要將關(guān)鍵字為k的元素填入到直接查找表，只需做以下兩步：1)計算關(guān)鍵字k的映象函數(shù)ii(k)；2)將關(guān)鍵字k及有關(guān)元素信息填入到表的第i項。(2) 直接查找表的取出要在直接查找表中取出關(guān)鍵字k的元素，也只需做以下兩步：1)

2、計算關(guān)鍵字k的映象函數(shù)ii(k)；2)檢查表中第i項：若第i項為空，則說明表中沒有關(guān)鍵字為k的元素；否則取出第i項中的元素即可。2. Hash表表例 將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n12的表中。映象函數(shù)為iINT(k/3)1。設(shè)表的長度為n。如果存在一個函數(shù)ii(k)，對于表中的任意一個元素的關(guān)鍵字k，滿足1in，則稱此表為Hash表。 其 中 函 數(shù) i i ( k ) 稱 為 關(guān) 鍵 字 k 的 H a s h 碼 。(1)構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次 數(shù) 。 即 H a s h 碼 的 均 勻 性

3、 要 比 較 好 。(2)當(dāng)表中元素發(fā)生沖突時，要進(jìn)行適當(dāng)?shù)奶幚怼?.2.2 幾種常用的幾種常用的Hash表表1. 線性線性Hash表表1)線性Hash表的填入將關(guān)鍵字k及有關(guān)信息填入線性Hash表的步驟如下：1)計算關(guān)鍵字k的Hash碼ii(k)。2)檢查表中第i項的內(nèi)容：若第i項為空，則將關(guān)鍵字k及有關(guān)信息填入該項；若第i項不空，則令imod(i1，n)，轉(zhuǎn)2)繼續(xù)檢查。只要Hash表尚未填滿，最終總可以找到一個空項，將關(guān)鍵字k及有關(guān)信息填入到Hash表中。2) 線性Hash表的取出要在線性Hash表中取出關(guān)鍵字k的元素，其步驟如下：1)計算關(guān)鍵字k的Hash碼ii(k)。2)檢查表中第i

4、項的內(nèi)容：若第i項登記著關(guān)鍵字k，則取出該項元素即可；若第i項為空，則表示在Hash表中沒有該關(guān)鍵字的信息；若 第 i 項 不 空 ， 且 登 記 的 不 是 關(guān) 鍵 字 k ， 則 令 i m o d ( i 1 ， n ) ， 轉(zhuǎn) 而 繼 續(xù) 檢 查 。 例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n12的線性Hash表中。設(shè) H a s h 碼 為 i I N T ( k / 3 ) 1 。缺點：1)在線性Hash表填入的過程中，當(dāng)發(fā)生沖突時，首先考慮 的是下一項，因此，當(dāng)當(dāng)HashHash碼的沖突較多時，在線性碼的沖突較多時，在

5、線性 HashHash表中會存在表中會存在“堆聚堆聚”現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記 在一起，從而會降低查找效率在一起，從而會降低查找效率。2)在線性Hash表的填入過程中，處理沖突時會帶來新的處理沖突時會帶來新的沖突沖突。2. 隨機隨機Hash表表（當(dāng)哈希表的長度設(shè)置成（當(dāng)哈希表的長度設(shè)置成 ）1) 隨機Hash表的填入將關(guān)鍵字k及有關(guān)信息填入隨機Hash表的步驟如下：1)計算關(guān)鍵字k的Hash碼i0i(k)。且令ii0。2)偽隨機數(shù)序列初始化，令j1（即將取隨機數(shù)指針指向偽 隨機數(shù)序列中的第1個隨機數(shù)）。3)檢查表中第i項的內(nèi)容：若第i項為空，則將關(guān)鍵字k及有關(guān)信

6、息填入該項；若第i項不空，則令imod(i0RN(j)，n)，并令jj1 （即將取隨機數(shù)指針指向下一個隨機數(shù)），轉(zhuǎn)3)繼續(xù)檢查。其中RN(j)表示偽隨機數(shù)序列RN中的第j個隨機數(shù)。偽 隨 機 數(shù) 序 列 R N 按 下 列 方 法 產(chǎn) 生 ： R1 FOR j1 TO n DO Rmod(5*R，4n) RN(j)INT(R/4) 2) 隨機Hash表的取出要在隨機Hash表中取出關(guān)鍵字k的元素，其步驟如下：1)計算關(guān)鍵字k的Hash碼i0i(k)。且令ii0。2)偽隨機數(shù)序列初始化，令j1（即將取隨機數(shù)指針指向偽 隨機數(shù)序列中的第1個隨機數(shù)）。3)檢查表中第i項的內(nèi)容：若第i項登記著關(guān)鍵字k

7、，則取出該項元素即可；若第i項空，則表示在Hash表中沒有該關(guān)鍵字信息；若 第 i 項 不 空 ， 且 登 記 的 不 是 關(guān) 鍵 字 k ， 則 令imod(i0RN(j)，n)，并令jj1（即將取隨機數(shù)指 針指向下一個隨機數(shù)），轉(zhuǎn)3)繼續(xù)檢查。其中RN(j)表示偽隨機數(shù)序列RN中的第j個隨機數(shù)。3. 溢出溢出Hash表表溢出溢出Hash表包括表包括Hash表和溢出表兩部分。表和溢出表兩部分。在在Hash表的填入過程中，將沖突的元素順序填入溢出表表的填入過程中，將沖突的元素順序填入溢出表，而當(dāng)查找過程中發(fā)現(xiàn)沖突時，就在溢出表中進(jìn)行順序查，而當(dāng)查找過程中發(fā)現(xiàn)沖突時，就在溢出表中進(jìn)行順序查找。找

8、。溢出表是一個順序查找表。溢出表是一個順序查找表。1) 溢出Hash表的填入將關(guān)鍵字k及有關(guān)信息填入溢出Hash表的步驟如下：1)計算關(guān)鍵字k的Hash碼ii(k)。2)檢查表中第i項的內(nèi)容：若第i項為空，則將關(guān)鍵字k及有關(guān)信息填入該項；若第i項不空，則將關(guān)鍵字k及有關(guān)信息依次填入 溢出表中的自由項。2) 溢出Hash表的取出要在溢出Hash表中取出關(guān)鍵字k的元素，其步驟如下：1)計算關(guān)鍵字k的Hash碼ii(k)。2)檢查表中第i項的內(nèi)容：若第i項登記著關(guān)鍵字k，則取出該項元素即可；若第i項為空，則表示在Hash表中沒有該關(guān)鍵字信息；若第i項不空，且登記的不是關(guān)鍵字k，則轉(zhuǎn)入在 溢出表中進(jìn)行

9、順序查找。例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n12的溢出Hash表中。設(shè)Hash碼為iINT(k/3)1。4. 拉鏈拉鏈Hash表表拉鏈拉鏈Hash表又分為外鏈表又分為外鏈Hash表與內(nèi)鏈表與內(nèi)鏈Hash表。表。 這里主要講外鏈這里主要講外鏈Hash 表。表。1) 外鏈Hash表的填入將關(guān)鍵字k及有關(guān)信息填入外鏈Hash表的步驟如下：1)計算關(guān)鍵字k的Hash碼ii(k)。2)取得一個新結(jié)點p，并將關(guān)鍵字k及有關(guān)信息填入結(jié)點p。3)將結(jié)點p鏈入以H(i)為頭指針的鏈表的鏈頭。例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n12的外鏈Hash表中。設(shè)Hash碼為iINT