數(shù)據(jù)結(jié)構(gòu)散列hashing(更新版)
【正文】 比較。 20210203 根據(jù)設(shè)定的哈希函數(shù) H(key)和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的 “ 像 ” 作為紀(jì)錄在表中的存儲(chǔ)位置，這種表便稱為哈希表，這一影像過程稱為哈希造表或散列，所得存儲(chǔ)位置稱哈希地址或散列地址。 但是，它要求散列地址空間的大小與關(guān)鍵字集合的 大小相同。 ? 設(shè)標(biāo)識(shí)符可以用一個(gè)計(jì)算機(jī)字長(zhǎng)的內(nèi)碼表示 。 20210203 ? 示例：設(shè)給定的關(guān)鍵字為 key = 23938587841，若存儲(chǔ)空間限定 3 位 , 則劃分結(jié)果為每段 3 位 . 上述關(guān)鍵字可劃分為 4段： 239 385 878 41 ? 把超出地址位數(shù)的最高位刪去 , 僅保留最低的 3位，做為可用的散列地址。需要注意的是，使用上面的散列函數(shù)計(jì)算出來的地址范圍是 0到 22，因此，從 23到 24這幾個(gè)散列地址實(shí)際上在一開始是不可能用散列函數(shù)計(jì)算出來的，只可能在處理溢出時(shí)達(dá)到這些地址。字符串 abcd看成整數(shù) a*(128)3 + b*(128)2 + c*(128) + d。 20210203 ? 用不同的方法溢出處理沖突時(shí)散列表的平均查找長(zhǎng)度如圖所示 處 理 溢 出 平 均 搜 索 長(zhǎng) 度 ASL 的 方 法 搜索成功 Sn 搜索不成功 ( 登入新記錄 ) Un 開 放 線性探查法 ?????????????? ?????????????????)( 定址 法 偽隨機(jī)探查法 二次探查法 雙散列法 ? ??????????? 1l og1e ???? 鏈 地 址 法 ( 同義詞子表法 ) ???? ???? ??e 各種方法處理溢出時(shí)的平均查找長(zhǎng)度
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1