為什么一般hashtable的桶數(shù)會(huì)取一個(gè)素?cái)?shù)

設(shè)有一個(gè)哈希函數(shù)

H( c ) = c % N;

當(dāng)N取一個(gè)合數(shù)時(shí)，最簡(jiǎn)單的例子是取2^n，比如說(shuō)取2^3=8,這時(shí)候

H( 11100(二進(jìn)制） ) = H( 28 ) = 4
H( 10100(二進(jìn)制) ) = H( 20 ）= 4

這時(shí)候c的二進(jìn)制第4位（從右向左數(shù)）就”失效”了，也就是說(shuō)，無(wú)論第c的4位取什么值，都會(huì)導(dǎo)致H( c )的值一樣．這時(shí)候c的第四位就根本不參與H( c )的運(yùn)算，這樣H( c )就無(wú)法完整地反映c的特性，增大了導(dǎo)致沖突的幾率．

取其他合數(shù)時(shí)，都會(huì)不同程度的導(dǎo)致c的某些位”失效”，從而在一些常見(jiàn)應(yīng)用中導(dǎo)致沖突．

但是取質(zhì)數(shù)，基本可以保證c的每一位都參與H( c )的運(yùn)算，從而在常見(jiàn)應(yīng)用中減小沖突幾率．．

（個(gè)人意見(jiàn)：有時(shí)候不取質(zhì)數(shù)效率也不會(huì)太差..但是無(wú)疑取質(zhì)數(shù)之比較保險(xiǎn)的..)

以上就是我的理解

補(bǔ)充一點(diǎn)，這里是說(shuō)在常見(jiàn)應(yīng)用中，往往有些數(shù)據(jù)會(huì)比較相近，這時(shí)候用質(zhì)數(shù)比較好，比如要存放的數(shù)據(jù)是壓縮的狀態(tài)，比如存儲(chǔ)一個(gè)描述當(dāng)前搜索狀態(tài)的表，的這時(shí)候哈希不用質(zhì)數(shù)沖突機(jī)率就比較大。

如果是隨機(jī)分布的整數(shù)，那么哈希模數(shù)只要取到足夠大，在概率上來(lái)說(shuō)都是一樣的，但是這顯然脫離實(shí)際應(yīng)用。

你說(shuō)的情況 是比較特殊的，因?yàn)檫x取了比較小的一個(gè)質(zhì)數(shù)，當(dāng)選去大質(zhì)數(shù)N時(shí)，就可以僅在N進(jìn)制的某一位失效，結(jié)合計(jì)算機(jī)系統(tǒng)的特性，N進(jìn)制位表示法往往是不關(guān)鍵的，而常用的2^N進(jìn)制比較關(guān)鍵，所以可以避免沖突。

其實(shí)，偶用一些大數(shù)做過(guò)測(cè)試，用來(lái)存放一個(gè)壓縮為二進(jìn)制的鄰接矩陣，當(dāng)模數(shù)足夠大時(shí)，即便是合數(shù)也能有很接近質(zhì)數(shù)的效果，但在某些（幾十個(gè)）合數(shù)上會(huì)造成效率嚴(yán)重下降，所以質(zhì)數(shù)是比較保險(xiǎn)的。

你不妨自己做實(shí)驗(yàn)，不要去選隨機(jī)整數(shù)，而要考慮一些常見(jiàn)應(yīng)用，用質(zhì)數(shù)和合數(shù)進(jìn)行測(cè)試，主要考察平均裝載因子，你得到的結(jié)論可能和我一樣：合數(shù)絕大多數(shù)時(shí)候效果也不錯(cuò)，但在一部分合數(shù)上效果差得出奇，而質(zhì)數(shù)幾乎全部都有很好的效果。

我個(gè)人認(rèn)為更普遍意義的理解，如果不取素?cái)?shù)的話是會(huì)有一定危險(xiǎn)的，危險(xiǎn)出現(xiàn)在當(dāng)假設(shè)所選非素?cái)?shù)m=x*y，如果需要hash的key正好跟這個(gè)約數(shù)x存在關(guān)系就慘了，最壞情況假設(shè)都為x的倍數(shù)，那么可以想象hash的結(jié)果為：1~y，而不是1~m。但是如果選桶的大小為素?cái)?shù)是不會(huì)有這個(gè)問(wèn)題。

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

最新評(píng)論