第三章 31 哈希表

1、什么是哈希表什么是哈希表設(shè)表的長(zhǎng)度為設(shè)表的長(zhǎng)度為n n，如果存在一個(gè)函數(shù)，如果存在一個(gè)函數(shù)i= i(k),i= i(k),對(duì)于對(duì)于表中的任意一個(gè)元素的關(guān)鍵字表中的任意一個(gè)元素的關(guān)鍵字k k，滿(mǎn)足，滿(mǎn)足 則稱(chēng)此表為則稱(chēng)此表為HashHash表。其中函數(shù)表。其中函數(shù)i= i(k)i= i(k)稱(chēng)為關(guān)鍵字稱(chēng)為關(guān)鍵字k k的的HashHash碼。碼。ni 1Hash表技術(shù)的關(guān)鍵是要處理好表中元素的沖突問(wèn)題，表技術(shù)的關(guān)鍵是要處理好表中元素的沖突問(wèn)題，它主要包括以下兩方面的工作：它主要包括以下兩方面的工作：構(gòu)造合適的構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突碼，以便盡量減少表中元素沖突的次數(shù)，即的次數(shù)

2、，即Hash碼的均勻性要比較好。碼的均勻性要比較好。當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚?。?dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚?。Hash碼的構(gòu)造碼的構(gòu)造 Hash表技術(shù)的主要目標(biāo)是提高查找效率，即縮表技術(shù)的主要目標(biāo)是提高查找效率，即縮短查表的時(shí)間。短查表的時(shí)間。截?cái)喾?。是指選取與關(guān)鍵字對(duì)應(yīng)的數(shù)字串中的截?cái)喾āＪ侵高x取與關(guān)鍵字對(duì)應(yīng)的數(shù)字串中的一段（一般選取低位數(shù)）作為該關(guān)鍵字的一段（一般選取低位數(shù)）作為該關(guān)鍵字的Hash碼。碼。分段疊加法。將關(guān)鍵字的編碼串分割成若干段，分段疊加法。將關(guān)鍵字的編碼串分割成若干段，然后把他們疊加后再進(jìn)行截段。然后把他們疊加后再進(jìn)行截段。除法。將關(guān)鍵字的編碼除以表

3、的長(zhǎng)度，最后所除法。將關(guān)鍵字的編碼除以表的長(zhǎng)度，最后所得的余數(shù)作為得的余數(shù)作為Hash碼，即取碼，即取Hash碼為碼為i=mod(k,n)(當(dāng)當(dāng)mod(k,n)0時(shí)，取時(shí)，取i=n)本方法構(gòu)造的本方法構(gòu)造的Hash碼，其均勻性比較好，但是以碼，其均勻性比較好，但是以一次除法為代價(jià)，在除法較快的機(jī)器上可以采一次除法為代價(jià)，在除法較快的機(jī)器上可以采用。用。乘法。將關(guān)鍵字編碼與一個(gè)常數(shù)乘法。將關(guān)鍵字編碼與一個(gè)常數(shù) 相乘后，相乘后，再除以表長(zhǎng)度再除以表長(zhǎng)度n，取其余數(shù)作為，取其余數(shù)作為Hash碼碼線(xiàn)性線(xiàn)性Hash表是一種最簡(jiǎn)單的表是一種最簡(jiǎn)單的Hash表。表。設(shè)線(xiàn)性表的長(zhǎng)度為設(shè)線(xiàn)性表的長(zhǎng)度為n，則將關(guān)

4、鍵字，則將關(guān)鍵字k及有關(guān)信息及有關(guān)信息填入線(xiàn)性填入線(xiàn)性Hash表的步驟如下：表的步驟如下：計(jì)算關(guān)鍵字計(jì)算關(guān)鍵字k的的Hash碼碼i=i(k).檢查表中第檢查表中第i項(xiàng)的內(nèi)容：項(xiàng)的內(nèi)容：若第若第i項(xiàng)為空，則將關(guān)鍵字項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；及有關(guān)信息填入該項(xiàng)；若第若第i項(xiàng)不空，則令項(xiàng)不空，則令i=mod(i+1，n)，轉(zhuǎn)，轉(zhuǎn)繼續(xù)檢查。繼續(xù)檢查。1.線(xiàn)性線(xiàn)性hash表表線(xiàn)性線(xiàn)性Hash表的取出表的取出計(jì)算關(guān)鍵字計(jì)算關(guān)鍵字k的的Hash碼碼i=i(k).檢查表中第檢查表中第i項(xiàng)的內(nèi)容：項(xiàng)的內(nèi)容：若第若第i項(xiàng)登記著關(guān)鍵字項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；，則取出該項(xiàng)元素即可；若第若第

