第三章 3.1 哈希表

第三章查找與排序技術(shù)什么是哈希表設(shè)表的長(zhǎng)度為n，如果存在一個(gè)函數(shù)i=i(k),對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足則稱此表為Hash表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的Hash碼。Hash表技術(shù)的關(guān)鍵是要處理好表中元素的沖突問(wèn)題，它主要包括以下兩方面的工作：①構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次數(shù)，即Hash碼的均勻性要比較好。②當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚?。Hash碼的構(gòu)造Hash表技術(shù)的主要目標(biāo)是提高查找效率，即縮短查表的時(shí)間。⑴截?cái)喾āＪ侵高x取與關(guān)鍵字對(duì)應(yīng)的數(shù)字串中的一段（一般選取低位數(shù)）作為該關(guān)鍵字的Hash碼。⑵分段疊加法。將關(guān)鍵字的編碼串分割成若干段，然后把他們疊加后再進(jìn)行截段。⑶除法。將關(guān)鍵字的編碼除以表的長(zhǎng)度，最后所得的余數(shù)作為Hash碼，即取Hash碼為i=mod(k,n)(當(dāng)mod(k,n)0時(shí)，取i=n)本方法構(gòu)造的Hash碼，其均勻性比較好，但是以一次除法為代價(jià)，在除法較快的機(jī)器上可以采用。⑷乘法。將關(guān)鍵字編碼與一個(gè)常數(shù)相乘后，再除以表長(zhǎng)度n，取其余數(shù)作為Hash碼線性Hash表是一種最簡(jiǎn)單的Hash表。⑴設(shè)線性表的長(zhǎng)度為n，則將關(guān)鍵字k及有關(guān)信息填入線性Hash表的步驟如下：①計(jì)算關(guān)鍵字k的Hash碼i=i(k).②檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則令i=mod(i+1，n)，轉(zhuǎn)②繼續(xù)檢查。1.線性hash表⑵線性Hash表的取出①計(jì)算關(guān)鍵字k的Hash碼i=i(k).②檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒(méi)有該關(guān)鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令i=mod(i+1,n)，轉(zhuǎn)②繼續(xù)檢查。線性表的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)單缺點(diǎn)：①在線性Hash表填入的過(guò)程中，當(dāng)發(fā)生沖突時(shí)，首先考慮的是下一項(xiàng)，因此，當(dāng)Hash碼的沖突較多時(shí)，在線性Hash表中會(huì)存在“堆聚”現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記在一起，從而會(huì)降低查找效率。②在線性Hash表的填入過(guò)程中，處理沖突時(shí)會(huì)帶來(lái)新的沖突，即線性Hash表的填入方法是不顧后效的。2.隨機(jī)Hash表當(dāng)Hash表的長(zhǎng)度n設(shè)計(jì)成n=2m時(shí),還可以定義另外一種Hash表——隨機(jī)Hash表。隨機(jī)Hash表與線性Hash表的不同之處在于：一旦發(fā)生元素沖突時(shí)，表項(xiàng)序號(hào)i的改變不是采用加1取模的方法，而是用某種偽隨機(jī)數(shù)來(lái)改變。⑴隨機(jī)Hash表的填入：①計(jì)算關(guān)鍵字k的Hash碼i0=i(k)，且令i=i0.②偽隨機(jī)數(shù)序列初始化，令j=1（將隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列的第1個(gè)隨機(jī)數(shù)）③檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則令i=mod(i0+RN(j)，n)，并令j=j+1（將隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)③繼續(xù)檢查。⑵隨機(jī)Hash表的取出：①計(jì)算關(guān)鍵字k的Hash碼i0=i(k)，且令i=i0②偽隨機(jī)數(shù)序列初始化，令j=1（將隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列的第1個(gè)隨機(jī)數(shù)）。③檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒(méi)有該關(guān)鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令i=mod(i0+RN(j)，n)，并令j=j+1（將隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)③繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)。3.溢出Hash表線性Hash表與隨機(jī)Hash表均存在兩個(gè)致命的缺點(diǎn)：一是在Hash表填入過(guò)程中不顧后效，從而在填入過(guò)程中其沖突的機(jī)會(huì)在不斷增多；二是當(dāng)Hash表填滿時(shí)，不能正常地進(jìn)行查找。如果將沖突的元素安排在另外的空間內(nèi)，而不占用Hash表本身的空間，則不會(huì)產(chǎn)生新的沖突，這就是溢出Hash表。

溢出Hash表包括Hash表和溢出表兩部分。在Hash表的填入過(guò)程中，將沖突的元素順序填入溢出表，而當(dāng)查找過(guò)程中發(fā)現(xiàn)沖突時(shí)，就在溢出表中進(jìn)行順序查找。溢出表的填入過(guò)程：①計(jì)算關(guān)鍵字k的Hash碼i=i(k).②檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字K及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則將關(guān)鍵字k及有關(guān)信息依次填入溢出表中的自由項(xiàng)。⑵溢出Hash表的取出：①計(jì)算關(guān)鍵字k的Hash碼i=i(k).②檢查表中第i項(xiàng)內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒(méi)有該關(guān)鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則轉(zhuǎn)入在溢出表中進(jìn)行順序查找。4.拉鏈Hash表-1

拉鏈Hash表分為外鏈Hash表與內(nèi)鏈Hash表。我們只討論外鏈Hash表。外鏈Hash表由Hash表及表外結(jié)點(diǎn)所組成。在Hash表中登記的并不是關(guān)鍵字k及有關(guān)信息，而只是登記指針。⑴外鏈Hash表的填入：①計(jì)算關(guān)鍵字k的Hash碼i=i(k).②取得一個(gè)新結(jié)點(diǎn)p，并將關(guān)鍵字k及有關(guān)信息填入結(jié)點(diǎn)p。③將結(jié)點(diǎn)p鏈入以H(i)為頭指針的鏈表的鏈頭。4.拉鏈Hash表-2⑴外鏈Hash表