面试 28k 职位,老乡面试官从 HashCode 到 HashMap 给我讲了一下午!「回家赶忙整理出 1.6 万字的面试材料」

用户头像
小傅哥
关注
发布于: 2020 年 08 月 23 日
面试28k职位,老乡面试官从HashCode到HashMap给我讲了一下午!「回家赶忙整理出1.6万字的面试材料」

作者:小傅哥

博客:https://bugstack.cn

一、前言



不是面试难,而是30岁要有30岁的能力,35岁要有35岁的经历!



☺️可能有点标题夸张,但本文通篇干货,要不亲身实践各项知识点,很难有这样的深度的总结。有时候我们会抱怨找工作难,但同样企业招聘也难,面试官向我透漏,为了招聘3个高开,以及筛选了200份简历,面试了70场。



本文从HashCode讲到HashMap,从一个小小的知识点扩展的理论实践验证,10来万单词表的数据验证;数据分布扰动函数负载因子数据迁移等各项核心数学知识,非常适合即将跨入高开的程序员学习。



*本文涉及到的源码和图表,可以关注公众号:bugstack虫洞栈,回复下载后,打开获得的链接,找到ID:19,即可下载。*



好!接下来就是我们这次面试的核心知识点总结,通篇1.6万字,需耐心阅读。



二、HashCode为什么使用31作为乘数



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碰撞概率计算



想计算碰撞很简单,也就是计算那些出现相同哈希值的数量,计算出碰撞总量即可。这里的实现方式有很多,可以使用setmap也可以使用java8stream流统计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是不能用的散列结果,但是它的数据是更加分散的,从图上能看到有两个小山包。但因为数据区间问题会有数据丢失问题,所以不能选择。



三、HashMap 数据结构与算法



1. 写一个最简单的HashMap



学习HashMap前,最好的方式是先了解这是一种怎么样的数据结构来存放数据。而HashMap经过多个版本的迭代后,乍一看代码还是很复杂的。就像你原来只穿个裤衩,现在还有秋裤和风衣。所以我们先来看看最根本的HashMap是什么样,也就是只穿裤衩是什么效果,之后再去分析它的源码。



问题:假设我们有一组7个字符串,需要存放到数组中,但要求在获取每个元素的时候时间复杂度是O(1)。也就是说你不能通过循环遍历的方式进行获取,而是要定位到数组ID直接获取相应的元素。



方案:如果说我们需要通过ID从数组中获取元素,那么就需要把每个字符串都计算出一个在数组中的位置ID。字符串获取ID你能想到什么方式? 一个字符串最直接的获取跟数字相关的信息就是HashCode,可HashCode的取值范围太大了[-2147483648, 2147483647],不可能直接使用。那么就需要使用HashCode与数组长度做与运算,得到一个可以在数组中出现的位置。如果说有两个元素得到同样的ID,那么这个数组ID下就存放两个字符串。



以上呢其实就是我们要把字符串散列到数组中的一个基本思路,接下来我们就把这个思路用代码实现出来。



1.1 代码实现



// 初始化一组字符串
List<String> list = new ArrayList<>();
list.add("jlkk");
list.add("lopi");
list.add("小傅哥");
list.add("e4we");
list.add("alpo");
list.add("yhjk");
list.add("plop");
// 定义要存放的数组
String[] tab = new String[8];
// 循环存放
for (String key : list) {
int idx = key.hashCode() & (tab.length - 1); // 计算索引位置
System.out.println(String.format("key值=%s Idx=%d", key, idx));
if (null == tab[idx]) {
tab[idx] = key;
continue;
}
tab[idx] = tab[idx] + "->" + key;
}
// 输出测试结果
System.out.println(JSON.toJSONString(tab));



这段代码整体看起来也是非常简单,并没有什么复杂度,主要包括以下内容;

  1. 初始化一组字符串集合,这里初始化了7个。

  2. 定义一个数组用于存放字符串,注意这里的长度是8,也就是2的倍数。这样的数组长度才会出现一个 0111 除高位以外都是1的特征,也是为了散列。

  3. 接下来就是循环存放数据,计算出每个字符串在数组中的位置。key.hashCode() & (tab.length - 1)

  4. 在字符串存放到数组的过程,如果遇到相同的元素,进行连接操作模拟链表的过程

  5. 最后输出存放结果。



