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