作者：coolblog
segmentfault.com/a/1190000010799123
1. 背景
某天，我在写代码的时候，无心中点开了 String hashCode 办法。而后大抵看了一下 hashCode 的实现，发现并不是很简单。然而我从源码中发现了一个奇怪的数字，也就是本文的配角 31。
这个数字竟然不是用常量申明的，所以没法从字面意思上推断这个数字的用处。起初带着疑难和好奇心，到网上去找材料查问一下。在看完材料后，默默的感叹了一句，原来是这样啊。那么到底是哪样呢？
在接下来章节里，请大家带着好奇心和我揭开数字 31 的用处之谜。
2. 抉择数字 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;
}下面的代码就是 String hashCode 办法的实现，是不是很简略。实际上 hashCode 办法外围的计算逻辑只有三行，也就是代码中的 for 循环。hashCode 和 identityHashCode 的区别你晓得吗？
咱们能够由下面的 for 循环推导出一个计算公式，hashCode 办法正文中曾经给出。如下：
s\[0\]\*31^(n-1) + s\[1\]\*31^(n-2) + ... + s\[n-1\]这里阐明一下，下面的 s 数组即源码中的 val 数组，是 String 外部保护的一个 char 类型数组。这里我来简略推导一下这个公式：
假如 n=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^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]下面的公式包含公式的推导并不是本文的重点，大家理解理解即可。接下来来说说本文的重点，即抉择 31 的理由。从网上的材料来看，个别有如下两个起因：
第一，31 是一个不大不小的质数，是作为 hashCode 乘子的优选质数之一。 另外一些相近的质数，比方 37、41、43 等等，也都是不错的抉择。 那么为啥偏偏选中了 31 呢？ 请看第二个起因。
第二、31 能够被 JVM 优化，31 * i = (i << 5) – i。
下面两个起因中，第一个须要解释一下，第二个比较简单，就不说了。上面我来解释第一个理由。个别在设计哈希算法时，会抉择一个非凡的质数。至于为啥抉择质数，我想应该是能够升高哈希算法的抵触率。
至于起因，这个就要问数学家了，我简直能够疏忽的数学程度解释不了这个起因。下面说到，31 是一个不大不小的质数，是优选乘子。那为啥同是质数的 2 和 101（或者更大的质数）就不是优选乘子呢，剖析如下。
这里先剖析质数 2。首先，假如 n = 6，而后把质数 2 和 n 带入下面的计算公式。并仅计算公式中次数最高的那一项，后果是 2^5 = 32，是不是很小。
所以这里能够判定，当字符串长度不是很长时，用质数 2 做为乘子算出的哈希值，数值不会很大。也就是说，哈希值会散布在一个较小的数值区间内，散布性不佳，最终可能会导致抵触率回升。
下面说了，质数 2 做为乘子会导致哈希值散布在一个较小区间内，那么如果用一个较大的大质数 101 会产生什么样的后果呢？
依据下面的剖析，我想大家应该能够猜出后果了。就是不必再放心哈希值会散布在一个小的区间内了，因为 101^5 = 10,510,100,501。
然而要留神的是，这个计算结果太大了。如果用 int 类型示意哈希值，后果会溢出，最终导致数值信息失落。只管数值信息失落并不一定会导致抵触率回升，然而咱们暂且先认为质数 101（或者更大的质数）也不是很好的抉择。最初，咱们再来看看质数 31 的计算结果：31^5 = 28629151，后果值绝对于 32 和 10,510,100,501 来说。是不是很 nice，不大不小。
下面用了比拟简陋的数学伎俩证实了数字 31 是一个不大不小的质数，是作为 hashCode 乘子的优选质数之一。
接下来我会用具体的试验来验证下面的论断，不过在验证前，咱们先看看 Stack Overflow 上对于这个问题的探讨，Why does Java’s hashCode() in String use 31 as a multiplier?。其中排名第一的答案援用了《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 虚拟机能够主动的实现这个优化。
排名第二的答案设这样说的：
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 实现所选用也就难能可贵了。
下面的两个答案完满的解释了 Java 源码中选用数字 31 的起因。接下来，我将针对第二个答案就行验证，请大家持续往下看。
3. 试验及数据可视化
本节，我将应用不同的数字作为乘子，对超过 23 万个英文单词进行哈希运算，并计算哈希算法的抵触率。同时，我也将针对不同乘子算出的哈希值散布状况进行可视化解决，让大家能够直观的看到数据分布状况。
本次实验所应用的数据是 Unix/Linux 平台中的英文字典文件，文件门路为 /usr/share/dict/words。
3.1 哈希值抵触率计算
计算哈希算法抵触率并不难，比方能够一次性将所有单词的 hash code 算出，并放入 Set 中去除反复值。之后拿单词数减去 set.size() 即可得出抵触数，有了抵触数，抵触率就能够算进去了。当然，如果应用 JDK8 提供的流式计算 API，则可更不便算出，代码片段如下：
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，抵触率达到了 55.14%。同时咱们留神察看质数 2 作为乘子时，哈希值的散布状况。能够看得出来，哈希值散布并不是很广，仅仅散布在了整个哈希空间的正半轴局部，即 0 ~ 231-1。而负半轴 -231 ~ -1，则无散布。
这也证实了咱们下面断言，即质数 2 作为乘子时，对于短字符串，生成的哈希值散布性不佳。而后再来看看咱们之前所说的 31、37、41 这三个不大不小的质数，体现都不错，抵触数都低于 7 个。而质数 101 和 199 体现的也很不错，抵触率很低，这也阐明哈希值溢出并不一定会导致抵触率回升。然而这两个家伙一言不合就溢出，咱们认为他们不是哈希算法的优选乘子。
最初咱们再来看看 32 和 36 这两个偶数的体现，后果并不好，尤其是 32，抵触率超过了了 50%。只管 36 体现的要好一点，不过和 31，37 相比，抵触率还是比拟高的。当然并非所有的偶数作为乘子时，抵触率都会比拟高，大家有趣味能够本人验证。
3.2 哈希值散布可视化
上一节剖析了不同数字作为乘子时的抵触率状况，这一节来剖析一下不同数字作为乘子时，哈希值的散布状况。在详细分析之前，我先说说哈希值可视化的过程。
我本来是打算将所有的哈希值用一维散点图进行可视化，然而起初找了一圈，也没找到适合的画图工具。加之起初想了想，一维散点图可能不适合做哈希值可视化，因为这里有超过 23 万个哈希值。也就意味着会在图上显示超过 23 万个散点，如果不出意外的话，这 23 万个散点会汇集的很密，有可能会变成一个大黑块，就失去了可视化的意义了。
所以这里抉择了另一种可视化成果更好的图表，也就是 excel 中的平滑曲线的二维散点图（上面简称散点曲线图）。当然这里同样没有把 23 万散点都显示在图表上，太多了。所以在理论绘图过程中，我将哈希空间等分成了 64 个子区间，并统计每个区间内的哈希值数量。最初将分区编号做为 X 轴，哈希值数量为 Y 轴，就绘制出了我想要的二维散点曲线图了。
这里举个例子阐明一下吧，以第 0 分区为例。第 0 分区数值区间是 [-2147483648, -2080374784)，咱们统计落在该数值区间内哈希值的数量，失去 < 分区编号, 哈希值数量 > 数值对，这样就能够绘图了。分区代码如下：
/**
* 将整个哈希空间等分成 64 份，统计每个空间内的哈希值数量
* @param hashs
*/
public static Map<Integer, Integer> partition(List<Integer> hashs) {
// step = 2^32 / 64 = 2^26
final int step = 67108864;
List<Integer> nums = new ArrayList<>();
Map<Integer, Integer> statistics = new LinkedHashMap<>();
int start = 0;
for (long i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i += step) {
final long min = i;
final long max = min + step;
int num = (int) hashs.parallelStream()
.filter(x -> x >= min && x < max).count();
statistics.put(start++, num);
nums.add(num);
}
// 为了避免计算出错，这里验证一下
int hashNum = nums.stream().reduce((x, y) -> x + y).get();
assert hashNum == hashs.size();
return statistics;
}本文中的哈希值是用整形示意的，整形的数值区间是 [-2147483648, 2147483647]，区间大小为 2^32。所以这里能够将区间等分成 64 个子区间，每个自子区间大小为 2^26。具体的分区对照表如下：
接下来，让咱们对照下面的分区表，对数字 2、3、17、31、101 的散点曲线图进行简略的剖析。先从数字 2 开始，数字 2 对于的散点曲线图如下：
下面的图还是很一幕了然的，乘子 2 算出的哈希值简直全副落在第 32 分区，也就是 [0, 67108864) 数值区间内，落在其余区间内的哈希值数量简直能够忽略不计。这也就不难解释为什么数字 2 作为乘子时，算出哈希值的抵触率如此之高的起因了。所以这样的哈希算法要它有何用啊，拖出去斩了吧。接下来看看数字 3 作为乘子时的体现：
3 作为乘子时，算出的哈希值散布状况和 2 很像，只不过略微好了那么一点点。从图中能够看出绝大部分的哈希值最终都落在了第 32 分区里，哈希值的散布性很差。这个也没啥用，拖出去枪毙 5 分钟吧。在看看数字 17 的状况怎么样：
数字 17 作为乘子时的体现，显著比下面两个数字好点了。尽管哈希值在第 32 分区和第 34 分区有肯定的汇集，然而相比拟下面 2 和 3，状况显著好好了很多。除此之外，17 作为乘子算出的哈希值在其余区也均有散布，且较为平均，还算是一个不错的乘子吧。
接下来来看看咱们本文的配角 31 了，31 作为乘子算出的哈希值在第 33 分区有肯定的小汇集。不过相比于数字 17，配角 31 的体现又好了一些。首先是哈希值的汇集水平没有 17 那么重大，其次哈希值在其余区散布的状况也要好于 17。总之，选 31，准没错啊。
最初再来看看大质数 101 的体现，不难看出，质数 101 作为乘子时，算出的哈希值散布状况要好于配角 31，有点喧宾夺主的意思。不过不可否认的是，质数 101 的作为乘子时，哈希值的散布性的确更加平均。所以如果不在意质数 101 容易导致数据信息失落问题，或者其是一个更好的抉择。
4. 写在最初
通过下面的剖析与实际，我想大家应该明确了 String hashCode 办法中抉择应用数字 31 作为乘子的起因了。本文实质是一篇简略的科普文而已，并没有银弹????。
如果大家读完后感觉又涨常识了，那这篇文章的目标就达到了。
最初，本篇文章的配图画的还是很辛苦的，所以如果大家感觉文章不错，无妨就给个赞吧，就当是对我的激励了。
另外，如果文章中有不妥或者谬误的中央，也欢送指出来。如果能不吝赐教，那就更好了。最初祝大家生存欢快，再见。
近期热文举荐：
1.Java 15 正式公布，14 个新个性，刷新你的认知！！
2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了，真香！
3. 我用 Java 8 写了一段逻辑，共事直呼看不懂，你试试看。。
4. 吊打 Tomcat，Undertow 性能很炸！！
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！