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