hashcode 为什么采用31 质数

義往昔 2月前 ⋅ 143 阅读
 public static int hashCode(int a[]) {
        if (a == null)
            return 0;

        int result = 1;
        for (int element : a)
            result = 31 * result + element;

        return result;
    }

hashCode()方法里为什么要用31这个数字作为生成hashCode的乘数

原因一:更少的乘积结果冲突

  31是质子数中一个“不大不小”的存在,如果你使用的是一个如2的较小质数,那么得出的乘积会在一个很小的范围,很容易造成哈希值的冲突。而如果选择一个100以上的质数,得出的哈希值会超出int的最大范围,这两种都不合适。而如果对超过 50,000 个英文单词(由两个不同版本的 Unix 字典合并而成)进行 hash code 运算,并使用常数 31, 33, 37, 39 和 41 作为乘子,每个常数算出的哈希值冲突数都小于7个(国外大神做的测试),那么这几个数就被作为生成hashCode值得备选乘数了。

原因二:31可以被JVM优化

  JVM里最有效的计算方式就是进行位运算了:

* 左移 << : 左边的最高位丢弃,右边补全0(把 << 左边的数据*2的移动次幂)。
* 右移 >> : 把>>左边的数据/2的移动次幂。
* 无符号右移 >>> : 无论最高位是0还是1,左边补齐0。   

       所以 : 31 * i = (i << 5) - i(左边  31*2=62,右边   2*2^5-2=62) - 两边相等,JVM就可以高效的进行计算啦。。。


全部评论: 0

    我有话说: