數(shù)據(jù)結(jié)構(gòu)散列hashing(存儲(chǔ)版)
【正文】 3 4. 折疊法 ? 此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。取質(zhì)數(shù) p= 23。 20210203 ?轉(zhuǎn)換的方法： ? 把字符串從右向左，按一個(gè)固定長(zhǎng)度 (例如 4 ) 進(jìn)行分段，必要時(shí)可在最左端添一些空格。 其中 n為整數(shù) ? 如果 Hi0, 則 Hi= Hi+ m*n。 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為增量序列 。 有人曾用 “ 輪盤(pán)賭 ” 的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析 ， 結(jié)論是平方取中法最接近于 “ 隨機(jī)化 ” 。散列函數(shù)為： hash ( key ) = key % p p ? m ? 其中 , “%”是整數(shù)除法取余的運(yùn)算，要求這時(shí)的質(zhì)數(shù) p不是接近 2的冪。 例 如 ， 若散列地址總數(shù)取為 m = 2r， 則對(duì)內(nèi)碼的平方數(shù) 取中間的 r位 ?？筛鶕?jù)散列表的大小，選取其中各種符號(hào)分布均勻的若干位作為散列地址。在存放表項(xiàng)時(shí)，依相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。 ? 順序查找，比較的結(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)。 ? 散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算 出結(jié)果。 20210203 3. 平方取中法 ? 此方法在詞典處理中使用十分廣泛 。 ? 把這些部分的數(shù)據(jù)疊加起來(lái)，就可以得到具有該關(guān)鍵字的記錄的散列地址。散列函數(shù) hash ( key ) = key % p。 ? 把每一個(gè)字符看成為一個(gè)數(shù)字，把字符串的每一段看作為一個(gè)整數(shù)。 其中 n為整數(shù) 處理沖突的方法 20210203 2. 再哈希法（也稱(chēng)雙散列法） Hi = R Hi (ke
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1