轉(zhuǎn)載至：https://www.cnblogs.com/xuwc/p/14044664.html
參考：
https://blog.csdn.net/liu_jm/article/details/105582711
https://blog.csdn.net/gs_albb/article/details/88091808
https://blog.csdn.net/qq_33330687/article/details/101479385
HashMap在jdk1.8也會(huì)出現(xiàn)死循環(huán)的問題（實(shí)測(cè)）
昨天在面試的時(shí)候，面試官問到HashMap在多線程并發(fā)的情況下怎么出現(xiàn)死循環(huán)的破婆？
我當(dāng)時(shí)非常有底氣的回答：Hashmap在jdk1.8之前多線程同時(shí)進(jìn)行put操作，并且同時(shí)進(jìn)行擴(kuò)容的時(shí)候可能會(huì)出現(xiàn)鏈表環(huán)邪乍，導(dǎo)致死循環(huán)的發(fā)生宙帝。
面試官緊接著問：那1.8就不會(huì)出現(xiàn)死循環(huán)了嗎秤朗？
底氣瞬間消失丹莲，思考一會(huì)：1.8在多線程的情況下HashMap會(huì)出現(xiàn)數(shù)據(jù)丟失的問題，比如…（給面試官舉了個(gè)栗子）朗涩。
面試官毫無(wú)波瀾忽孽，好像沒有g(shù)et到答案的樣子問：那jdk1.8的HashMap是不是就不會(huì)出現(xiàn)死循環(huán)了？
我當(dāng)時(shí)愣了一下谢床，心想難道1.8也會(huì)出現(xiàn)死循環(huán)…考慮一會(huì)兄一，最后決定堅(jiān)持自己，但是已經(jīng)沒有了底氣：是的识腿。
面試官露出了開心的樣子：嗯出革，好的。（看來(lái)肯定是說(shuō)錯(cuò)了）
…
…
…
介紹完前因后果渡讼，那么來(lái)看一下Hashmap在jdk1.8會(huì)不會(huì)出現(xiàn)死循環(huán)的情況骂束。
測(cè)試代碼
import java.util.*;
public class MainTest {
Map<String,String> map = new HashMap<>();
public void hashMapTest() {
for (int i = 0;i < 500;i++) {
new Thread(new Runnable() {
@Override
public void run() {
for (int j = 0;j < 500;j++) {
map.put(Thread.currentThread().getName() + "-" + j, j+"");
}
}
}).start();
}
try {
Thread.sleep(2000);
// map.forEach((x,y) -> System.out.println(x));
System.out.println(map.size());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
[圖片上傳失敗...(image-5e3108-1699429002669)]
發(fā)現(xiàn)cpu使用率99.9%，符合死循環(huán)的情況成箫。
然后再使用 jps 和 jstack 命令查看一下進(jìn)程的狀態(tài)
[圖片上傳失敗...(image-2d2df2-1699429002669)]
看一下HashMap的1948行
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//說(shuō)明線程在這個(gè)for循環(huán)中一直沒有返回展箱，導(dǎo)致了死循環(huán)
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
} // 1948行
}
}
moveRootToFront(tab, root);
}
這個(gè)方法看出，說(shuō)明Hashmap在jdk1.8的時(shí)候也會(huì)出現(xiàn)死循環(huán)的情況蹬昌，是在鏈表轉(zhuǎn)換為樹的時(shí)候for循環(huán)一直無(wú)法跳出析藕，導(dǎo)致死循環(huán)。
不止這些凳厢，經(jīng)過(guò)多次測(cè)試，發(fā)現(xiàn)死循環(huán)還會(huì)在2239行出現(xiàn)
java.lang.Thread.State: RUNNABLE
at java.util.HashMap$TreeNode.balanceInsertion(HashMap.java:2239)
at java.util.HashMap$TreeNode.treeify(HashMap.java:1945)
at java.util.HashMap$TreeNode.split(HashMap.java:2180)
at java.util.HashMap.resize(HashMap.java:714)
at java.util.HashMap.putVal(HashMap.java:663)
at java.util.HashMap.put(HashMap.java:612)
at com.luck.ejob.server.MainTest$1.run(MainTest.java:151)
at java.lang.Thread.run(Thread.java:748)
再看下面這種情況
java.lang.Thread.State: RUNNABLE
at java.util.HashMap$TreeNode.root(HashMap.java:1824)
at java.util.HashMap$TreeNode.putTreeVal(HashMap.java:1978)
at java.util.HashMap.putVal(HashMap.java:638)
at java.util.HashMap.put(HashMap.java:612)
at com.luck.ejob.server.MainTest$1.run(MainTest.java:151)
at java.lang.Thread.run(Thread.java:748)
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p; //1824行
}
}
所以jdk1.8的HashMap在多線程的情況下也會(huì)出現(xiàn)死循環(huán)的問題竞慢，但是1.8是在鏈表轉(zhuǎn)換樹或者對(duì)樹進(jìn)行操作的時(shí)候會(huì)出現(xiàn)線程安全的問題先紫。
復(fù)習(xí)一下線程安全的定義：
在擁有共享數(shù)據(jù)的多條線程并行執(zhí)行的程序中，線程安全的代碼會(huì)通過(guò)同步機(jī)制保證各個(gè)線程都可以正常且正確的執(zhí)行筹煮，不會(huì)出現(xiàn)數(shù)據(jù)污染等意外情況遮精。
HashMap在jdk1.8中也會(huì)死循環(huán)
jdk1.7版本中多線程同時(shí)對(duì)HashMap擴(kuò)容時(shí)，會(huì)引起鏈表死循環(huán)败潦，盡管jdk1.8修復(fù)了該問題本冲，但是同樣在jdk1.8版本中多線程操作hashMap時(shí)仍然會(huì)引起死循環(huán)，只是原因不一樣劫扒。
示例代碼
package com.gsonkeno.interview;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
/**
*
* jdk7擴(kuò)容時(shí)都可能導(dǎo)致死鎖
* jdk8在PutTreeValue時(shí)可能死循環(huán) 死循環(huán)在hashMap的1816行或2229行檬洞， java version "1.8.0_111"
* jstack發(fā)現(xiàn)可能卡在 at java.util.HashMap$TreeNode.balanceInsertion(HashMap.java:2229)
* 也有可能卡在 at java.util.HashMap$TreeNode.root(HashMap.java:1816)
* @author gaosong
* @since 2019-02-23
*/
public class HashMap1 {
public static void main(String[] args) {
HashMapThread hmt0 = new HashMapThread();
HashMapThread hmt1 = new HashMapThread();
HashMapThread hmt2 = new HashMapThread();
HashMapThread hmt3 = new HashMapThread();
HashMapThread hmt4 = new HashMapThread();
hmt0.start();
hmt1.start();
hmt2.start();
hmt3.start();
hmt4.start();
}
}
class HashMapThread extends Thread
{
private static AtomicInteger ai = new AtomicInteger(0);
private static Map<Integer, Integer> map = new HashMap<Integer, Integer>(1);
@Override
public void run()
{
while (ai.get() < 100000)
{
map.put(ai.get(), ai.get());
ai.incrementAndGet();
}
System.out.println(Thread.currentThread().getName() + "執(zhí)行結(jié)束完");
}
}
代碼見github
說(shuō)明
[圖片上傳失敗...(image-334c7d-1699429002669)]
多個(gè)線程全部全部在如下代碼塊的1816行，一直循環(huán)沟饥，無(wú)法退出for循環(huán)添怔。
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p; //1816行
}
}
類似地湾戳，還有可能卡在at java.util.HashMap$TreeNode.balanceInsertion(HashMap.java:2229)
可能Node節(jié)點(diǎn)轉(zhuǎn)換為TreeNode結(jié)點(diǎn)異常
主要原因其實(shí)是多線程下操作同一對(duì)象時(shí)，對(duì)象內(nèi)部屬性的不一致性導(dǎo)致的广料。分析方式跟為什么單例要使用雙重鎖check類似砾脑。
總結(jié)的經(jīng)驗(yàn)就是，在多線程下不要使用HashMap艾杏，至少jdk8及其以下不要使用韧衣，之上版本也建議不要使用。
JDK8中HashMap依然會(huì)死循環(huán)
JDK8中HashMap依然會(huì)死循環(huán)购桑！
是否你聽說(shuō)過(guò)JDK8之后HashMap已經(jīng)解決的擴(kuò)容死循環(huán)的問題畅铭，雖然HashMap依然說(shuō)線程不安全，但是不會(huì)造成服務(wù)器load飆升的問題其兴。
然而事實(shí)并非如此顶瞒。少年可曾了解一種紅黑樹成環(huán)的場(chǎng)景，=v=
今日在查看監(jiān)控時(shí)候發(fā)現(xiàn)元旬，某一臺(tái)機(jī)器load飆升
[圖片上傳失敗...(image-1e4e75-1699429002669)]
感覺問題不對(duì)勁榴徐，ssh大法登陸機(jī)器，top匀归，top -Hp,jstack坑资，jmap四連擊保存下來(lái)堆棧，cpu使用最高的線程穆端，內(nèi)存信息準(zhǔn)備分析袱贮。
首先查看使用最耗費(fèi)cpu的線程堆棧信息
cat stack | grep -i 34670 -C10 --color
[圖片上傳失敗...(image-e21a45-1699429002669)]
我勒個(gè)去，HashMap体啰，猜測(cè)八成死循環(huán)了攒巍，但是我們使用的JDK8，在8中通過(guò)棧封閉的鏈表替換荒勇，解決了擴(kuò)容死循環(huán)的問題柒莉。疑惑，繼續(xù)往下看沽翔。
根據(jù)堆棧信息兢孝，root方法是問題所在，點(diǎn)開HashMap源碼
[圖片上傳失敗...(image-6ae6eb-1699429002669)]
好嘛仅偎，load飆高跨蟹，代碼有個(gè)for語(yǔ)句，我覺得鐵定死循環(huán)了橘沥，看代碼情況只可能是兩個(gè)紅黑樹節(jié)點(diǎn)的父親節(jié)點(diǎn)相互引用才可以導(dǎo)致無(wú)法走出這個(gè)for語(yǔ)句窗轩。
然而這都是我的猜測(cè)，我沒有證據(jù)座咆。而且讓我追紅黑樹的代碼品姓，也是需要耗費(fèi)大量時(shí)間的事情寝并，我需要快速驗(yàn)證我的猜測(cè)。
我之前dump下來(lái)了堆內(nèi)存信息腹备，我通過(guò)jhat 命令生成html的內(nèi)存信息頁(yè)面
[圖片上傳失敗...(image-56d23d-1699429002668)]
然后輸入http://localhost:7000查看
我先找業(yè)務(wù)代碼中持有這個(gè)HashMap的對(duì)象衬潦，然后點(diǎn)進(jìn)去查詢內(nèi)部信息
[圖片上傳失敗...(image-d12c47-1699429002668)]
因?yàn)閿?shù)據(jù)都放在table中，點(diǎn)擊Table字段植酥，查看其內(nèi)容
[圖片上傳失敗...(image-604f65-1699429002668)]
table中存在唯一的一個(gè)TreeNode節(jié)點(diǎn)镀岛，這肯定是已經(jīng)變成了紅黑樹了
點(diǎn)進(jìn)去查看
[圖片上傳失敗...(image-54a851-1699429002668)]
點(diǎn)擊parent字段信息
[圖片上傳失敗...(image-b6c931-1699429002668)]
0x72745d828與0x72745d7b8兩個(gè)TreeNode節(jié)點(diǎn)的Parent引用都是對(duì)方。
后續(xù)打算深入研究一下紅黑樹什么場(chǎng)景會(huì)造成這個(gè)原因友驮。
最后漂羊，無(wú)論什么并發(fā)場(chǎng)景請(qǐng)別使用HashMap，ConcurrentHashmap大法好
