HashMap在jdk1.8也会出现死循环的问题（实测）_hashmap1.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();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

如果执行之后发现，程序正常执行结束，那就再多执行几次，总有那么一次会出现问题，或者增加线程数量试试。当出现程序一直没有结束，来查看一下我们的cpu使用情况

发现cpu使用率99.9%，符合死循环的情况。
然后再使用 jps 和 jstack 命令查看一下进程的状态

看一下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);
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

这个方法看出，说明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)
1
2
3
4
5
6
7
8
9

balanceInsertion这个方法是对树进行一个重新的平衡。
再看下面这种情况

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)
1
2
3
4
5
6
7

final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p; //1824行
    }
}
1
2
3
4
5
6
7

所以jdk1.8的HashMap在多线程的情况下也会出现死循环的问题，但是1.8是在链表转换树或者对树进行操作的时候会出现线程安全的问题。

复习一下线程安全的定义：

在拥有共享数据的多条线程并行执行的程序中，线程安全的代码会通过同步机制保证各个线程都可以正常且正确的执行，不会出现数据污染等意外情况。