數(shù)據(jù)結(jié)構(gòu)散列hashing(專業(yè)版)
【正文】 字符串 abcd看成整數(shù) a*(128)3 + b*(128)2 + c*(128) + d。 20210203 ? 示例：設(shè)給定的關(guān)鍵字為 key = 23938587841，若存儲(chǔ)空間限定 3 位 , 則劃分結(jié)果為每段 3 位 . 上述關(guān)鍵字可劃分為 4段： 239 385 878 41 ? 把超出地址位數(shù)的最高位刪去 , 僅保留最低的 3位，做為可用的散列地址。 但是，它要求散列地址空間的大小與關(guān)鍵字集合的 大小相同。 哈希表的定義 20210203 ? 散列方法在表項(xiàng)的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系 Hash( )，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一存儲(chǔ)位置相對(duì)應(yīng)： Address ＝ Hash ( ) ? 在查找時(shí)，首先對(duì)表項(xiàng)的關(guān)鍵字進(jìn)行函數(shù)計(jì)算，把函數(shù)值當(dāng)做表項(xiàng)的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取表項(xiàng)比較。 因?yàn)閮?nèi) 碼平方數(shù)的中間幾位一般是由標(biāo)識(shí)符所有字符決定 ， 所以對(duì)不同的標(biāo)識(shí)符計(jì)算出的散列地址大多不相同 ， 即使其中有些字符相同 。 20210203 ? 以上介紹了幾種常用的散列函數(shù) 。 ? 示例 ——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 33 11 00 .. 55 33 除留余數(shù) 10 .20 22 .42 25 .79 移位折疊 21 .75 65
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1