數(shù)據(jù)結(jié)構(gòu)散列hashing-wenkub
2023-05-24 00:10:00 本頁面
【正文】 這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突?？筛鶕?jù)散列表的大小，選取其中各種符號分布均勻的若干位作為散列地址。 它先計算構(gòu)成關(guān)鍵字 的標(biāo)識符的內(nèi)碼的平方 ， 然后按照散列表的大小取中間 的若干位作為散列地址 。 例 如 ， 若散列地址總數(shù)取為 m = 2r， 則對內(nèi)碼的平方數(shù) 取中間的 r位 。 ? 有兩種疊加方法： ? 移位法 — 把各部分的最后一位對齊相加； ? 分界法 — 各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當(dāng)做散列地址。散列函數(shù)為： hash ( key ) = key % p p ? m ? 其中 , “%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù) p不是接近 2的冪。則散列地址為： 20210203 hash ( 962148 ) = 962148 % 23 = 12 ? 可以按計算出的地址存放記錄。 有人曾用 “ 輪盤賭 ” 的統(tǒng)計分析方法對它們進行了模擬分析 ， 結(jié)論是平方取中法最接近于 “ 隨機化 ” 。如 , ASCII碼采用 7位字符代碼，因此每一個字符可以看成一個 128進制的數(shù)字。 20210203 1. 開放定址法（閉散列） ——是處理溢出的一種常用的方法 ? Hash函數(shù)： Hi = (H(key)+di) MOD m, i=1,2,… ,k(k≤m 1) 其中： H(key)為哈希函數(shù) ， m為哈希表表長 ， di為增量序列 。 ? 示例 ——P258例 93 20210203 ? = n / m 散列函數(shù) 種類 鏈地 址法 開放定址法 鏈地 址法 開放定址法 鏈地 址法 開放 定址法 鏈地 址法 開放 定址法 平平 方方 取取 中中 11 .. 22 66 11 .. 77 33 11 .. 44 00 99 .. 77 55 11 .. 44 55 33 11 00 .. 11 44 11 .. 44 77
試題試卷相關(guān)推薦
鄂ICP備17016276號-1