HashCode为什么使用31作为乘数 – FrancisSoung

先来看看stackoverflow的提问，借此来详细做一下剖析。

这个问题其实☞指的就是，hashCode的计算逻辑中，为什么是31作为乘数？

在获取hashCode的源码中可以看到，有一个固定值31，在for循环每次执行时进行乘积计算，循环后的公式如下； s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]

来自stackoverflow的回答

在stackoverflow关于为什么选择31作为固定乘积值，有一篇讨论文章，Why does Java’s hashCode() in String use 31 as a multiplier? 这是一个时间比较久的问题了，摘取两个回答点赞最多的；

413个赞👍的回答

最多的这个回答是来自《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 是一个奇质数，如果选择偶数会导致乘积运算时数据溢出；
另外在二进制中，2个5次方是32，那么也就是 31 * i == (i << 5) – i。这主要是说乘积运算可以使用位移提升性能，同时目前的JVM虚拟机也会自动支持此类的优化。

80个赞👍的回答

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.

这个回答就很有实战意义了，告诉你用超过5万个单词计算hashCode，这个hashCode的运算使用31、33、37、39和41作为乘积，得到的碰撞结果，31被使用就很正常了。

他这句话就就可以作为我们实践的指向了。

Hash值碰撞概率统计

改造Hash计算函数，与原hash函数对比只是替换了可变参数，用于我们统计不同乘积数的计算结果。

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;
}

2. 想计算碰撞很简单，也就是计算那些出现相同哈希值的数量，计算出碰撞总量即可。这里的实现方式有很多，可以使用set、map也可以使用java8的stream流统计distinct。

private static RateInfo hashCollisionRate(Integer multiplier, List<Integer> hashCodeList) {
    int maxHash = hashCodeList.stream().max(Integer::compareTo).get();
    int minHash = hashCodeList.stream().min(Integer::compareTo).get();
    int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());
    double collisionRate = (collisionCount * 1.0) / hashCodeList.size();
    return new RateInfo(maxHash, minHash, multiplier, collisionCount, collisionRate);
}

这里记录了最大hash和最小hash值，以及最终返回碰撞数量的统计结果。

3. 单元测试

这里搞了一个单词库测试，下面是单词库样式

1	a	"n.(A)As 或 A's  安(ampere(a) art.一;n.字母A /[军] Analog.Digital,模拟/数字 /(=account of) 帐上"
2	aaal	American Academy of Arts and Letters 美国艺术和文学学会
3	aachen	 亚琛[德意志联邦共和国西部城市]
4	aacs	Airways and Air Communications Service (美国)航路与航空通讯联络处
5	aah	" [军]Armored Artillery Howitzer,装甲榴弹炮;[军]Advanced Attack Helicopter,先进攻击直升机"
6	aal	"ATM Adaptation Layer,ATM适应层"
7	aapamoor	"n.[生]丘泽,高低位镶嵌沼泽"

@Before
public void before() {
    "abc".hashCode();
    // 读取文件，103976个英语单词库.txt
    words = FileUtil.readWordList("E:/itstack/git/github.com/interview/interview-01/103976个英语单词库.txt");
}

@Test
public void test_collisionRate() {
    List<RateInfo> rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
    for (RateInfo rate : rateInfoList) {
        System.out.println(String.format("乘数 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
    }
}

以上先设定读取英文单词表中的10个单词，之后做hash计算。
在hash计算中把单词表传递进去，同时还有乘积数；2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199，最终返回一个list结果并输出。
这里主要验证同一批单词，对于不同乘积数会有怎么样的hash碰撞结果。

测试结果

单词数量：103976
乘数 = 2, 最小Hash = 97, 最大Hash = 1842581979, 碰撞数量 = 60382, 碰撞概率 = 58.0730%
乘数 = 3, 最小Hash = -2147308825, 最大Hash = 2146995420, 碰撞数量 = 24300, 碰撞概率 = 23.3708%
乘数 = 5, 最小Hash = -2147091606, 最大Hash = 2147227581, 碰撞数量 = 7994, 碰撞概率 = 7.6883%
乘数 = 7, 最小Hash = -2147431389, 最大Hash = 2147226363, 碰撞数量 = 3826, 碰撞概率 = 3.6797%
乘数 = 17, 最小Hash = -2147238638, 最大Hash = 2147101452, 碰撞数量 = 576, 碰撞概率 = 0.5540%
乘数 = 31, 最小Hash = -2147461248, 最大Hash = 2147444544, 碰撞数量 = 2, 碰撞概率 = 0.0019%
乘数 = 32, 最小Hash = -2007883634, 最大Hash = 2074238226, 碰撞数量 = 34947, 碰撞概率 = 33.6106%
乘数 = 33, 最小Hash = -2147469046, 最大Hash = 2147378587, 碰撞数量 = 1, 碰撞概率 = 0.0010%
乘数 = 39, 最小Hash = -2147463635, 最大Hash = 2147443239, 碰撞数量 = 0, 碰撞概率 = 0.0000%
乘数 = 41, 最小Hash = -2147423916, 最大Hash = 2147441721, 碰撞数量 = 1, 碰撞概率 = 0.0010%
乘数 = 199, 最小Hash = -2147459902, 最大Hash = 2147480320, 碰撞数量 = 0, 碰撞概率 = 0.0000%

以上就是不同的乘数下的hash碰撞结果图标展示，从这里可以看出如下信息：

乘数是2时，hash的取值范围比较小，基本是堆积到一个范围内了，后面内容会看到这块的展示；
乘数是3、5、7、17等，都有较大的碰撞概率；
乘数是31的时候，碰撞的概率已经很小了，基本稳定；
顺着往下看，你会发现199的碰撞概率更小，这就相当于一排奇数的茅坑量多，自然会减少碰撞。但这个范围值已经远超过int的取值范围了，如果用此数作为乘数，又返回int值，就会丢失数据信息。