5、i項(xiàng)為空，則表示在項(xiàng)為空，則表示在Hash表中沒(méi)有該關(guān)鍵字的信表中沒(méi)有該關(guān)鍵字的信息；息；若第若第i項(xiàng)不空，且登記的不是關(guān)鍵字項(xiàng)不空，且登記的不是關(guān)鍵字k，則令，則令i=mod(i+1,n)，轉(zhuǎn)，轉(zhuǎn)繼續(xù)檢查。繼續(xù)檢查。線(xiàn)性表的優(yōu)缺點(diǎn)：線(xiàn)性表的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)單優(yōu)點(diǎn)：簡(jiǎn)單缺點(diǎn)：缺點(diǎn)：在線(xiàn)性在線(xiàn)性Hash表填入的過(guò)程中，當(dāng)發(fā)生沖突表填入的過(guò)程中，當(dāng)發(fā)生沖突時(shí)，首先考慮的是下一項(xiàng)，因此，當(dāng)時(shí)，首先考慮的是下一項(xiàng)，因此，當(dāng)Hash碼的沖碼的沖突較多時(shí)，在線(xiàn)性突較多時(shí)，在線(xiàn)性Hash表中會(huì)存在表中會(huì)存在“堆聚堆聚”現(xiàn)象，現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記在一起，從而會(huì)降低查即許多關(guān)鍵字被連續(xù)登記在一起，從而會(huì)

6、降低查找效率。找效率。在線(xiàn)性在線(xiàn)性Hash表的填入過(guò)程中，處理沖突時(shí)會(huì)帶來(lái)表的填入過(guò)程中，處理沖突時(shí)會(huì)帶來(lái)新的沖突，即線(xiàn)性新的沖突，即線(xiàn)性Hash表的填入方法是表的填入方法是不顧后效不顧后效的的。2.隨機(jī)隨機(jī)Hash表表 當(dāng)當(dāng)Hash表的長(zhǎng)度表的長(zhǎng)度n設(shè)計(jì)成設(shè)計(jì)成n=2m時(shí)時(shí),還可以定還可以定義另外一種義另外一種Hash表表隨機(jī)隨機(jī)Hash表。隨機(jī)表。隨機(jī)Hash表與線(xiàn)性表與線(xiàn)性Hash表的不同之處在于：一表的不同之處在于：一旦發(fā)生元素沖突時(shí)，表項(xiàng)序號(hào)旦發(fā)生元素沖突時(shí)，表項(xiàng)序號(hào)i的改變不是的改變不是采用加采用加1取模的方法，而是用某種偽隨機(jī)數(shù)取模的方法，而是用某種偽隨機(jī)數(shù)來(lái)改變。來(lái)改變。隨機(jī)隨

7、機(jī)Hash表的填入：表的填入：計(jì)算關(guān)鍵字計(jì)算關(guān)鍵字k的的Hash碼碼i0=i(k)，且令，且令i=i0.偽隨機(jī)數(shù)序列初始化，令偽隨機(jī)數(shù)序列初始化，令j=1（將隨機(jī)數(shù)指針指向（將隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列的第偽隨機(jī)數(shù)序列的第1個(gè)隨機(jī)數(shù)）個(gè)隨機(jī)數(shù)）檢查表中第檢查表中第i項(xiàng)的內(nèi)容：項(xiàng)的內(nèi)容：若第若第i項(xiàng)為空，則將關(guān)鍵字項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；及有關(guān)信息填入該項(xiàng)；若第若第i項(xiàng)不空，則令項(xiàng)不空，則令i=mod(i0+RN(j)，n)，并令，并令j=j+1（將隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)（將隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)繼續(xù)繼續(xù)檢查。檢查。隨機(jī)隨機(jī)Hash表的取出：表的取出：計(jì)算關(guān)鍵

8、字計(jì)算關(guān)鍵字k的的Hash碼碼i0=i(k)，且令，且令i=i0偽隨機(jī)數(shù)序列初始化，令偽隨機(jī)數(shù)序列初始化，令j=1（將隨機(jī)數(shù)指針指向偽隨機(jī)（將隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列的第數(shù)序列的第1個(gè)隨機(jī)數(shù)）。個(gè)隨機(jī)數(shù)）。檢查表中第檢查表中第i項(xiàng)的內(nèi)容：項(xiàng)的內(nèi)容：若第若第i項(xiàng)登記著關(guān)鍵字項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；，則取出該項(xiàng)元素即可；若第若第i項(xiàng)為空，則表示在項(xiàng)為空，則表示在Hash表中沒(méi)有該關(guān)鍵字的信息；表中沒(méi)有該關(guān)鍵字的信息；若第若第i項(xiàng)不空，且登記的不是關(guān)鍵字項(xiàng)不空，且登記的不是關(guān)鍵字k，則令，則令i=mod(i0+RN(j)，n)，并令，并令j=j+1（將隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)

