數(shù)據(jù)結(jié)構(gòu)散列hashing-wenkub.com
2025-05-09 00:10 本頁(yè)面
【正文】 其中 n為整數(shù) 處理沖突的方法 20210203 2. 再哈希法（也稱(chēng)雙散列法） Hi = R Hi (key) 20210203 3. 鏈地址法 —開(kāi)散列方法 ? 將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性 表中 。 20210203 ? 如果這個(gè)整數(shù)之和太大，再選擇一個(gè)適當(dāng)?shù)某?shù) C (大于任一段字符串轉(zhuǎn)換成的整數(shù) )來(lái)除這個(gè)和并取其余數(shù)，就得到這個(gè)字符串所對(duì)應(yīng)的整數(shù)了。 ? 把每一個(gè)字符看成為一個(gè)數(shù)字，把字符串的每一段看作為一個(gè)整數(shù)。 在實(shí)際工作中應(yīng)根據(jù)關(guān)鍵字的特點(diǎn) ， 選用適當(dāng)?shù)姆椒?。散列函數(shù) hash ( key ) = key % p。 20210203 5. 除留余數(shù)法 ? 設(shè)散列表中允許的地址數(shù)為 m,取一個(gè)不大于 m，但最接近于或等于 m的質(zhì)數(shù) p,或選取一個(gè)不小于 20的質(zhì)因數(shù)的合數(shù)作為除數(shù)，利用以下公式把關(guān)鍵字轉(zhuǎn)換成散列地址。 ? 把這些部分的數(shù)據(jù)疊加起來(lái)，就可以得到具有該關(guān)鍵字的記錄的散列地址。 ? 在平方取中法中 ， 一般取散列地址為 2的某次冪 。 20210203 3. 平方取中法 ? 此方法在詞典處理中使用十分廣泛 。這 r 種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻些；在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)。 ? 散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算 出結(jié)果。若關(guān)鍵字相等，則查找成功。 ? 順序查找，比較的結(jié)果為 “ =”或 “ ≠ ” ? 非順序查找，比較的結(jié)果為 “ ”， “ =”， “ ” ? 散列的思想： 根據(jù)紀(jì)錄的關(guān)鍵字直接找到記錄的存儲(chǔ)位置， 即為關(guān)鍵字和記錄的存儲(chǔ)位置建立一個(gè)對(duì)應(yīng) 關(guān)系 f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的 存儲(chǔ)位置相對(duì)應(yīng)。 對(duì)應(yīng)關(guān)系 f為散列函數(shù)，按該思想建立的表 為散列表。在存放表項(xiàng)時(shí)，依相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。 哈希函數(shù)的構(gòu)造方法 20210203 1. 直接定址法 此類(lèi)函數(shù)直接取關(guān)鍵字或關(guān)鍵字的某個(gè) 線性函數(shù) 值作為散列地址： Hash ( key ) ＝ a * key + b { a, b為常數(shù) } ?
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1