第二十六講哈希表及其查找-文庫(kù)吧資料
2024-09-12 14:57本頁(yè)面
【正文】 址方法很多，下面介紹三種： 1. 線性探測(cè)法 Hi=(Hash(key)+di) mod m ( 1≤ i m ) 其中： Hash(key)為哈希函數(shù) m 為哈希表長(zhǎng)度 di 為增量序列 1， 2，??， m1，且 di=i 【例 】關(guān)鍵碼集為 {47， 7， 29， 11， 16， 92， 22， 8， 3}，哈希表表長(zhǎng)為 11， Hash(key)=key mod 11，用線性探測(cè)法處理沖突，建表如下： 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ù)得到的沒(méi)有沖突的哈希地址而直接存入的 ； Hash(29)=7，哈希地址上沖突，需尋找下一個(gè)空的哈希地址： 由 H1=(Hash(29)+1) mod 11=8，哈希地址 8為空，將 29存入。 3 4 7 3 9 1 9 ───────────── ① ② ③ ④ ⑤ ⑥ ⑦ 四 . 平方取中法 對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。 第七 章 查找 【例 】有一組關(guān)鍵碼如下： 3 4 7 0 5 2 4 第 2 位均是“ 3 和 4”，第 3 位也只有 3 4 9 1 4 8 7 “ 9”，因此，這幾位不能用，余 3 4 8 2 6 9 6 下四位分布較均勻，可作為哈希地址選用。 數(shù)字分析法根據(jù) r 種不同的符號(hào)，在各位上的分布情況，選取某幾位，組合成哈希地址。 【例 】若關(guān)鍵碼是 4 位十進(jìn)制數(shù)，則每位上可能有十個(gè)不同的數(shù)符 0～ 9，所以 r=10。 p 一般選取質(zhì)數(shù)，也可以是不包含小于 20質(zhì)因子 的合數(shù)。 【例 】關(guān)鍵碼集合為 {100， 300， 500， 700， 800， 900}，選取哈希函數(shù)為 Hash(key)=key/100，則存放如下： 0 1 2 3 4 5 6 7 8 9 100 300 500 700 800 900 二 . 除留余數(shù)法 Hash(key)=key mod p (p 是一個(gè)整數(shù) ) 即取關(guān)鍵碼除以 p的余數(shù)作為哈希地址。 構(gòu)造 哈希函數(shù) 的常
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1