科普：String hashCode 方法为什么选择数字31作为乘子

1. 背景

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一个奇怪的数字，也就是本文的主角31。这个数字居然不是用常量声明的，所以没法从字面意思上推断这个数字的用途。后来带着疑问和好奇心，到网上去找资料查询一下。在看完资料后，默默的感叹了一句，原来是这样啊。那么到底是哪样呢？在接下来章节里，请大家带着好奇心和我揭开数字31的用途之谜。
2. 选择数字31的原因

在详细说明 String hashCode 方法选择数字31的作为乘子的原因之前，我们先来看看 String hashCode 方法是怎样实现的，如下：

1. public int hashCode() {
2.     int h = hash;
3.     if (h == 0 && value.length > 0) {
4.         char val[] = value;
6.         for (int i = 0; i < value.length; i++) {
7.             h = 31 * h + val[i];
8.         }
9.         hash = h;
10.     }
11.     return h;
12. }

复制代码

上面的代码就是 String hashCode 方法的实现，是不是很简单。实际上 hashCode 方法核心的计算逻辑只有三行，也就是代码中的 for 循环。我们可以由上面的 for 循环推导出一个计算公式，hashCode 方法注释中已经给出。如下：

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

这里说明一下，上面的 s 数组即源码中的 val 数组，是 String 内部维护的一个 char 类型数组。这里我来简单推导一下这个公式：

1. 假设 n=3
2. i=0 -> h = 31 * 0 + val[0]
3. i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
4. i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
5.        h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
6.        h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]

复制代码

上面的公式包括公式的推导并不是本文的重点，大家了解了解即可。接下来来说说本文的重点，即选择31的理由。从网上的资料来看，一般有如下两个原因：
第一，31是一个不大不小的质数，是作为 hashCode 乘子的优选质数之一。另外一些相近的质数，比如37、41、43等等，也都是不错的选择。那么为啥偏偏选中了31呢？请看第二个原因。

第二、31可以被 JVM 优化，31 * i = (i