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

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

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

前言

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

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），那么逻辑过程就是这样的：

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 的取值范围（上溢），丢失部分数值信息，散列冲突概率不稳定。

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

选31的佐证

以下内容是我自己往上收集和个人筛选的结果，不一定完全正确（个人感觉有些道理，就整理分享给大家）

对于原因1中提到的位运算效率，比较好理解。位运算必然超过乘法运算。Stack Overflow 上关于这个问题的讨论，其中排名第一的答案引用了《Effective Java》中的一段话，这里也引用一下：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

简单翻译下，就是说:

选择数字31是因为它是一个奇质数，如果选择一个偶数会在乘法运算中产生溢出，导致数值信息丢失，因为乘二相当于移位运算。选择质数的优势并不是特别的明显，但这是一个传统。同时，数字31有一个很好的特性，即乘法运算可以被移位和减法运算取代，来获取更好的性能：31 * i == (i << 5) - i，现代的 Java 虚拟机可以自动的完成这个优化。

对于原因2，这就是考虑哈希值的用途问题。但这里需要注意一个问题，为什么要是质数？。我觉得就是质数能很好的对只进行散列分布和减少哈希冲突--这感觉像一个传统。至于比较专业的解释，就得去问数学家了，我这个水平就解答不了了😭

当Stack Overflow上得答案给了我们一点启发：

As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.

意思是：

正如 Goodrich 和 Tamassia 指出的那样，如果你对超过 50,000 个英文单词（由两个不同版本的 Unix 字典合并而成）进行 hash code 运算，并使用常数 31, 33, 37, 39 和 41 作为乘子，每个常数算出的哈希值冲突数都小于7个，所以在上面几个常数中，常数 31 被 Java 实现所选用也就不足为奇了。

按照这个说法，这里贴一个哈希值冲突率计算的案例，请大家一观。整体逻辑是这样的。一次性将所有单词的 hash code 算出，并放入 Set 中去除重复值。之后拿单词数减去 set.size() 即可得出冲突数，有了冲突数，冲突率就可以算出来了。

public static Integer hashCode(String str, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = multiplier * hash + str.charAt(i);
    }

    return hash;
}
    
/**
 * 计算 hash code 冲突率，顺便分析一下 hash code 最大值和最小值，并输出
 * @param multiplier
 * @param hashs
 */
public static void calculateConflictRate(Integer multiplier, List<Integer> hashs) {
    Comparator<Integer> cp = (x, y) -> x > y ? 1 : (x < y ? -1 : 0);
    int maxHash = hashs.stream().max(cp).get();
    int minHash = hashs.stream().min(cp).get();

    // 计算冲突数及冲突率
    int uniqueHashNum = (int) hashs.stream().distinct().count();
    int conflictNum = hashs.size() - uniqueHashNum;
    double conflictRate = (conflictNum * 1.0) / hashs.size();

    System.out.println(String.format("multiplier=%4d, minHash=%11d, maxHash=%10d, conflictNum=%6d, conflictRate=%.4f%%",
                multiplier, minHash, maxHash, conflictNum, conflictRate * 100));
}

我们测试了从2开始到的一些的质数。得到下面的结果。

ps:1就没算了，因为用1和没用是一样的--1乘以任何数都等于数本身，还算个啥呢

从上图可以看出，使用较小的质数做为乘子时，冲突率会很高。尤其是质数2，冲突率达到了 55.14%。同时我们注意观察质数2作为乘子时，哈希值的分布情况。可以看得出来，哈希值分布并不是很广，仅仅分布在了整个哈希空间的正半轴部分，即 0 ~ 2^31-1。而负半轴 -2^31 ~ -1，上一个哈希值都没有。哈希值散列分布性非常不好。

我们看到31、37、41、101 和 199 这几个不大不小的质数，表现都不错，冲突率很低。但为什选择了31呢？

先来说，为什么不是101？我们知道，这个质数是要参与到哈希值的计算的。String字符串的字符数有个三五七八个很常见。我们折中下，取个6的长度，那么在求哈希的时候，最高价就是101的5次幂，结果是：10,510,100,501。别忘了hashcode的数据类型是int类型。就问你能不能装下这一百多个亿？显然不能，这就是原因3中所说的值溢出问题。 更别说，有些字符串的字符数多大十多个的情况了！因此，这个质数，在不影响散列分布性和最小冲突的情况下，越小越好，这样就不会导致hashcode值超出int类型的范围了！

好啦！这就是关于hashcode中质数31的全部内容啦~ 祝大家天天开心，我们下期见！

One more thing

欢迎关注程序视点，这里会不定时分享一些技术要点，更有一些深受资源收藏爱好者会喜欢的优质学习资料。吃瓜、摸鱼、白嫖技术就等你了~