為什么一般hashtable的桶數會取一個素數

設有一個哈希函數

H( c ) = c % N;

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

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

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

取其他合數時，都會不同程度的導致c的某些位”失效”，從而在一些常見應用中導致沖突．

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

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

以上就是我的理解

補充一點，這里是說在常見應用中，往往有些數據會比較相近，這時候用質數比較好，比如要存放的數據是壓縮的狀態，比如存儲一個描述當前搜索狀態的表，的這時候哈希不用質數沖突機率就比較大。

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

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

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

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

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

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