HashMap死循环及JDK1.8的resize()如何维护链表顺序

HashMap死循环

我记得第一次听到HashMap会有死循环的问题是两年前,我们团队有一个学长实习回来给我们说有个同事因为没有注意到HashMap在多线程可能会造成死循环而造成了一些损失。后面就对这个问题很感兴趣,然后趁着今天整理资料就顺便记录一下,虽然偷懒了,逃 = -=

什么造成的

我们知道HashMap不是线程安全的,那么具体到代码,是哪部分代码的原因呢?
我本来想写一篇博客介绍如何死循环产生的原因及过程,然后再查资料的时候发现了美团点评的这篇博客:Java 8系列之重新认识HashMap中介绍死循环的部分已经写的非常清楚了,就不想做重复工作了 = -=,哈哈
但是呢,最主要的问题解决了,我就只好分析一下JDK1.8中是如何做到扩容后链表依然保持着原来的顺序喽~哈哈

resize()方法

JDK1.8的改变

相较于JDK1.7,在1.8中resize()方法不再调用transfer()方法,而是直接将原来transfer()方法中的代码写在自己方法体内;
当然表面上我们能看到方法的减少,其实还有一个重大改变,那就是:扩容后,新数组中的链表顺序依然与旧数组中的链表顺序保持一致!

数组长度的技巧

在分析源码之前,我们还需要知道HashMap底层数组的一些优化:
数组长度总是2的倍数,扩容则是直接在原有数组长度基础上乘以2。

为什么要这么做?有两个优点:

  1. 通过与元素的hash值进行与操作,能够快速定位到数组下标
    相对于取模运算,直接进行与操作能提高计算效率。在CPU中,所有的加减乘除都是通过加法实现的,而与操作时CPU直接支持的。
  2. 扩容时简化计算数组下标的计算量
    因为数组每次扩容都是原来的两倍,所以每一个元素在新数组中的位置要么是原来的index,要么index = index + oldCap,假设

数组长度:2,key:3
0 0 0 1
0 0 1 1 结果为 0 0 0 1 = 1 所以数组下标为1;

扩容后,数组长度:4,key:3
0 0 1 1
0 0 1 1 结果为 0 0 1 1 = 3 = 原来的index + oldCap = 1 + 2


即确定元素在新数组的下标时,我们只需要检测元素的hash值与oldCap作与操作的结果是否为0:为0,那么下标还是原来的下标;为1,那么下标等于原来下标加上旧数组长度。

我们来看关键代码(resize()方法完整代码附后):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//如果扩容后,元素的index依然与原来一样,那么使用这个head和tail指针
Node<K,V> loHead = null, loTail = null
//如果扩容后,元素的index=index+oldCap,那么使用这个head和tail指针
Node<K,V> hiHead = null, hiTail = null
Node<K,V> next;
do {
next = e.next;
//这个地方直接通过hash值与oldCap进行与操作得出元素在新数组的index
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
//tail指针往后移动一位,维持顺序
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
//tail指针往后移动一位,维持顺序
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
//还是原来的index
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//index = index + oldCap
newTab[j + oldCap] = hiHead;
}

resize()方法完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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 thresh
newCap = oldThr;
else { // zero initial threshold signifies usin
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPA
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMU
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = 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, old
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;
//这个地方很巧妙,直接通过e.hash & oldCap得出e在newTab中的位置;
//因为table是2倍扩容,所以只需要看hash值与oldCap进行与操作,结果为0,那么还是原来的index;否则index = index + oldCap
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;
//还是原来的index
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//index 变为 index + oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

附加题

JDK 1.8 是否会出现类似于 JDK 1.7中那样的死循环呢?
我感觉有可能也会出现类似问题。
今下午想了很久,最后还是没有得到一个清晰的答案;
以后有了答案再补回来~

参考资料