作者:葛
博客:付晓

沉淀，分享，成长，让自己和他人都有所收获！

一、前言

《脸型经典手册》前两章介绍了“面试官问了我什么”和“知道自己在技术栈上的盲点”。这两个内容主要说明了面试过程的范围，包括个人介绍、技术栈积累、项目经验等。，并在技术栈盲点一章介绍了一套完整的技术栈在系统架构中的应用，以便扫描各方面我需要补充哪些盲点。以下章节将以各系列技术栈中遇到的面试问题为切入点，讲解技术要点，理解技术原理，包括；数据结构、数据算法、技术栈、框架等等都是逐步学习的。

在进入数据结构这一章之前，你可以知道什么是数据结构，大概上可以包括；数组、堆栈、队列、链表、树、散列、堆和图。

本文主要讲hashmap相关的HashCode，本来想讲HashMap的，但是随着数据的排序和HashMap的实现，HashCode的哈希占了一个很重点的设计思路，所以最好把这部分知识补全，后面再讲。

二、面试题

说到HashCode的面试问题，可能这是一个非常核心的问题。其他考点；如何实现哈希，计算逻辑等。，可以通过对这个问题的研究了解到。

为什么Java & # 39String中的s hashCode()用31做乘数？

这个问题其实指的是在hashCode的计算逻辑中，为什么要用31作为乘数。

三、资源下载

本文过程中涉及到部分源代码和其他资源。关注微信官方账号:bugstack虫洞栈，回复下载即可获得(回复下载后，打开获得的链接，找到编号ID: 19)，包括:

HashCode 源码测试验证工程，interview-03103976个英语单词库.txt，验证HashCode值HashCode散列分布.xlsx，散列和碰撞图表四、源码讲解1. 固定乘积31在这用到了

//获取hashCode & # 34abc & # 34。hashCode()；public int hashCode(){ int h = hash；if(h = = 0 & & value . length & gt；0){ char val[]= value；for(int I = 0；我& lt值.长度；i++){ h = 31 * h+val[I]；} hash = h；}返回h；}从获取hashCode的源代码可以看出，有一个固定值31，每次执行for循环都计算乘积。循环后的公式如下:s[0]*31^(n-1) + s[1]*31^(n-2) +…+ s[n-1]

那么为什么选择31作为这里的产品值呢？

2. 来源stackoverflow的回答

在stackoverflow中，有一篇讨论文章是有关为什么选择31作为固定的产品值，为什么Java & # 39String中的s hashCode()用31做乘数？这是一个由来已久的问题。挑两个赞最多的答案；

413个精彩答案

这个回答大部分来源有效Java的内容；

选择数值31是因为它是一个奇数素数。如果是偶数并且乘法溢出，信息将会丢失，因为乘以2相当于移位。使用素数的优势不太明显，但它是传统的。31的一个很好的特性是乘法可以用移位和减法来代替，以获得更好的性能:31 * I = =(I & lt；& lt5)-I .现代虚拟机会自动进行这种优化。该内容的要点包括:

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

80个好答案

正如Goodrich和Tamassia指出的那样，如果你有超过50，000个英语单词(由Unix的两个变体提供的单词列表的联合构成)，使用常数31、33、37、39和41在每种情况下将产生不到7个冲突。了解了这一点，很多Java实现选择其中一个常量就不足为奇了。这个回答很有实际意义，告诉你计算五万多字的hashCode。这个hashCode操作使用31、33、37、39和41作为乘积，使用31时得到的碰撞结果是正常的。他的话可以作为我们实践的方向。3.哈希值碰撞概率统计接下来要做的事情并不难，只需要依据stackoverflow的回答，统计10万字不同积数的哈希计算结果。已提供10字列表，关注微信官方账号:bugstack虫洞栈即可下载。

3.1 读取单词字典表