测试结果



key值=jlkk Idx=2
key值=lopi Idx=4
key值=小傅哥 Idx=7
key值=e4we Idx=5
key值=alpo Idx=2
key值=yhjk Idx=0
key值=plop Idx=5
测试结果:["yhjk",null,"jlkk->alpo",null,"lopi","e4we->plop",null,"小傅哥"]



  • 在测试结果首先是计算出每个元素在数组的Idx,也有出现重复的位置。

  • 最后是测试结果的输出,1、3、6,位置是空的,2、5,位置有两个元素被链接起来e4we->plop

  • 这就达到了我们一个最基本的要求,将串元素散列存放到数组中,最后通过字符串元素的索引ID进行获取对应字符串。这样是HashMap的一个最基本原理,有了这个基础后面就会更容易理解HashMap的源码实现。



1.2 Hash散列示意图



如果上面的测试结果不能在你的头脑中很好的建立出一个数据结构,那么可以看以下这张散列示意图,方便理解;





  • 这张图就是上面代码实现的全过程,将每一个字符串元素通过Hash计算索引位置,存放到数组中。

  • 黄色的索引ID是没有元素存放、绿色的索引ID存放了一个元素、红色的索引ID存放了两个元素。



1.3 这个简单的HashMap有哪些问题



以上我们实现了一个简单的HashMap,或者说还算不上HashMap,只能算做一个散列数据存放的雏形。但这样的一个数据结构放在实际使用中,会有哪些问题呢?



  1. 这里所有的元素存放都需要获取一个索引位置,而如果元素的位置不够散列碰撞严重,那么就失去了散列表存放的意义,没有达到预期的性能。

  2. 在获取索引ID的计算公式中,需要数组长度是2的倍数,那么怎么进行初始化这个数组大小。

  3. 数组越小碰撞的越大,数组越大碰撞的越小,时间与空间如何取舍。

  4. 目前存放7个元素,已经有两个位置都存放了2个字符串,那么链表越来越长怎么优化。

  5. 随着元素的不断添加,数组长度不足扩容时,怎么把原有的元素,拆分到新的位置上去。



以上这些问题可以归纳为;扰动函数初始化容量负载因子扩容方法以及链表和红黑树转换的使用等。接下来我们会逐个问题进行分析。



2. 扰动函数



在HashMap存放元素时候有这样一段代码来处理哈希值,这是java 8的散列值扰动函数,用于优化散列效果;



static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}



2.1 为什么使用扰动函数



理论上来说字符串的hashCode是一个int类型值,那可以直接作为数组下标了,且不会出现碰撞。但是这个hashCode的取值范围是[-2147483648, 2147483647],有将近40亿的长度,谁也不能把数组初始化的这么大,内存也是放不下的。



我们默认初始化的Map大小是16个长度 DEFAULT_INITIAL_CAPACITY = 1 << 4,所以获取的Hash值并不能直接作为下标使用,需要与数组长度进行取模运算得到一个下标值,也就是我们上面做的散列列子。



那么,hashMap源码这里不只是直接获取哈希值,还进行了一次扰动计算,(h = key.hashCode()) ^ (h >>> 16)。把哈希值右移16位,也就正好是自己长度的一半,之后与原哈希值做异或运算,这样就混合了原哈希值中的高位和低位,增大了随机性。计算方式如下图;





  • 说白了,使用扰动函数就是为了增加随机性,让数据元素更加均衡的散列,减少碰撞。



2.2 实验验证扰动函数



从上面的分析可以看出,扰动函数使用了哈希值的高半区和低半区做异或,混合原始哈希码的高位和低位,以此来加大低位区的随机性。



但看不到实验数据的话,这终究是一段理论,具体这段哈希值真的被增加了随机性没有,并不知道。所以这里我们要做一个实验,这个实验是这样做;



  1. 选取10万个单词词库

  2. 定义128位长度的数组格子

  3. 分别计算在扰动和不扰动下,10万单词的下标分配到128个格子的数量

  4. 统计各个格子数量,生成波动曲线。如果扰动函数下的波动曲线相对更平稳,那么证明扰动函数有效果。



2.2.1 扰动代码测试



扰动函数对比方法



