第二十六講哈希表及其查找(存儲版)
【正文】 方法進行查找。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。 分析這三個因素，盡管哈希函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度，但一般情況下，我們總認(rèn)為所選的哈希函數(shù)是“均勻的”，因此，可不考慮哈希函數(shù)對平均查找長度的影響。查找時，對給定值 kx通過哈希函數(shù)計算出哈希地址 i，先與基本表的 base_tbl[i]單元比較，若相等，查找成功；否則，再到溢出表中進行查找。 線性探測法可能使第 i個哈希地址的同義詞存入第 i+1個哈希地址，這樣本應(yīng)存入第 i+1 第七 章 查找 個哈希地址的元素變成了第 i+2 個哈希地址的同義詞，??，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。 數(shù)字分析法根據(jù) r 種不同的符號，在各位上的分布情況，選取某幾位，組合成哈希地址。 構(gòu)造 哈希函數(shù) 的常用方法 一 . 直接定址法 Hash(key)=a 哈希表與哈希方法 ：選取某個函數(shù)，依該函數(shù)按關(guān)鍵碼計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值 kx計算地址，將 kx與地址單元中元素關(guān)鍵碼進行比，確定查找是否成功，這就是 哈希方法 (雜湊法 )；哈希方法中使用的轉(zhuǎn)換函數(shù)稱為 哈希函數(shù) (雜湊函數(shù) )；按這個思想構(gòu)造的表稱為 哈希表 (雜湊表 )。 2． 理解解決沖突的主要方法 。 ? 教學(xué)難點： 解決地址沖突的方法。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個哈希地址上，這種現(xiàn)象稱為 沖突 (Collision)，映射到同一哈希地址上的關(guān)鍵碼稱為 同義詞 。使用除留余數(shù)法，選取合適的 p 很重要，若哈希表表長為 m，則要求 p≤ m，且接近 m 或等于 m。 3 4 8 5 2 7 0 若哈希地址是兩位，則可取這四位中的任 3 4 8 6 3 0 5 意兩位組合成哈希地址，也 可以取其中兩 3 4 9 8 0 5 8 位與其它兩位疊加求和后，取低兩位作哈 3 4 7 9 6 7 1 希地址。 di) mod m 其中： Hash(key)為哈希函數(shù) m 為哈希表長度， m 要求是某個 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
公司管理相關(guān)推薦
鄂ICP備17016276號-1