【正文】 .10 71 11 分界折疊 22 .97 48 .70 69 .63 91 數(shù)字分析 30 .62 89 .20 12 理論值 10 .50 查找關(guān)鍵字時(shí)所需對(duì)桶的平均訪問(wèn)次數(shù) 從圖中可以看出，鏈地址法優(yōu)于開(kāi)放定址法；在散列函數(shù)中，用除留余數(shù)法作散列函數(shù)優(yōu)于其它類型的散列函數(shù)，最差的是折疊法。則散列地址為： 20210203 hash ( 962148 ) = 962148 % 23 = 12 ? 可以按計(jì)算出的地址存放記錄。 它先計(jì)算構(gòu)成關(guān)鍵字 的標(biāo)識(shí)符的內(nèi)碼的平方 ， 然后按照散列表的大小取中間 的若干位作為散列地址 。 對(duì)應(yīng)關(guān)系 f為散列函數(shù)，按該思想建立的表 為散列表。這 r 種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻些；在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)。 20210203 5. 除留余數(shù)法 ? 設(shè)散列表中允許的地址數(shù)為 m,取一個(gè)不大于 m，但最接近于或等于 m的質(zhì)數(shù) p,或選取一個(gè)不小于 20的質(zhì)因數(shù)的合數(shù)作為除數(shù)，利用以下公式把關(guān)鍵字轉(zhuǎn)換成散列地址。 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ù)據(jù)疊加起來(lái)，就可以得到具有該關(guān)鍵字的記錄的散列地址。 ? 散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算 出結(jié)果。在存放表項(xiàng)時(shí)，依相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。 例 如 ， 若散列地址總數(shù)取為 m = 2r， 則對(duì)內(nèi)碼的平方數(shù) 取中間的 r位 。 有人曾用 “ 輪盤賭 ” 的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析 ， 結(jié)論是平方取中法最接近于 “ 隨機(jī)化 ” 。 其中 n為整數(shù) ? 如果 Hi0, 則 Hi= Hi+ m*n。取質(zhì)數(shù) p= 23。如果換一個(gè)關(guān)鍵字集合，選擇哪幾位要重新決定