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();
        }
    }
}


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

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);
        }

这个方法看出，说明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)


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)

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

说明

在这里插入图片描述

多个线程全部全部在如下代码块的1816行，一直循环，无法退出for循环。

        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;   //1816行
            }
        }