public class Disturb {
public static int disturbHashIdx(String key, int size) {
return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));
}
public static int hashIdx(String key, int size) {
return (size - 1) & key.hashCode();
}
}



  • disturbHashIdx 扰动函数下,下标值计算

  • hashIdx 非扰动函数下,下标值计算



单元测试



// 10万单词已经初始化到words中
@Test
public void test_disturb() {
Map<Integer, Integer> map = new HashMap<>(16);
for (String word : words) {
// 使用扰动函数
int idx = Disturb.disturbHashIdx(word, 128);
// 不使用扰动函数
// int idx = Disturb.hashIdx(word, 128);
if (map.containsKey(idx)) {
Integer integer = map.get(idx);
map.put(idx, ++integer);
} else {
map.put(idx, 1);
}
}
System.out.println(map.values());
}



以上分别统计两种函数下的下标值分配,最终将统计结果放到excel中生成图表。



2.2.2 扰动函数散列图表



以上的两张图,分别是没有使用扰动函数和使用扰动函数的,下标分配。实验数据;

  1. 10万个不重复的单词

  2. 128个格子,相当于128长度的数组



未使用扰动函数





使用扰动函数





  • 从这两种的对比图可以看出来,在使用了扰动函数后,数据分配的更加均匀了。

  • 数据分配均匀,也就是散列的效果更好,减少了hash的碰撞,让数据存放和获取的效率更佳。



3. 初始化容量和负载因子



接下来我们讨论下一个问题,从我们模仿HashMap的例子中以及HashMap默认的初始化大小里,都可以知道,散列数组需要一个2的倍数的长度,因为只有2的倍数在减1的时候,才会出现01111这样的值。



那么这里就有一个问题,我们在初始化HashMap的时候,如果传一个17个的值new HashMap<>(17);,它会怎么处理呢?



3.1 寻找2的倍数最小值



在HashMap的初始化中,有这样一段方法;



public HashMap(int initialCapacity, float loadFactor) {
...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}



  • 阀值threshold,通过方法tableSizeFor进行计算,是根据初始化来计算的。

  • 这个方法也就是要寻找比初始值大的,最小的那个2进制数值。比如传了17,我应该找到的是32。



计算阀值大小的方法;



static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}



  • MAXIMUM_CAPACITY = 1 << 30,这个是临界范围,也就是最大的Map集合。

  • 乍一看可能有点晕😵怎么都在向右移位1、2、4、8、16,这主要是为了把二进制的各个位置都填上1,当二进制的各个位置都是1以后,就是一个标准的2的倍数减1了,最后把结果加1再返回即可。



那这里我们把17这样一个初始化计算阀值的过程,用图展示出来,方便理解;





3.2 负载因子



static final float DEFAULT_LOAD_FACTOR = 0.75f;



负载因子是做什么的?



负载因子,可以理解成一辆车可承重重量超过某个阀值时,把货放到新的车上。



那么在HashMap中,负载因子决定了数据量多少了以后进行扩容。这里要提到上面做的HashMap例子,我们准备了7个元素,但是最后还有3个位置空余,2个位置存放了2个元素。 所以可能即使你数据比数组容量大时也是不一定能正正好好的把数组占满的,而是在某些小标位置出现了大量的碰撞,只能在同一个位置用链表存放,那么这样就失去了Map数组的性能。



所以,要选择一个合理的大小下进行扩容,默认值0.75就是说当阀值容量占了3/4s时赶紧扩容,减少Hash碰撞。



同时0.75是一个默认构造值,在创建HashMap也可以调整,比如你希望用更多的空间换取时间,可以把负载因子调的更小一些,减少碰撞。



4. 扩容元素拆分



为什么扩容,因为数组长度不足了。那扩容最直接的问题,就是需要把元素拆分到新的数组中。拆分元素的过程中,原jdk1.7中会需要重新计算哈希值,但是到jdk1.8中已经进行优化,不在需要重新计算,提升了拆分的性能,设计的还是非常巧妙的。



4.1 测试数据



