設(shè)有一個(gè)哈希函數(shù)
H( c ) = c % N;
當(dāng)N取一個(gè)合數(shù)時(shí)，最簡單的例子是取2^n，比如說取2^3=8,這時(shí)候
H( 11100(二進(jìn)制） ) = H( 28 ) = 4
H( 10100(二進(jìn)制) ) = H( 20 ）= 4

因?yàn)槌砸粋€(gè)2^n，可以看為向左移動(dòng)n位，而模除得到的余數(shù)其實(shí)就是這移掉的n位數(shù)，因此在這種情況下，除開這低位的n位數(shù)以外，剩余的高位數(shù)所有位都沒有利用上，也就是說無論高位上的位取什么數(shù)，都對(duì)最后的余數(shù)不影響，從而有很多不同的數(shù)，但由于低n位是一樣的，所以依然發(fā)生沖突。也就是導(dǎo)致沖突的幾率增大。

關(guān)于為什么模除以素?cái)?shù)就比除以合數(shù)沖突概率小？以下是個(gè)人推測：

　　當(dāng)除以一個(gè)素?cái)?shù)的時(shí)候(素?cái)?shù)定義：只有1和它本身兩個(gè)因數(shù)的自然數(shù))，由于該數(shù)不是2的倍數(shù)，因此除法不能完整的說是左右多少位，如果硬要除以該素?cái)?shù)按進(jìn)行移位來算的話，可以說移掉的低多少位，不再是一個(gè)整數(shù)，那么模除將影響的不再是低多少位數(shù)，而是相比于合數(shù)來說，要影響更多位，甚至說基本上會(huì)影響一個(gè)數(shù)所有的而二進(jìn)制位。從而讓一個(gè)數(shù)的所有二進(jìn)制位都對(duì)最后產(chǎn)生的模除結(jié)果發(fā)揮了作用，相比于模除一個(gè)合數(shù)僅僅是低n位發(fā)揮作用來說，模除以一個(gè)素?cái)?shù)發(fā)生沖突的概率就會(huì)更小。

　　

轉(zhuǎn)載于:https://www.cnblogs.com/lordcheng/p/7344652.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[原创] 为什么模除的时候一般建议选择素数来除？比如说hashtable的桶数会取一个素数...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。