• 151

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

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

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

阅读 6k
评论
    2 个回答
    • 21.7k

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

    那么以10000000000011这个种子为例,把它翻n倍:

    1000000000001100
     110000000001001
     100000000000110
      10000000000011
    

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

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

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

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


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

      哈希函数的重要特性沙渺的答案也指出了,就是要尽量让输出等概率,从而降低碰撞的频率。不过剩下的条件我觉的不一定适用。从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上发言,有错误和不妥之处还请各位大牛多多指正。

        撰写回答

        登录后参与交流、获取后续更新提醒