第二十六講哈希表及其查找(參考版)
2024-09-08 14:57本頁面
【正文】 以下給出幾種不同處理沖突方法的平均查找長度： 第七 章 查找 哈希方法存取速度快，也較節(jié)省空間，靜態(tài)查找、動態(tài)查找均適用，但由于存取是隨機的，因此，不便于順序查找。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。 分析這三個因素，盡管哈希函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度，但一般情況下，我們總認為所選的哈希函數(shù)是“均勻的”，因此，可不考慮哈希函數(shù)對平均查找長度的影響。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。所以，對哈希表查找效率的量度，依然用平均查找長度來衡量。一些關(guān)鍵碼可通過哈希函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵碼在哈希函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進行查找。查找時，對給定值 kx通過哈希函數(shù)計算出哈希地址 i，先與基本表的 base_tbl[i]單元比較，若相等，查找成功；否則，再到溢出表中進行查找。 【例 】關(guān)鍵碼序列為 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，哈希函數(shù)為 Hash(key)=key mod 11 用拉鏈法處理沖突，建表如圖 。 3. 雙哈希函數(shù)探測法 Hi=(Hash(key)+i*ReHash(key)) mod m (i=1， 2，??， m1) 其中： Hash(key)， ReHash(key)是兩個哈希函數(shù)， m 為哈希表長度 雙哈希 函數(shù)探測法，先用第一個函數(shù) Hash(key)對關(guān)鍵碼計算哈希地址，一旦產(chǎn)生地址沖突，再用第二個函數(shù) ReHash(key)確定移動的步長因子，最后，通過步長因子序列由探測函數(shù)尋找空的哈希地址。 2. 二次探測法 Hi=(Hash(key)177。 線性探測法可能使第 i個哈希地址的同義詞存入第 i+1個哈希地址，這樣本應(yīng)存入第 i+1 第七 章 查找 個哈希地址的元素變成了第 i+2 個哈希地址的同義詞，??，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。 找空哈希地
公司管理相關(guān)推薦
鄂ICP備17016276號-1