这篇文章主要讲解了“HashCode使用31作为乘数的原因是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“HashCode使用31作为乘数的原因是什么”吧！
创新互联公司是一家专业提供措美企业网站建设,专注与成都做网站、成都网站建设、H5场景定制、小程序制作等业务。10年已为措美众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。
// 获取hashCode "abc".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的源码中可以看到，有一个固定值31，在for循环每次执行时进行乘积计算，循环后的公式如下；s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
「那么这里为什么选择31作为乘积值呢？」
在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 * 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.
接下来要做的事情并不难，只是根据stackoverflow的回答，统计出不同的乘积数对10万个单词的hash计算结果。10个单词表已提供，可以通过关注公众号：bugstack虫洞栈进行下载
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.[生]丘泽,高低位镶嵌沼泽" 资源下载进行获取 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;
} 想计算碰撞很简单，也就是计算那些出现相同哈希值的数量，计算出碰撞总量即可。这里的实现方式有很多，可以使用set、map也可以使用java8的stream流统计distinct。
private static RateInfo hashCollisionRate(Integer multiplier, List 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);
}
@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 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));
}
} 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199，最终返回一个list结果并输出。「测试结果」
单词数量：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%
Process finished with exit code 0
以上就是不同的乘数下的hash碰撞结果图标展示，从这里可以看出如下信息；
除了以上看到哈希值在不同乘数的一个碰撞概率后，关于散列表也就是hash，还有一个非常重要的点，那就是要尽可能的让数据散列分布。只有这样才能减少hash碰撞次数，也就是后面章节要讲到的hashMap源码。
那么怎么看散列分布呢？如果我们能把10万个hash值铺到图表上，形成的一张图，就可以看出整个散列分布。但是这样的图会比较大，当我们缩小看后，就成一个了大黑点。所以这里我们采取分段统计，把2 ^ 32方分64个格子进行存放，每个格子都会有对应的数量的hash值，最终把这些数据展示在图表上。
public static Map hashArea(List hashCodeList) {
Map statistics = new LinkedHashMap<>();
int start = 0;
for (long i = 0x80000000; i <= 0x7fffffff; i += 67108864) {
long min = i;
long max = min + 67108864;
// 筛选出每个格子里的哈希值数量，java8流统计；https://bugstack.cn/itstack-demo-any/2019/12/10/%E6%9C%89%E7%82%B9%E5%B9%B2%E8%B4%A7-Jdk1.8%E6%96%B0%E7%89%B9%E6%80%A7%E5%AE%9E%E6%88%98%E7%AF%87(41%E4%B8%AA%E6%A1%88%E4%BE%8B).html
int num = (int) hashCodeList.parallelStream().filter(x -> x >= min && x < max).count();
statistics.put(start++, num);
}
return statistics; int取值范围内，每个哈希值存放到不同格子里的数量。@Test
public void test_hashArea() {
System.out.println(HashCode.hashArea(words, 2).values());
System.out.println(HashCode.hashArea(words, 7).values());
System.out.println(HashCode.hashArea(words, 31).values());
System.out.println(HashCode.hashArea(words, 32).values());
System.out.println(HashCode.hashArea(words, 199).values());
} 「统计图表」
感谢各位的阅读，以上就是“HashCode使用31作为乘数的原因是什么”的内容了，经过本文的学习后，相信大家对HashCode使用31作为乘数的原因是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！