@Test
public void test_hashMap() {
List<String> list = new ArrayList<>();
list.add("jlkk");
list.add("lopi");
list.add("jmdw");
list.add("e4we");
list.add("io98");
list.add("nmhg");
list.add("vfg6");
list.add("gfrt");
list.add("alpo");
list.add("vfbh");
list.add("bnhj");
list.add("zuio");
list.add("iu8e");
list.add("yhjk");
list.add("plop");
list.add("dd0p");
for (String key : list) {
int hash = key.hashCode() ^ (key.hashCode() >>> 16);
System.out.println("字符串:" + key + " \tIdx(16):" + ((16 - 1) & hash) + " \tBit值:" + Integer.toBinaryString(hash) + " - " + Integer.toBinaryString(hash & 16) + " \t\tIdx(32):" + ((
System.out.println(Integer.toBinaryString(key.hashCode()) +" "+ Integer.toBinaryString(hash) + " " + Integer.toBinaryString((32 - 1) & hash));
}
}



测试结果



字符串:jlkk Idx(16):3 Bit值:1100011101001000010011 - 10000 Idx(32):19
1100011101001000100010 1100011101001000010011 10011
字符串:lopi Idx(16):14 Bit值:1100101100011010001110 - 0 Idx(32):14
1100101100011010111100 1100101100011010001110 1110
字符串:jmdw Idx(16):7 Bit值:1100011101010100100111 - 0 Idx(32):7
1100011101010100010110 1100011101010100100111 111
字符串:e4we Idx(16):3 Bit值:1011101011101101010011 - 10000 Idx(32):19
1011101011101101111101 1011101011101101010011 10011
字符串:io98 Idx(16):4 Bit值:1100010110001011110100 - 10000 Idx(32):20
1100010110001011000101 1100010110001011110100 10100
字符串:nmhg Idx(16):13 Bit值:1100111010011011001101 - 0 Idx(32):13
1100111010011011111110 1100111010011011001101 1101
字符串:vfg6 Idx(16):8 Bit值:1101110010111101101000 - 0 Idx(32):8
1101110010111101011111 1101110010111101101000 1000
字符串:gfrt Idx(16):1 Bit值:1100000101111101010001 - 10000 Idx(32):17
1100000101111101100001 1100000101111101010001 10001
字符串:alpo Idx(16):7 Bit值:1011011011101101000111 - 0 Idx(32):7
1011011011101101101010 1011011011101101000111 111
字符串:vfbh Idx(16):1 Bit值:1101110010111011000001 - 0 Idx(32):1
1101110010111011110110 1101110010111011000001 1
字符串:bnhj Idx(16):0 Bit值:1011100011011001100000 - 0 Idx(32):0
1011100011011001001110 1011100011011001100000 0
字符串:zuio Idx(16):8 Bit值:1110010011100110011000 - 10000 Idx(32):24
1110010011100110100001 1110010011100110011000 11000
字符串:iu8e Idx(16):8 Bit值:1100010111100101101000 - 0 Idx(32):8
1100010111100101011001 1100010111100101101000 1000
字符串:yhjk Idx(16):8 Bit值:1110001001010010101000 - 0 Idx(32):8
1110001001010010010000 1110001001010010101000 1000
字符串:plop Idx(16):9 Bit值:1101001000110011101001 - 0 Idx(32):9
1101001000110011011101 1101001000110011101001 1001
字符串:dd0p Idx(16):14 Bit值:1011101111001011101110 - 0 Idx(32):14
1011101111001011000000 1011101111001011101110 1110



  • 这里我们随机使用一些字符串计算他们分别在16位长度和32位长度数组下的索引分配情况,看哪些数据被重新路由到了新的地址。

  • 同时,这里还可以观察🕵出一个非常重要的信息,原哈希值与扩容新增出来的长度16,进行&运算,如果值等于0,则下标位置不变。如果不为0,那么新的位置则是原来位置上加16。{这个地方需要好好理解下,并看实验数据}

  • 这样一来,就不需要在重新计算每一个数组中元素的哈希值了。



4.2 数据迁移





  • 这张图就是原16位长度数组元素,像32位数组长度中转移的过程。

  • 其中黄色区域元素zuio因计算结果 hash & oldCap 不为1,则被迁移到下标位置24。

  • 同时还是用重新计算哈希值的方式验证了,确实分配到24的位置,因为这是在二进制计算中补1的过程,所以可以通过上面简化的方式确定哈希值的位置。



四、HashMap源码解析



1. 插入



1.1 疑问点&考题



通过上一章节的学习:《HashMap核心知识,扰动函数、负载因子、扩容链表拆分,深度学习》



大家对于一个散列表数据结构的HashMap往里面插入数据时,基本已经有了一个印象。简单来说就是通过你的Key值取得哈希再计算下标,之后把相应的数据存放到里面。



但再这个过程中会遇到一些问题,比如;

  1. 如果出现哈希值计算的下标碰撞了怎么办?

  2. 如果碰撞了是扩容数组还是把值存成链表结构,让一个节点有多个值存放呢?

  3. 如果存放的数据的链表过长,就失去了散列表的性能了,怎么办呢?

  4. 如果想解决链表过长,什么时候使用树结构呢,使用哪种树呢?



这些疑问点都会在后面的内容中逐步讲解,也可以自己思考一下,如果是你来设计,你会怎么做。



1.2 插入流程和源码分析



HashMap插入数据流程图





visio原版流程图,可以通过关注公众号:bugstack虫洞栈,进行下载



以上就是HashMap中一个数据插入的整体流程,包括了;计算下标、何时扩容、何时链表转红黑树等,具体如下;



  1. 首先进行哈希值的扰动,获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);



  1. 判断tab是否位空或者长度为0,如果是则进行扩容操作。



```java

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

```



  1. 根据哈希值计算下标,如果对应小标正好没有存放数据,则直接插入即可否则需要覆盖。tab[i = (n - 1) & hash])



  1. 判断tab[i]是否为树节点,否则向链表中插入数据,是则向树中插入节点。



  1. 如果链表中插入节点的时候,链表长度大于等于8,则需要把链表转换为红黑树。treeifyBin(tab, hash);



  1. 最后所有元素处理完成后,判断是否超过阈值;threshold,超过则扩容。



  1. treeifyBin,是一个链表转树的方法,但不是所有的链表长度为8后都会转成树,还需要判断存放key值的数组桶长度是否小于64 MIN_TREEIFY_CAPACITY。如果小于则需要扩容,扩容后链表上的数据会被拆分散列的相应的桶节点上,也就把链表长度缩短了。



JDK1.8 HashMap的put方法源码如下:



public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶数组 table,table 被延迟到插入新数据时再进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果桶中不包含键值对节点引用,则将新键值对节点的引用存入桶中即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果键的值以及节点 hash 等于链表中的第一个键值对节点时,则将 e 指向该键值对
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中的引用类型为 TreeNode,则调用红黑树的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 对链表进行遍历,并统计链表长度
for (int binCount = 0; ; ++binCount) {
// 链表中不包含要插入的键值对节点时,则将该节点接在链表的最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表长度大于或等于树化阈值,则进行树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 条件为 true,表示当前链表包含要插入的键值对,终止遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判断要插入的键值对是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 键值对数量超过阈值时,则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}



1.3 扩容机制



HashMap是基于数组+链表和红黑树实现的,但用于存放key值得的数组桶的长度是固定的,由初始化决定。



那么,随着数据的插入数量增加以及负载因子的作用下,就需要扩容来存放更多的数据。而扩容中有一个非常重要的点,就是jdk1.8中的优化操作,可以不需要再重新计算每一个元素的哈希值,这在上一章节中已经讲到,可以阅读系列专题文章,机制如下图;





里我们主要看下扩容的代码(注释部分);



final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// Cap 是 capacity 的缩写,容量。如果容量不为空,则说明已经初始化。
if (oldCap > 0) {
// 如果容量达到最大1 << 30则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按旧容量和阀值的2倍计算新容量和阀值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// initial capacity was placed in threshold 翻译过来的意思,如下;
// 初始化时,将 threshold 的值赋值给 newCap,
// HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 这一部分也是,源代码中也有相应的英文注释
// 调用无参构造方法时,数组桶数组容量为默认容量 1 << 4; aka 16
// 阀值;是默认容量与负载因子的乘积,0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr为0,则使用阀值公式计算容量
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 初始化数组桶,用于存放key
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果旧数组桶,oldCap有值,则遍历将键值映射到新数组桶中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 这里split,是红黑树拆分操作。在重新映射时操作的。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 这里是链表,如果当前是按照链表存放的,则将链表节点按原顺序进行分组{这里有专门的文章介绍,如何不需要重新计算哈希值进行拆分《HashMap核心知识,扰动函数、负载因子、扩容链表拆分,深度学习》}
do {
next = e.next;
if ((e.hash & oldCap) == 0) {