转载至：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也会出现死循环的问题（实测）
昨天在面试的时候，面试官问到HashMap在多线程并发的情况下怎么出现死循环的？
我当时非常有底气的回答：Hashmap在jdk1.8之前多线程同时进行put操作，并且同时进行扩容的时候可能会出现链表环，导致死循环的发生。
面试官紧接着问：那1.8就不会出现死循环了吗？
底气瞬间消失，思考一会：1.8在多线程的情况下HashMap会出现数据丢失的问题，比如…（给面试官举了个栗子）。
面试官毫无波澜，好像没有get到答案的样子问：那jdk1.8的HashMap是不是就不会出现死循环了？
我当时愣了一下，心想难道1.8也会出现死循环…考虑一会，最后决定坚持自己，但是已经没有了底气：是的。
面试官露出了开心的样子：嗯，好的。（看来肯定是说错了）
…
…
…
介绍完前因后果，那么来看一下Hashmap在jdk1.8会不会出现死循环的情况。
测试代码
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)]
发现cpu使用率99.9%，符合死循环的情况。
然后再使用 jps 和 jstack 命令查看一下进程的状态
[图片上传失败...(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;
//说明线程在这个for循环中一直没有返回，导致了死循环
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);
}
这个方法看出，说明Hashmap在jdk1.8的时候也会出现死循环的情况，是在链表转换为树的时候for循环一直无法跳出，导致死循环。
不止这些，经过多次测试，发现死循环还会在2239行出现
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在多线程的情况下也会出现死循环的问题，但是1.8是在链表转换树或者对树进行操作的时候会出现线程安全的问题。
复习一下线程安全的定义：
在拥有共享数据的多条线程并行执行的程序中，线程安全的代码会通过同步机制保证各个线程都可以正常且正确的执行，不会出现数据污染等意外情况。
HashMap在jdk1.8中也会死循环
jdk1.7版本中多线程同时对HashMap扩容时，会引起链表死循环，尽管jdk1.8修复了该问题，但是同样在jdk1.8版本中多线程操作hashMap时仍然会引起死循环，只是原因不一样。
示例代码
package com.gsonkeno.interview;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
/**
*
* jdk7扩容时都可能导致死锁
* jdk8在PutTreeValue时可能死循环 死循环在hashMap的1816行或2229行， java version "1.8.0_111"
* jstack发现可能卡在 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() + "执行结束完");
}
}
代码见github
说明
[图片上传失败...(image-334c7d-1699429002669)]
多个线程全部全部在如下代码块的1816行，一直循环，无法退出for循环。
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节点转换为TreeNode结点异常
主要原因其实是多线程下操作同一对象时，对象内部属性的不一致性导致的。分析方式跟为什么单例要使用双重锁check类似。
总结的经验就是，在多线程下不要使用HashMap，至少jdk8及其以下不要使用，之上版本也建议不要使用。
JDK8中HashMap依然会死循环
JDK8中HashMap依然会死循环！
是否你听说过JDK8之后HashMap已经解决的扩容死循环的问题，虽然HashMap依然说线程不安全，但是不会造成服务器load飙升的问题。
然而事实并非如此。少年可曾了解一种红黑树成环的场景，=v=
今日在查看监控时候发现，某一台机器load飙升
[图片上传失败...(image-1e4e75-1699429002669)]
感觉问题不对劲，ssh大法登陆机器，top，top -Hp,jstack，jmap四连击保存下来堆栈，cpu使用最高的线程，内存信息准备分析。
首先查看使用最耗费cpu的线程堆栈信息
cat stack | grep -i 34670 -C10 --color
[图片上传失败...(image-e21a45-1699429002669)]
我勒个去，HashMap，猜测八成死循环了，但是我们使用的JDK8，在8中通过栈封闭的链表替换，解决了扩容死循环的问题。疑惑，继续往下看。
根据堆栈信息，root方法是问题所在，点开HashMap源码
[图片上传失败...(image-6ae6eb-1699429002669)]
好嘛，load飙高，代码有个for语句，我觉得铁定死循环了，看代码情况只可能是两个红黑树节点的父亲节点相互引用才可以导致无法走出这个for语句。
然而这都是我的猜测，我没有证据。而且让我追红黑树的代码，也是需要耗费大量时间的事情，我需要快速验证我的猜测。
我之前dump下来了堆内存信息，我通过jhat 命令生成html的内存信息页面
[图片上传失败...(image-56d23d-1699429002668)]
然后输入http://localhost:7000查看
我先找业务代码中持有这个HashMap的对象，然后点进去查询内部信息
[图片上传失败...(image-d12c47-1699429002668)]
因为数据都放在table中，点击Table字段，查看其内容
[图片上传失败...(image-604f65-1699429002668)]
table中存在唯一的一个TreeNode节点，这肯定是已经变成了红黑树了
点进去查看
[图片上传失败...(image-54a851-1699429002668)]
点击parent字段信息
[图片上传失败...(image-b6c931-1699429002668)]
0x72745d828与0x72745d7b8两个TreeNode节点的Parent引用都是对方。
后续打算深入研究一下红黑树什么场景会造成这个原因。
最后，无论什么并发场景请别使用HashMap，ConcurrentHashmap大法好
