第二十六講哈希表及其查找(編輯修改稿)
2024-10-10 14:57 本頁面
【文章內(nèi)容簡介】 所謂開放定 址法，即是由關(guān)鍵碼得到的哈希地址一旦產(chǎn)生了沖突，也就是說，該地址已經(jīng)存放了數(shù)據(jù)元素，就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 找空哈希地址方法很多，下面介紹三種： 1. 線性探測法 Hi=(Hash(key)+di) mod m ( 1≤ i m ) 其中： Hash(key)為哈希函數(shù) m 為哈希表長度 di 為增量序列 1， 2，??， m1，且 di=i 【例 】關(guān)鍵碼集為 {47， 7， 29， 11， 16， 92， 22， 8， 3}，哈希表表長為 11， Hash(key)=key mod 11，用線性探測法處理沖突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 △ ▲ △ △ 4 1 1 92 均是由哈希函數(shù)得到的沒有沖突的哈希地址而直接存入的 ； Hash(29)=7，哈希地址上沖突，需尋找下一個(gè)空的哈希地址： 由 H1=(Hash(29)+1) mod 11=8，哈希地址 8為空，將 29存入。另外， 2 8 同樣在哈希地址上有沖突，也是由 H1找到空的哈希地址的； 而 Hash(3)=3，哈希地址上沖突，由 H1=(Hash(3)+1) mod 11=4 仍然沖突； H2=(Hash(3)+2) mod 11=5 仍然沖突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入。 線性探測法可能使第 i個(gè)哈希地址的同義詞存入第 i+1個(gè)哈希地址，這樣本應(yīng)存入第 i+1 第七 章 查找 個(gè)哈希地址的元素變成了第 i+2 個(gè)哈希地址的同義詞，??，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。為此，可采用二次探測法，或雙哈希函數(shù)探測法，以改善“堆積”問題。 2. 二次探測法 Hi=(Hash(key)177。 di) mod m 其中： Hash(key)為哈希函數(shù) m 為哈希表長度， m 要求是某個(gè) 4k+3 的質(zhì)數(shù) (k 是整數(shù) ) di 為增量序列 12， 12， 22， 22，??， q2， q2 且 q≤ (m1) 仍以上例用二次探測法處理沖突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1