HashMap的死循环(HashMap infinite loop)

仅供学习交流,如有错误请指出,如要转载请加上出处,谢谢

HashMap是一个线程不安全的key-value的存储集合,也意味着它在多线程的环境中也存在很大的风险。

HashMap的存储结构:

通常来讲,HashMap是由一个数组和一个链表组成,在初始化的时候,HashMap会初始化一个数组table[],在不指定容量的情况下默认为16,负载系数为0.75,HashMap在put的时候会通过key的hash值来计算这个数组的下标,然后就把这个存储集合存储在该下标的数组中,在查找时的复杂度为O(1),然而在Hash算法中,很有可能存在不同的key算出相同的值,HashMap就会把相同的值用链表来表示,这个时候就要遍历链表了,查找复杂度为O(n)

正是由于链表的存在,在多线程的环境下,共享链表,这就会变得不安全了

什么时候链表会变得不安全呢?HashMap的容量是动态的,随着容量的增加而增量,在每次put的时候都会检查当前的容量是否满足,假设上述图片的容量为4,如果当前的容量大于4乘以0.75(负载因子),就会创建一个4乘以2的容量的新数组,将老的数组Copy到新的数组,然后所有的值就会重新hash,也就是rehash

现在我们模拟两个线程下的rehash情况,我们有两个线程:Thread1,Thread2,我们先看看HashMap中的rehash方法transfer().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// tranfer()片段
// 这是在resize()中调用的方法,resize()就是HashMap扩容的方法
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next; //假设线程1停留在这里就挂起了,线程2登场
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}

此时运行完Thread1:

此时Entry e是e1,Entry next = e.next中的next是next1,红色是还没有完成,指针指向步骤还没有开始。
现在Thread2登场了,Thread2运行完结构如下:

发现与Thread1的情况刚好反过来了,此时Entry e是e2,Entry next = e.next中的next是next2,是的,Thread2已经完成了指针指向操作了

1
2
3
4
5
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;//假设Thread2已经走了这里

这个时候Thread1要登场了,从Entry next = e.next;开始继续运行下去,此时在Thread2的影响下Thread1运行的结构已经变了

此时由于Thread2的影响,(key:2 ,value:b)已经指向了(key:1,value:a),而红线是Thread1接下来的操作,完成指针指向操作,当Thread1完成时结构如下

这个时候你就会发现圆圈内形成了一个闭环,infinite loop就形成了!!!!