9、（將隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)繼續(xù)檢查。其中繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列表示偽隨機(jī)數(shù)序列RN中的第中的第j個(gè)個(gè)隨機(jī)數(shù)。隨機(jī)數(shù)。3.溢出溢出Hash表表 線(xiàn)性線(xiàn)性Hash表與隨機(jī)表與隨機(jī)Hash表均存在兩個(gè)致命的缺表均存在兩個(gè)致命的缺點(diǎn)：一是在點(diǎn)：一是在Hash表填入過(guò)程中不顧后效，從而表填入過(guò)程中不顧后效，從而在填入過(guò)程中其沖突的機(jī)會(huì)在不斷增多；二是在填入過(guò)程中其沖突的機(jī)會(huì)在不斷增多；二是當(dāng)當(dāng)Hash表填滿(mǎn)時(shí)，不能正常地進(jìn)行查找。如果表填滿(mǎn)時(shí)，不能正常地進(jìn)行查找。如果將沖突的元素安排在另外的空間內(nèi)，而不占用將沖突的元素安排在另外的空間內(nèi)，而不占用Hash表本身的空間，則不會(huì)產(chǎn)

10、生新的沖突，這表本身的空間，則不會(huì)產(chǎn)生新的沖突，這就是溢出就是溢出Hash表。表。 溢出溢出Hash表包括表包括Hash表表和和溢出表溢出表兩部分。在兩部分。在Hash表的填入過(guò)程中，將沖突的元素順序填入溢表的填入過(guò)程中，將沖突的元素順序填入溢出表，而當(dāng)查找過(guò)程中發(fā)現(xiàn)沖突時(shí)，就在溢出表出表，而當(dāng)查找過(guò)程中發(fā)現(xiàn)沖突時(shí)，就在溢出表中進(jìn)行順序查找。中進(jìn)行順序查找。溢出表的填入過(guò)程：溢出表的填入過(guò)程：計(jì)算關(guān)鍵字計(jì)算關(guān)鍵字k的的Hash碼碼i=i(k).檢查表中第檢查表中第i項(xiàng)的內(nèi)容：項(xiàng)的內(nèi)容：若第若第i項(xiàng)為空，則將關(guān)鍵字項(xiàng)為空，則將關(guān)鍵字K及有關(guān)信息填入該項(xiàng)；及有關(guān)信息填入該項(xiàng)；若第若第i項(xiàng)不空，則將

11、關(guān)鍵字項(xiàng)不空，則將關(guān)鍵字k及有關(guān)信息依次填入溢及有關(guān)信息依次填入溢出表中的自由項(xiàng)出表中的自由項(xiàng)。溢出溢出Hash表的取出：表的取出：計(jì)算關(guān)鍵字計(jì)算關(guān)鍵字k的的Hash碼碼i=i(k).檢查表中第檢查表中第i項(xiàng)內(nèi)容：項(xiàng)內(nèi)容：若第若第i項(xiàng)登記著關(guān)鍵字項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；，則取出該項(xiàng)元素即可；若第若第i項(xiàng)為空，則表示在項(xiàng)為空，則表示在Hash表中沒(méi)有該關(guān)鍵字的信表中沒(méi)有該關(guān)鍵字的信息；息；若第若第i項(xiàng)不空，且登記的不是關(guān)鍵字項(xiàng)不空，且登記的不是關(guān)鍵字k，則轉(zhuǎn)入在溢，則轉(zhuǎn)入在溢出表中進(jìn)行順序查找。出表中進(jìn)行順序查找。4.拉鏈拉鏈Hash表表-1 拉鏈拉鏈Hash表分為外鏈表分為外鏈Hash表與內(nèi)鏈表與內(nèi)鏈Hash表。我表。我們只討論外鏈們只討論外鏈Hash表。表。 外鏈外鏈Hash表由表由Hash表及表外結(jié)點(diǎn)所組成。在表及表外結(jié)點(diǎn)所組成。在Hash表中登記的并不是關(guān)鍵字表中登記的并不是關(guān)鍵字k及有關(guān)信息，而及有關(guān)信息，而只是登記指針。只是登記指針。外鏈外鏈Hash表的填入：表的填入：計(jì)算關(guān)鍵字計(jì)算關(guān)鍵字k的的Hash碼碼i=i(k).取得一個(gè)新結(jié)點(diǎn)取得一個(gè)新結(jié)點(diǎn)p，并將關(guān)鍵字，并將關(guān)鍵字k及有關(guān)信息填入及有關(guān)信息填入結(jié)點(diǎn)結(jié)點(diǎn)p。將結(jié)點(diǎn)將結(jié)點(diǎn)p鏈入以鏈入以H(i)為頭指針的鏈表的鏈頭。為頭指針的鏈表的鏈頭。4.拉鏈拉鏈Hash表表-2外鏈外鏈HashH