HashMap进行put操作会引起死循环?
最近在磕《java并发编程艺术》,在看到第六章的时候出现了下面这段我不是很理解的东西,如下
《java并发编程艺术》截取
为什么要使用ConcurrentHashMap
在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非常低下,基于以上两个原因,便有了ConcurrentHashMap的登场机会。
1. 线程不安全的HashMap
在多线程环境下,使用HashMap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。例如,执行以下代码会引起死循环。
final HashMap
<String, String> map
= new HashMap<> (2);
Thread t
= new Thread (() -> {
for (int i
= 0; i
< 10000; i
++) {
new Thread (() -> map
.put
(UUID
.randomUUID
().toString
(), ""), "ftf" + i
).start
();
}
}, "ftf");
t
.start();
t
.join();
HashMap在并发执行put操作时会引起死循环,是因为多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry。
不知道是不是由于篇幅原因,我觉得作者并没有把为什么会引起死循环说明白,我只好自己再去看源码了
JDK1.8 HashMap源码
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
;
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
;
if (p
.hash
== hash
&&
((k
= p
.key
) == key
|| (key
!= null
&& key
.equals
(k
))))
e
= p
;
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)
treeifyBin
(tab
, hash
);
break;
}
if (e
.hash
== hash
&&
((k
= e
.key
) == key
|| (key
!= null
&& key
.equals
(k
))))
break;
p
= e
;
}
if (e
!= null
) {
V oldValue
= e
.value
;
if (! onlyIfAbsent
|| oldValue
== null
)
e
.value
= value
;
afterNodeAccess
(e
);
return oldValue
;
}
}
++ modCount
;
if (++ size
> threshold
)
resize
();
afterNodeInsertion
(evict
);
return null
;
}
当你看到这的时候是不是还是不懂为什么会有死循环?是的,我看到这也没懂,只能去网上看看大佬们怎么说
百度上关于这个问题的第一篇文章就是这个:https://www.cnblogs.com/wfq9330/p/9023892.html
这源码跟我看的JDK1.8的截然不同,目测应该是JDK1.8以下的
结论
JDK1.8之前,为了提高rehash的速度,冲突链表是使用头插法,因为头插法是操作速度最快的,找到数组位置就直接找到插入位置了,头插法在多线程下回引起死循环JDK1.8之后开始加入红黑树,当链表长度大于8时链表就会转换成红黑树,这样就大大提高了在冲突链表查找的速度,同时因为链表的长度不可能大于8,链表在rehash的消耗就小很多,所以JDK1.8使用尾插法也避免了死循环问题