HashMap在并发情况下为什么造成死循环？

这个问题是在面试时常问的几个问题，一般在问这个问题之前会问Hashmap和HashTable的区别？面试者一般会回答：hashtable是线程安全的，hashmap是线程不安全的。

那么面试官就会紧接着问道，为什么hashmap不是线程安全的，会造成什么问题么？于是面试者就回答：HashMap在并发情况下的put操作会造成死循环。

这时候就会被面试官问：HashMap在并发为什么造成死循环？

很多面试者这时候就会一脸懵。没有过相关经验和深入的理解源码是很难回答这个问题的。

下面我们就通过HahMap源码来验证下，多线程并发put操作为何会生成环形链表，产生死循环。

这是HashMap扩容的源码

/**
 * Transfers all entries from current table to newTable. 
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {

        while(null != e) {
            //（关键代码）
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        } // while  

    }
}

开始之前先回顾一下HashMap的扩容机制：

HashMap默认设定的装载因子为0.75（可改），HashMap的大小为length，已经装载的元素数量为num，当（ num / length ）> 装载因子时，

开始扩容

先创建一个散列表HashMap：Map<Integer> map = new HashMap<Integer>(2);，装载因子默认0.75，当插入第二个元素时，会发生扩容

我们先在map中放入6、8两个元素。

插入后的状态

这时有两个线程都执行put操作，那么在此刻两个线程都对HashMap进行扩容，这时候就注意在上文的源码里注释为（关键代码）这一行：Entry<K,V> next = e.next;

假如两个线程分别为A、B两个线程。A线程在执行到关键代码这一行线程就被挂起，那么此刻A线程中：e = 6; next = 8;

接着B线程开始进行扩容，假设新的散列表中，节点6 和 节点8 还是会产生散列冲突，那么线程B的扩容过程为：

• 先申请一个空间为旧散列表两倍大的空间

<img src="https://upload-images.jianshu.io/upload_images/2710833-091c030487692445.png" alt="申请两倍大小的空间" style="zoom:33%;" />

• 将节点6 迁移至新散列表

节点6迁移至新散列表

• 将节点8 迁移至新散列表

将节点8 迁移至新散列表

此时线程B的扩容已经完成，节点8 的后继节点为节点6 ，节点6的后继节点为null。

我们将新旧两个散列表做个对比：

对比

回顾一下线程A的当前状态：e = 6; next = 8;，处于挂起状态。接着A线程取消挂起状态，接着执行（关键代码）之后的代码：将e = 6;节点迁移至新的散列表，并将next = 8的节点赋值给e。扩容并迁移节点6后的状态，如下图所示：

A线程扩容迁移节点6

于是第二次执行while循环时，当前待处理节点：e = 8;

在执行（关键代码）这一行时，由于线程B在扩容时将节点8的后继节点变为节点6，所以next不是为null，而是next = 6;

接着开始执行第三次while循环，由于节点6的后继节点为null，所以 next = null;，执行完第三次while循环的结果为：

循环结束。

可以看到扩容后的散列表中链表成环，如果这时候执行get()方法查询，就会导致死循环。

总结

HashMap的方法不是线程安全的。HashMap在并发执行put操作时发生扩容，可能会导致节点丢失，产生环形链表等情况。

• 节点丢失，会导致数据不准
• 生成环形链表，会导致get()方法死循环。

知识拓展

在jdk1.7中，由于扩容时使用头插法，在并发时可能会形成环状列表，导致死循环，在jdk1.8中改为尾插法，可以避免这种问题，但是依然避免不了节点丢失的问题。

建议

HashMap的设计初衷就不是在并发情况下使用，如果有并发的场景，推荐使用ConcurrentHashMap