一、造成死循环的原因
HashMap扩容导致死循环的主要原因在于扩容后链表中的节点在新的hash桶使用头插法插入。新的hash桶会倒置原hash桶中的单链表,那么在多个线程同时扩容的情况下就可能导致产生一个存在闭环的单链表,从而导致死循环。
在JDK1.8中,HashMap是不会造成死循环的,因为在JDK1.8中,采用的是尾插法,保证了链表的顺序与之前一致。而且在1.8中链表过长时会转换为红黑树,在转换为红黑树前,也是先根据尾插法生成新链表再进行转换的,所以是不会造成死循环的。
二、JDK1.7中的HashMap扩容原理
在JDK1.7中,HashMap扩容时会通过transfer函数将元素添加到扩容后的数组中,并将table的索引指向这个新的数组
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
//保留要转移指针的下一个节点
Entry<K, V> next = e.next;
//计算出要转移节点在hash桶中的位置
int i = indexFor(e.hash, newCapacity); -----------------1
//使用头插法将需要转移的节点插入到hash桶中原有的单链表中
e.next = newTable[i]; -----------------2
//将hash桶的指针指向单链表的头节点
newTable[i] = e; -----------------3
//转移下一个需要转移的节点
e = next;
} while (e != null);
}
}
}
三、死链过程分析
首先假设在扩容时,hash表中有一个单链表,单链表中有两个元素:元素1和元素2
如果该HashMap为单线程操作时
执行过程:
-
首先 e = 元素1
-
执行到 next = e.next 的时候 next =元素2
-
从 1 到 3 的过程会将 元素1 按照头插法插入到newtable[i]所引用的单链表中
-
然后 e = next 会将 next 赋值给 e,所以就有 e = 元素2
-
判断后 e != null,继续循环,然后以同样方式插入元素2
-
因为 元素2 的 next 为 null 所以最后 e = null
-
这时候循环就结束了,原链表的顺序由 元素1—>元素2 变成了 元素2—>元素1(结果如图所示)。
如果该HashMap为多线程操作时(假设有T1、T2两个线程)
执行过程:
-
T1执行到 next = e.next;时挂起
-
T2开始执行并且执行完了整个流程,也就是说T2把所有元素都插入了新数组之后,原来
-
的table引用现在指向了 newtable,即 table = newtable;
-
这时T1回归继续执行,这时就会有如下场景
-
当元素1正常插入后 next 是 元素2,e = next = 元素2,继续执行插入
-
此时,由于原表中 元素2 的 next 已经被T2所修改,不再是T1挂起时的 next = null了,所以T1就会碰到如下情况,因为 next 永远都不为空,所以就会一直循环执行插入操作,造成死循环。(图中这种状态的链表称为死链)
四、避免死循环
第一种方式:使用HashTable
-
HashTable和HashMap一样都实现了Map接口,但是HashTable是一个线程安全的类,所以不会出现死循环问题。
第二种方式:使用Collections.synchronizeMap(hashMap)
-
该方法是Collections类中的静态方法,返回的是一个线程安全的HashMap
第三种方式:使用concurrentHashMap
-
concurrentHashMap也是一个线程安全类,他比HashTable更为高效。在HashTable中,使用的是同一个锁,所以当一个线程操作某一个功能时,其他线程想要操作另外的功能就要等待锁被让出来。而concurrentHashMap采用了【锁分段】技术,不同的地方使用了不同的锁,功能之间的锁不一样,操作不同功能时就不再需要等待,这样就大大提高了执行效率。