[理學(xué)]第二十五講哈希表查找(編輯修改稿)
2024-11-12 21:28 本頁面
【文章內(nèi)容簡介】 ，所選取的位數(shù)與表長有關(guān)。例如 哈希表長 1000，如下圖所示： 分析： 平方取中法適用于關(guān)鍵字中每一位的取值 都不夠分散或分散的位數(shù)小于哈希地址所需要的 位數(shù)的情況。 關(guān)鍵字 平方數(shù) 哈希地址 1324 2541 1436 ……. 1752976 6456681 2062096 …….. 529 566 620 ……… 折疊法 當(dāng)關(guān)鍵字的位數(shù)很多，采用平方取中法計 算太復(fù)雜時，采用折疊法，即將關(guān)鍵字分成 位數(shù)相同的幾段（最后一段位數(shù)可以少 些）。每一段的長度取決于哈希地址的位 數(shù)，然后取這幾段的疊加和（舍去最高進(jìn) 位）作為哈希地址。 折疊法中進(jìn)行疊加有兩種方法：一種為移位疊 加，指分割后的每一段最低位對齊相加，最高 位舍去；一種為間界疊加，指從一端向另一端 沿分割界來回折疊后對齊相加。 例如：哈希表長為 1000時，關(guān)鍵字 k=230203700904121,則 15位數(shù)字以每段 3位分成 5 段，每段數(shù)字為 230， 203， 700， 904， 121。 這兩種疊加的過程如下圖所示： 移位疊加 間界疊加 230 203 700 904 +） 121 （ 2） 158 230 302 700 409 +） 121 （ 1） 762 其中高位舍去后，對應(yīng)的哈希地址為 158和 762。 折疊法適用于關(guān)鍵字位數(shù)多，而對應(yīng)的哈希地 址的位數(shù)要求較少的情況。 除留取余法 指取關(guān)鍵字 k除以最接近表長的素數(shù) m所 得的余數(shù)為哈希地址，對應(yīng)的哈希函數(shù)為： H（ k） =k%m 這是一種最簡單、也最常用的構(gòu)造哈希函 數(shù)的方法，它不僅可以對關(guān)鍵字直接取模 （ MOD） 也可在折疊、平方取中等運(yùn)算之后 取模。 一般地， m是哈希表的長度，它的取值在～ 。 注意：在使用此種方法時，對 m的選擇很重要。 若選擇不好，容易產(chǎn)生同義詞，從而產(chǎn)生沖突 。 隨機(jī)數(shù)法 選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù) 值為它的哈希地址，即 H(key)=random(key) 其中 random為隨機(jī)函數(shù)。通常，當(dāng)關(guān)鍵字長 度不等的時采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。 以上介紹了建立哈希函數(shù)產(chǎn)生哈希地址的方 法，在實際應(yīng)用中，應(yīng)根據(jù)關(guān)鍵字的特點，確定 適當(dāng)?shù)姆椒?，還可以根據(jù)具體情況構(gòu)造出滿足需 要的隨機(jī)性能好的哈希函數(shù)。 處理沖突的方法 在前面已經(jīng)講過，均勻的哈希函數(shù)可以 減少沖突，但不能夠避免，因而解決沖突的 問題尤為重要。 假設(shè)哈希表的地址范圍為 0….. m1,沖突是 指由關(guān)鍵字得到的哈希地址為 j（ 0=j=m1） 的位置上已有關(guān)鍵字記錄，則“處理沖突”就 是為該關(guān)鍵字的記錄找到另一個空的哈希地址。 在處理沖突的過程中可能得到一個地址序列 Hi i=1,2,3,……,k(H i屬于 [0， m1]),即在處理哈希地 址的沖突時，若得到的另一個哈希地址 H1仍然發(fā) 生沖突，則在求下一個地址 H2， 若仍然沖突，在 求 H3。 依次類推，直至不發(fā)生沖突為止。 解決沖突的方法有兩大類：開放地址法和 鏈地址法。 一、開放地址法 開放地址法指當(dāng)發(fā)生沖突時，使用某種方 法在沖突位置前后尋找可存放記錄的空單元。 我們利用下列公式來求得用來存放該記錄的下一個地址單元的地址： Hi=(H(k)+di)%m 其中， H(k)關(guān)鍵字為 k的記錄所對應(yīng)的哈希地 址（即發(fā)生沖突的地址）； di為增量序列； m為哈希表的長度。根據(jù) di的取法，開放地址 法又可以
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1