为何哈希函数取余法要避免2的幂?

Question

百科上说直接取余法：f(x):=xmodmaxM;maxM一般是不太接近2^t的一个质数。听说是为了尽量避免冲突,我搞不懂怎么就能避免了?

Answer 1

我觉得这个是从二进制的角度考虑的。接近2^i的种子，二进制表达时中间必然产生大段的0或1。
那么以10000000000011这个种子为例，把它翻n倍：
1000000000001100
110000000001001
100000000000110
10000000000011
可以看到，如果种子过于接近2^i，那么无论如何翻倍，种子中间仍然会有大段的0或1。
取余运算的本质无非是个减去种子n倍的减法。那么做减法的时候，种子中间大段的0或1就会让哈希原值的中间一段，有非常大的可能性仍然保持原样。
哈希函数的本质目的就是混淆，原值的变化产生哈希值无规律、等概率、不可预测、不能逆推的变化为最佳。
如果做完哈希运算之后，哈希值和原值中间居然有一大段二进制位保持不变，那么这个哈希函数就可以说是失败到不能再失败了。
当然必须说明的是：简单取余这个哈希函数本来就是非常失败的。简单分析即可，不必深究，也不要在任何真正的产品代码中实用。