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

Question

百科上说
直接取余法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。

听说是为了尽量避免冲突,我搞不懂怎么就能避免了?

Answer 1

我觉得这个是从二进制的角度考虑的。接近2^i的种子，二进制表达时中间必然产生大段的0或1。

那么以10000000000011这个种子为例，把它翻n倍：

1000000000001100
 110000000001001
 100000000000110
  10000000000011

可以看到，如果种子过于接近2^i，那么无论如何翻倍，种子中间仍然会有大段的0或1。

取余运算的本质无非是个减去种子n倍的减法。那么做减法的时候，种子中间大段的0或1就会让哈希原值的中间一段，有非常大的可能性仍然保持原样。

哈希函数的本质目的就是混淆，原值的变化产生哈希值无规律、等概率、不可预测、不能逆推的变化为最佳。

如果做完哈希运算之后，哈希值和原值中间居然有一大段二进制位保持不变，那么这个哈希函数就可以说是失败到不能再失败了。

---

当然必须说明的是：简单取余这个哈希函数本来就是非常失败的。简单分析即可，不必深究，也不要在任何真正的产品代码中实用。

Answer 2

哈希函数的重要特性沙渺的答案也指出了，就是要尽量让输出等概率，从而降低碰撞的频率。不过剩下的条件我觉的不一定适用。从mod可以猜到，这里的哈希是给哈希表算数据该放到哪个bucket里的，而不是用来进行签名/密码保护的(md5, sha-1...)。所以不可预测，不可逆推等不是必要条件。

对一个用于加密的哈希函数来说，原值部分保持不变是非常失败的。不过对一个用在哈希表上的哈希函数，就不能用容易逆推什么的证明它失败了。理论上，若x的分布是平均的，那么maxM取值多少效果都一样好。假设x平均分布在[0, k * maxM]，那么f(x)就会平均分布于[0, maxM]。从排除哈希碰撞的角度看，这已经是最优的分布了。

但是理论归理论，实际上maxM最好还得是个质数，因为x的分布在实际应用中很难做到平均分布，这时候maxM的取值就至关重要。首先不难看出maxM不能取2^t这种数，因为这样等同于把输入数据的高位截断了。如果恰好输入数据变化的只有高位。。。那就会悲剧。。。所有的数据都会被分配到一个桶。比如maxM=256，257%256=1，513%256=1，769%256=1……

再把之前的思路扩展一下，一个哈希函数若能保证在输入数据跟任何整数同余（不光只有2的幂）的情况下，都能避免大量碰撞，那就更好了。在Java的HashMap实现中(http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/HashMap.java?av=f#360)，第368行就解释了通过高低位不断异或的方式打乱同余的规律，从而达到了抑制碰撞的效果。

但要是只能用题目中f(x) = x mod m这种形式呢？假设输入形式是a+k, 2a+k, 3a+k等等：

让X={ja+k | k,j为正整数}, x∈X
让b=gcd(a, m), c=a/b, d=m/b
(ja+k) mod m
=(ja mod m + k mod m) mod m
=[b(jc mod d + k mod m)] mod m
=b[(jc mod d + k mod m) mod d]
因为c和d互质，所以jc mod d的可能取值是d个。
而k mod m又是常数，所以整个等式的可能取值正好是d个。d=m/gcd(a, m)

由此看出f(x)只可能取maxM/gcd(maxM, a)这么多个值。a若跟maxM互质，取值范围就会最大化，哈希函数会达到不错的散布效果。
所以maxM是质数的话，a取多少都能保证良好散布啦。

以上简要写了下我对maxM为啥不能是2^t，而且一般是质数的理解，至于为啥不能接近2^t，我还是没法回答。初次在segmentfault上发言，有错误和不妥之处还请各位大牛多多指正。