1a & # 34；(a) as或A & # 39安(安培)第一条；字母A /[军用]模拟。数字、模拟/数字账户& # 34；2 AAAL美国艺术与文学学院美国艺术与文学学院3亚琛亚琛【联邦德国西部城市】4 AACS航空与空中通信服务公司(美国)5 aah & # 34装甲火炮榴弹炮，装甲火炮榴弹炮；]高级攻击直升机& # 34；6 AAL & # 34；ATM适配层，ATM适配层& # 34；7 aapamoor & # 34邱泽，一个高低镶嵌的沼泽& # 34；单词表的文件格式如上，自己读取文件的代码比较简单，这里不做赘述。可以获取3.2哈希计算函数public static integer hash代码(string str，integer multiplier){ int Hash = 0；for(int I = 0；我& ltstr . length()；i++){ hash = multiplier * hash+str . charat(I)；}返回哈希；}这个过程比较简单。与原来的hash函数相比，它只是替换了可变参数，用于统计不同积数的计算结果。3.3 Hash碰撞概率计算碰撞的计算很简单，就是计算那些Hash值差不多的个数，计算出碰撞的总数。实现这一点的方法有很多。可以使用set和map，也可以使用java8的stream stream statistics来统计distinct。

private static rate info hashCollisionRate(整数乘数，List & lt整数& gthashCodeList){ int max hash = hashCodeList . stream()。max(Integer::compareTo)。get()；int minHash = hashCodeList.stream()。min(Integer::compareTo)。get()；int collision count =(int)(hashcodelist . size()-hashcodelist . stream()。独特()。count())；double collision rate =(collision count * 1.0)/hashcodelist . size()；返回新的RateInfo(maxHash，minHash，multiplier，collisionCount，collision rate)；}这里记录了最大和最小的哈希值，以及最终返回的碰撞次数的统计结果。3.4单元测试@ before public void before(){ & # 34；abc & # 34。hashCode()；//看文件，103976个英文单词。TxtWords = fileutil。read wordlist(& # 34；e:/it stack/git/github . com/interview/interview-01/103976英语词库。txt & # 34);} @ test public void test _ collision rate(){ List & lt；RateInfo & gtrateInfoList = hashcode . collisionratelist(words，2，3，5，7，17，31，32，33，39，41，199)；for(rate info rate:rate infolist){ system . out . println(string . format(& # 34；乘数= %4d，最小哈希= %11d，最大哈希= %10d，冲突数=%6d，冲突概率= % .4f % & # 34、rate.getMultiplier()、rate.getMinHash()、rate.getMaxHash()、rate.getCollisionCount()、rate . getcollisionrate()* 100)；}}以上，设置读取英文单词列表中的10个单词，然后做哈希计算。哈希计算中，传入的是单词列表，也有产品编号；2，3，5，7，17，31，32，33，39，41，199，最后返回一个列表结果并输出。这里主要验证不同产品号的同批词的哈希碰撞结果。试验结果

单词数量：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

微信官方账号:bugstack虫洞栈，hash哈希表。

以上是一个堆积百分比统计图，可以看到下方是不同乘数下的，每个格子里的数据统计。除了199不能用以外，31的散列结果相对来说比较均匀。4.2.1 乘数2散列乘数是2的时候，散列的结果大概都堆积在中间，没有很好的散列。4.2.2 乘数31散列乘数是31的时候，散列的效果就非常明显了，大概在每个范围都有数据存放。4.2.3 乘数199散列乘数是199是不能用的散列结果，但是它的数据是更加分散的，从图上能看到有两个小山包。但因为数据区间问题会有数据丢失问题，所以不能选择。

文中引用

http://www.tianxiaobo.com/2018/01/18/String-hashCode-%E6%96%B9%E6%B3%95%E4%B8%BA%E4%BB%80%E4%B9%88%E9%80%89%E6%8B%A9%E6%95%B0%E5%AD%9731%E4%BD%9C%E4%B8%BA%E4%B9%98%E5%AD%90/https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier五、总结以上主要介绍了hashCode选择31作为乘数的主要原因和实验数据验证，算是一个散列的数据结构的案例讲解，在后续的类似技术中，就可以解释其他的源码设计思路了。看过本文至少应该让你可以从根本上解释了hashCode的设计，有关他的所有问题也就不需要死记硬背了，学习编程内容除了最开始的模仿到深入未来就需要不断的研究数学逻辑和数据结构。文中参考了优秀的hashCode资料和stackoverflow，并亲自做实验验证结果，大家也可以下载本文中资源内容；英文字典、源码、excel图表等内容。