乐趣区

关于java:面经手册-第2篇数据结构HashCode为什么使用31作为乘数

jiezi


作者：小傅哥
博客：https://bugstack.cn

积淀、分享、成长，让本人和别人都能有所播种！????

一、前言

在面经手册的前两篇介绍了 [《面试官都问我啥》]() 和[《认知本人的技术栈盲区》]()，这两篇内容次要为了阐明面试过程的考查范畴，包含集体的自我介绍、技术栈积攒、我的项目教训等，以及在技术栈盲区篇章中介绍了一个整套技术栈在零碎架构用的利用，以此全方面的扫描本人有哪些盲区还须要补充。而接下来的章节会以各个系列的技术栈中遇到的面试题作为切入点，解说技术要点，理解技术原理，包含；数据结构、数据算法、技术栈、框架等进行逐渐开展学习。

在进入数据结构章节解说之前能够先理解下，数据结构都有哪些，根本能够包含；数组 (Array)、 栈(Stack)、队列 (Queue)、 链表 (LinkList)、 树(Tree)、散列表 (Hash)、 堆(Heap)、图(Graph)。

而本文次要解说的就是与散列表相干的 HashCode，原本想先讲HashMap，但随着整顿材料发现与HashMap 的实现中，HashCode的散列占了很重要的一设计思路，所以最好把这部分常识补全，再往下解说。

二、面试题

说到 HashCode 的面试题，可能这是一个十分外围的了。其余考点；怎么实现散列、计算逻辑等，都能够通过这道题的学习理解相干常识。

Why does Java’s hashCode() in String use 31 as a multiplier?

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

三、资源下载

本文解说的过程中波及局部源码等资源，能够通过关注公众号：bugstack 虫洞栈 ，回复下载进行获取{ 回复下载后关上取得的链接，找到编号 ID：19}，包含；

  1. HashCode 源码测试验证工程，interview-03
  2. 103976 个英语单词库.txt，验证 HashCode 值
  3. HashCode 散列散布.xlsx，散列和碰撞图表

四、源码解说

1. 固定乘积 31 在这用到了

// 获取 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 作为乘积值呢？

2. 来自 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.

这段内容次要论述的观点包含；

  1. 31 是一个奇质数，如果抉择偶数会导致乘积运算时数据溢出。
  2. 另外在二进制中，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 被应用就很失常了。
  • 他这句话就就能够作为咱们实际的指向了。

3. Hash 值碰撞概率统计

接下来要做的事件并不难，只是依据 stackoverflow 的答复，统计出不同的乘积数对 10 万个单词的 hash 计算结果。10 个单词表已提供，能够通过关注公众号：bugstack 虫洞栈进行下载

3.1 读取单词字典表

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.[生]丘泽, 高下位镶嵌沼泽"
  • 单词表的文件格式如上，能够自行解析
  • 读取文件的代码比较简单，这里不展现了，能够通过 资源下载 进行获取

3.2 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;
}
  • 这个过程比较简单，与原 hash 函数比照只是替换了可变参数，用于咱们统计不同乘积数的计算结果。

3.3 Hash 碰撞概率计算

想计算碰撞很简略，也就是计算那些呈现雷同哈希值的数量，计算出碰撞总量即可。这里的实现形式有很多，能够应用 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.4 单元测试

@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%

Process finished with exit code 0

以上就是不同的乘数下的 hash 碰撞后果图标展现，从这里能够看出如下信息；

  1. 乘数是 2 时，hash 的取值范畴比拟小，根本是沉积到一个范畴内了，前面内容会看到这块的展现。
  2. 乘数是 3、5、7、17 等，都有较大的碰撞概率
  3. 乘数是 31 的时候，碰撞的概率曾经很小了，根本稳固。
  4. 顺着往下看，你会发现 199 的碰撞概率更小，这就相当于一排奇数的茅坑量多，天然会缩小碰撞。但这个范畴值曾经远超过 int 的取值范畴了，如果用此数作为乘数，又返回 int 值，就会失落数据信息。

4. Hash 值散列散布

除了以上看到哈希值在不同乘数的一个碰撞概率后，对于散列表也就是 hash，还有一个十分重要的点，那就是要尽可能的让数据散列散布。只有这样能力缩小 hash 碰撞次数，也就是前面章节要讲到的 hashMap 源码。

那么怎么看散列散布呢？如果咱们能把 10 万个 hash 值铺到图表上，造成的一张图，就能够看出整个散列散布。然而这样的图会比拟大，当咱们放大看后，就成一个了大黑点。所以这里咱们采取分段统计，把 2 ^ 32 方分 64 个格子进行寄存，每个格子都会有对应的数量的 hash 值，最终把这些数据展现在图表上。

4.1 哈希值分段寄存

public static Map<Integer, Integer> hashArea(List<Integer> hashCodeList) {Map<Integer, Integer> 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 取值范畴内，每个哈希值寄存到不同格子里的数量。
  • 这里也是应用了 java8 的新个性语法，统计起来还是比拟不便的。

4.2 单元测试

@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());
}
  • 这里列出咱们要统计的乘数值，每一个乘数下都会有对应的哈希值数量汇总，也就是 64 个格子里的数量。
  • 最终把这些统计值放入到 excel 中进行图表化展现。

统计图表

  • 以上是一个沉积百分比统计图，能够看到下方是不同乘数下的，每个格子里的数据统计。
  • 除了 199 不能用以外，31 的散列后果相对来说比拟平均。
4.2.1 乘数 2 散列

  • 乘数是 2 的时候，散列的后果根本都沉积在两头，没有很好的散列。
4.2.2 乘数 31 散列

  • 乘数是 31 的时候，散列的成果就非常明显了，根本在每个范畴都有数据寄存。
4.2.3 乘数 199 散列

  • 乘数是 199 是不能用的散列后果，然而它的数据是更加扩散的，从图上能看到有两个小山包。但因为数据区间问题会有数据失落问题，所以不能抉择。

文中援用

  • http://www.tianxiaobo.com/201…
  • https://stackoverflow.com/que…

五、总结

  • 以上次要介绍了 hashCode 抉择 31 作为乘数的次要起因和试验数据验证，算是一个散列的数据结构的案例解说，在后续的相似技术中，就能够解释其余的源码设计思路了。
  • 看过本文至多应该让你能够从根本上解释了 hashCode 的设计，对于他的所有问题也就不须要死记硬背了，学习编程内容除了最开始的模拟到深刻当前就须要一直的钻研数学逻辑和数据结构。
  • 文中参考了优良的 hashCode 材料和 stackoverflow，并亲自做试验验证后果，大家也能够下载本文中资源内容；英文字典、源码、excel 图表等内容。

六、举荐浏览

  • 面经手册 · 开篇《面试官都问我啥》
  • 工作两年简历写成这样，谁要你呀！
  • 讲道理，只有你是一个爱折腾的程序员，毕业找工作真的不须要再花钱培训！
  • 大学四年到毕业工作 5 年的学习路线资源汇总
  • 手写 mybait-spring 外围性能(干货好文一次学会工厂 bean、类代理、bean 注册的应用)
  • 源码剖析 | Mybatis 接口没有实现类为什么能够执行增删改查
退出移动版