第二十六講哈希表及其查找(完整版)
【正文】 的合數。 3 4 7 3 9 1 9 ───────────── ① ② ③ ④ ⑤ ⑥ ⑦ 四 . 平方取中法 對關鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。 3. 雙哈希函數探測法 Hi=(Hash(key)+i*ReHash(key)) mod m (i=1， 2，??， m1) 其中： Hash(key)， ReHash(key)是兩個哈希函數， m 為哈希表長度 雙哈希 函數探測法，先用第一個函數 Hash(key)對關鍵碼計算哈希地址，一旦產生地址沖突，再用第二個函數 ReHash(key)確定移動的步長因子，最后，通過步長因子序列由探測函數尋找空的哈希地址。所以，對哈希表查找效率的量度，依然用平均查找長度來衡量。以下給出幾種不同處理沖突方法的平均查找長度： 第七 章 查找 哈希方法存取速度快，也較節(jié)省空間，靜態(tài)查找、動態(tài)查找均適用，但由于存取是隨機的，因此，不便于順序查找。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。 【例 】關鍵碼序列為 47,7,29,11,16, １ ─ 2 ^ ^ 0 1 2 3 4 5 6 7 8 9 10 22 3 89 ^ 11 ^ 47 ^ 37 92 ^ 16 ^ 50 ^ 29 7 ^ 8 ^ 10 ^ 第七 章 查找 92,22,8,3,50,37,89,94,21，哈希函數為 Hash(key)=key mod 11 用拉鏈法處理沖突，建表如圖 。 找空哈希地址方法很多，下面介紹三種： 1. 線性探測法 Hi=(Hash(key)+di) mod m ( 1≤ i m ) 其中： Hash(key)為哈希函數 m 為哈希表長度 di 為增量序列 1， 2，??， m1，且 di=i 【例 】關鍵碼集為 {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 2
公司管理相關推薦
鄂ICP備17016276號-1