大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
上文回顾
在上文深入源码分析HashMap到底是怎样将元素put进去的
我们着重分析了无参构造函数是如何创建map对象和HashMap是如何将第一个元素put
进table
的。
此篇重点
这篇我们将逐行代码分析
1、有参构造函数是如何创建map对象的
2、当元素增多导致扩容之后,元素是如何重新分布的
同样,为了方便读者复盘,我截取源码是尽量将行号带上。
jdk版本还是1.8
结构图
再重复一遍,HashMap的底层数据结构为数组+链表+红黑树的结构,放一个HashMap的结构示意图,有个大致印象。
解剖思路
创建一个有参构造函数,并往其中添加若干元素,直至触发扩容机制
为了方便方便计算hash值,key和value都选用比较小的字符串
关于调试键的使用请参照:IDEA调试键的说明,在此不再赘诉
调试代码
public static void main(String[] args) {
System.out.println("★★★★★★解剖开始★★★★★★");
HashMap<String, String> map = new HashMap<>(12);
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
// 实验key相同的情况
map.put("4", "D");
map.put("5", "5");
map.put("6", "6");
map.put("7", "7");
map.put("8", "8");
map.put("9", "9");
map.put("10", "10");
map.put("11", "11");
map.put("12", "12");
// 第一个扩容点
map.put("13", "13");
map.put("14", "14");
map.put("15", "15");
map.put("16", "16");
map.put("17", "17");
map.put("18", "18");
map.put("19", "19");
map.put("20", "20");
map.put("21", "21");
map.put("22", "22");
map.put("23", "23");
map.put("24", "24");
//第二个扩容点
map.put("25", "25");
}
断点打在第一行
以debug模式启动,开始解剖之旅
点击Step Over
到HashMap<String, String> map = new HashMap<>(12);
所在行
点击Force Step Into
,会发现先调用的是类加载器
这不是今天的重点,我们直接Step Out
,然后再次点击Force Step Into
,进入源码
调用的是双参构造函数DEFAULT_LOAD_FACTOR
为0.75,initialCapacity
为12,继续Force Step Into
上图来到双参构造函数,继续Force Step Into
会发现依旧调用了父类的构造函数
掉完父类构造函数,继续双参构造函数,经过参数校验,源码456
行之后,loadFactor
=0.75,我们重点看看this.threshold = tableSizeFor(initialCapacity)
在457
行Force Step Into
,会发现跳转到tableSizeFor(int cap)
关于tableSizeFor(int cap)
,在以前的文章详细分析过,有兴趣的可以去看看 读HashMap源码之tableSizeFor,这里直接说结论,就是你给一个初始容量值,经过这个方法后,返回一个最接近该值的、且不小于该值本身的2^n的那个值,当然,最大不能超过static final int MAXIMUM_CAPACITY = 1 << 30
即2的30次方
所以这里传入12
返回的应该是16
,n = 15 ,n+1 = 16
所以看到这应该明白,管你传9 10 11 12 13 14 15 16
,经过tableSizeFor
后都是返回16
,这样就确保了threshold
总是2的n次方,后面就会发现,其实这个值不是给扩容阈值的,而是给map的初始容量
继续Force Step Into
回到双参函数,将tableSizeFor
的结果赋值给threshold
扩容阈值=16
开始 put
到此初始化map完成,其实到了这一步,table
还没建立,继续往下Force Step Into
开始put
继续Force Step Into
进入map.put("1", "1");
,来到源码的put(K key, V value)
源码的put(K key, V value)
又是调用的putVal
,调用之前会计算一下key的hash值,进去看看
key.hashCode()
调用的是String
的hashCode
然后返回put
方法进入putVal
,继续Force Step Into
,此时hash值为49
因为在初始化时,并没有看到有初始化table
,所以此处的table
肯定是null
那顺理成章的就要执行resize()
了,继续Force Step Into
,进入resize()
这个我们在上文 **深入源码分析HashMap到底是怎样将元素put进去的**已经分析了一次,鉴于比较复杂,就再分析一次,还是一样,代码执行路径用红框标记出来
直接返回newTab
通过对上面源码的走读,发现带参构造函数创建的map,
初始容量就取决于源码692
行的newCap = oldThr;
,
而oldThr
又取决于源码680
行的int oldThr = threshold;
还记得threshold
怎么来的吗,源码457
行的tableSizeFor(int initialCapacity)
,你说狗不狗,在这等你呢,
所以tableSizeFor
的真实目的是为了确保所有map初始化时容量均为2的n次幂
扯远了,回来,拉回来,继续Force Step Into
,刚刚走到table创建完,即首次resize
完成
有了数组了,长度也知道了,该考虑元素位置了,上文也详细讲解了,
决定元素位置的是(n - 1) & hash
表达式的结果,自己想动手算的参照上文的方法去算
这里直接看结果,计算出i
=1
因为是刚刚创建的,所以tab[1]
自然为null
,顺理成章的就执行tab[i] = newNode(hash, key, value, null);
,构建一个链表的节点放入1
号位
继续调试,执行完放入元素之后modCount
自增,size
自增,并和扩容阈值(当前是12
)比较,1
小于12
不用扩容,
执行完毕,关于modCount
见上文
自己画个示意图,大概就是这样的,只有1
号位置有元素,其他的均为null
继续Force Step Into
,继续map.put("2", "2");
,这次算的hash值为50
,但此时table
不再为null
,直接计算位置,1
等于2,且该位置为null
,直接构造一个Node
放进去
依次类推,我们就不一一看了,直接Step Over
到map.put("4", "D");
,看看key值相同,value不同时怎么处理
一路Force Step Into
,来到putVal
,发现hash
还是52
,定位的i
也是4
,个位置已经有元素了,所以走了源码634
行
仔细研究一下这行代码
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
p.hash == hash
为ture
,(k = p.key) == key
也为真so执行e = p;
,然后暂时还没有树化,所以源码656
行直接将新的value
覆盖旧的的value
至此,覆盖问题解决,继续Force Step Into
,后面没有值重复的,经过一路Force Step Into
,1-9位置示意图如下
一直put
、put
、put
直到map.put("10", "10");
,为什么到了这里停下来看呢,因为此时hash只不同了,位置大概率也会不同,进去看看
果然,此时hash
已经变成了1567
,比之前的递增大了很多,位置也变成了15
,与此类似,11
的位置为0
截止到目前已经放了11
个元素,位置示意图如下
理论上,再放一个就触及到了我们的扩容阈值threshold = 16*0.75 = 12
,但看一下源码662
行
其实12
的时候还不会,是要大于12
才会,那就继续Force Step Into
走进map.put("12", "12")
事情开始起变化,这hash
值不同,但计算的位置i
=1上却已经有了元素
上面红色框就是代码执行路径,源码642
表明12
节点被放在p
节点即1
号位置的next
,而e
在源码641
赋值时p.next
此时还是null
,所以下面的代码路径是正确的
所以此时的key=1
就有了next
,此时示意图如下:
继续Force Step Into
,发现前半段map.put("13", "13");
还是和map.put("12", "12");
一样
本来按照剧本,key=13
应该被放到2
号位置key=2
的next
示意图应该如下
但是,万事就怕但是,在这里if (++size > threshold)
不满足了
增量扩容
他要再次执行resize()
了进去瞧瞧,先不管元素移动,先看扩容
对比第一次的resize
来看
元素迁移
第二次的容量和阈值都比第一次大了2倍,且oldTab
不再为null
,需要将oldTab
迁移到newTab
所以接下来我们就要品读这段代码了,你先品品
if (oldTab != null) {
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)
((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;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
回到正题,继续Force Step Into
,看源码707
行,for (int j = 0; j < oldCap; ++j)
就是要循环整个旧表
上面的代码分三种情况来读
- 一是位置上只有一个
Node
元素,即next
为null
的,类似上面的3-9
号位置上都只有一个元素 - 第二种一个位置上有多个元素的,类似上面的
1
、2
号位置,目前都有两个元素 - 第三种就是此位置上的元素为
TreeNode
类型的,目前没有,今天先不考虑
对于第一种情况,核心操作就是源码712
行的newTab[e.hash & (newCap - 1)] = e;
计算该元素在新表中的位置,e.hash & (newCap - 1)
所以0
号元素经过e.hash & (newCap - 1)
即1568 & 31
后,工具计算结果在新表的位置是0
然后第二个元素即1
号元素,正好是第二种情况,示意图再看一下
源码709
行oldTab[1]
不为null
,711
行e.next
也不为null
且e instanceof TreeNode
也是false
,所以核心流程来到了719
行的do……while
把do……while
这段单独拎出来看,先定义两个链表的头和尾,一个链表用来装与旧表元素位置相同的元素,一个用来装需要重新分配位置的元素
Node<K,V> loHead = null, loTail = null;// 位置相同的链表的头尾
Node<K,V> hiHead = null, hiTail = null;// 位置要移动的链表头尾
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
当key=1
元素开始执行时,源码721
行e.hash & oldCap
即46 & 16 != 0
,跳转至源码729
继续循环1
号位置,此时e.hash & oldCap
为1569 & 16
结果为0
,所以将e
赋值给loHead
,同时链表尾部loTail
也指向e
由于只有两个元素,循环到此结束了
最后将loHead
放在newTab[1]
即在新数组中与旧数组位置相同的地方
而hiHead
则被放在新的数组newTab[1 + 16]
即在旧数组位置基础上再加上旧数组的容量
以此类推,2
号位上的两个元素分别被放置在新表的2
号和2+16
号位置上
最后操作下来,位置关系如示意图
总结
到此目标完成,总结一下要点
1、HashMap的初始化是在插入第一个元素时调用resize
完成的(源码629
行)
2、不指定容量,默认容量为16(源码694
)
3、指定容量不一定按照你的值来,会经过tableSizeFor
转成不小于输入值的2的n次幂,源码378
这里有个小问题,tableSizeFor
转换成2的n次幂不是直接赋值给capacity
,而是先将值暂时保存在threshold
,见源码457
,然后在put第一个元素resize时,婉转的传递给newCap
4、put元素时,元素的位置取决于数组的长度和key的hash值按位与的结果i = (n - 1) & hash
源码630
4.1 如果这里没有元素,直接放这
4.2 如果有,判断是不是键冲突(源码634
),直接新值覆盖旧值*(源码657
)
4.3 如果有且不是键冲突,则将其放在原元素的next位置(源码642
)
5、只有当size大于了扩容阈值size > threshold
,才会触发扩容,源码662
,扩容前,当前元素已经放好了
6、扩容时,容量和扩容阈值都翻番(源码687
),但要小于MAXIMUM_CAPACITY
7、扩容时,元素在新表中的位置分情况
7.1 当元素只是孤家寡人即元素的next==null
(源码)711
时,位置为e.hash & (newCap - 1)
(源码712
)
7.2 当元素有next
节点时,该链表上的元素分两类
7.21 e.hash & oldCap = 0
的,在新表中与旧表中的位置一样(源码738
)
7.22 e.hash & oldCap != 0
的,位置为旧表位置+旧表容量,源码742
展望:
调了一天,还只是调了其中的一部分,初始化、初始扩容,和增量扩容,类似树化、拆树还没研究呢
构造树化的思路,也是从源码上找,主要是以下几行
只要你能让不同的key的hash值相同,并且key不相同,就可以制造出hash冲突,就能将多个元素放在同一个位置上,然后直至触发树化,具体情况我们下回分解。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190974.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...