數(shù)據(jù)結(jié)構(gòu)散列hashing-文庫吧資料
2025-05-21 00:10本頁面
【正文】 進行分段，必要時可在最左端添一些空格。 有人曾用 “ 輪盤賭 ” 的統(tǒng)計分析方法對它們進行了模擬分析 ， 結(jié)論是平方取中法最接近于 “ 隨機化 ” 。 20210203 ? 以上介紹了幾種常用的散列函數(shù) 。則散列地址為： 20210203 hash ( 962148 ) = 962148 % 23 = 12 ? 可以按計算出的地址存放記錄。取質(zhì)數(shù) p= 23。散列函數(shù)為： hash ( key ) = key % p p ? m ? 其中 , “%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù) p不是接近 2的冪。 20210203 ? 一般當(dāng)關(guān)鍵字的位數(shù)很多 ， 而且關(guān)鍵字每一位上數(shù)字的分布大致比較均勻時 ， 可用這種方法得到散列地址 。 ? 有兩種疊加方法： ? 移位法 — 把各部分的最后一位對齊相加； ? 分界法 — 各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當(dāng)做散列地址。 20210203 4. 折疊法 ? 此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。 例 如 ， 若散列地址總數(shù)取為 m = 2r， 則對內(nèi)碼的平方數(shù) 取中間的 r位 。 因為內(nèi) 碼平方數(shù)的中間幾位一般是由標(biāo)識符所有字符決定 ， 所以對不同的標(biāo)識符計算出的散列地址大多不相同 ， 即使其中有些字符相同 。 它先計算構(gòu)成關(guān)鍵字 的標(biāo)識符的內(nèi)碼的平方 ， 然后按照散列表的大小取中間 的若干位作為散列地址 。如果換一個關(guān)鍵字集合，選擇哪幾位要重新決定?？筛鶕?jù)散列表的大小，選取其中各種符號分布均勻的若干位作為散列地址。 20210203 2. 數(shù)字分析法 設(shè)有 n個 d位數(shù)，每一位可能有 r種不同的符號。 哈希函數(shù)的構(gòu)造方法 20210203 1. 直接定址法 此類函數(shù)直接取關(guān)鍵字或關(guān)鍵字的某個 線性函數(shù) 值作為散列地址： Hash ( key ) ＝ a * key + b { a, b為常數(shù) } ? 這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突。 ? 散列函數(shù)計算出來的地址應(yīng)
試題試卷相關(guān)推薦
鄂ICP備17016276號-1