为什么String中hashCode方法里使用神奇因子 31呢？

将程序视点设为星标精品文章第一时间阅读

大家好，欢迎来到程序视点！我是小二哥。

今天我们接着聊聊String类型一个有趣的问题：hashCode 方法中的因子31。

前言

我们先来看看 String hashCode 方法是怎样实现的，如下：

代码语言：javascript复制

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i  ) {
            h = 31 * h   val[i];
        }
        hash = h;
    }
    return h;
}

hashCode 方法核心的计算逻辑只有三行，也就是代码中的 for 循环：对value这个char数组每个元素都算个出个和31相关的数。

假设这里value数组的长度为3（value.length = 3），那么逻辑过程就是这样的：

代码语言：javascript复制

i=0 -> h = 31 * 0   val[0]
i=1 -> h = 31 * (31 * 0   val[0]) 
              val[1]
i=2 -> h = 31 * (31 * (31 * 0   val[0])   val[1]) 
              val[2]
//把括号里的数据乘出来
       h = 31*31*31*0   31*31*val[0]   31*val[1]   val[2]
//于是我们可以推导出这个式子
       h = 31^(3-1)*val[0]   31^(3-2)*val[1]   val[2]

上面的 for 循环推导出一个计算公式:

val[0]*31^(n-1) val[1]*31^(n-2) ... val[n-1]

上面公式的推导并不是本文的重点，大家了解了解即可。但需要知道这里时时刻刻都有着31的身影。

选择数字31的原因

原因 1：31 可以被编译器优化为31∗i=(i<<5)−i，位运算和减法运算的效率比乘法运算高。

原因 2: 31 是一个质数：质数是只能被 1 和自身整除的数，使用质数作为乘法因子获得的散列值，在将来进行取模时，得到相同 index 的概率会降低，即降低了哈希冲突的概率。

原因 3: 31 是一个不大不小的质数：质数太小容易造成散列值聚集在一个小区间，提供散列冲突概率；质数过大容易造成散列值超出 int 的取值范围（上溢），丢失部分数值信息，散列冲突概率不稳定。

重点提醒：大家只需要知道上面着三个原因即可。对此想深入了解的，可以继续往下看~ 当成小故事来看就好啦~

0 人点赞