為什么一般hashtable的桶數(shù)會取一個素數(shù)

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

H( c ) = c % N;

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

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

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

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

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

（個人意見：有時候不取質(zhì)數(shù)效率也不會太差..但是無疑取質(zhì)數(shù)之比較保險的..)

以上就是我的理解

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

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

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

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

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

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

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

最新評論