HashMap 死循环

程序员文章站 2022-03-23 22:46:50

在多线程环境中，使用HashMap进行put操作时会引起死循环，因为在HashMap本来就不支持多线程使用，要并发就用ConcurrentHashmap。会导致死循环是在jdk1.7中，由于扩容时的操作是使用头插法，在多线程的环境下可能产生循环链表，由此导致了死循环。在。jdk1.8中改为使用尾插法，避免了该死循环的情况，暂无此问题。在创建了新的数组之后调用transfer方法来完成元素的迁移操作，具体迁移逻辑如下：/*** Transfers all......

在多线程环境中，使用HashMap进行put操作时会引起死循环，因为在HashMap本来就不支持多线程使用，要并发就用ConcurrentHashMap。 HashMap扩容时会导致死循环是在JDK1.7中，由于扩容时的操作是使用头插法，在多线程的环境下可能产生循环链表，由此导致了死循环。在JDK1.8中改为使用尾插法，避免了该死循环的情况，暂无此问题。

源码分析：

在创建了新的数组之后调用transfer方法来完成元素的迁移操作，具体迁移逻辑如下：

   /**
      * 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);  //线程1等线程2执行结束后
                                                        //从此处开始执行
                                                        //此时e的key=3,e.next.key=7
                                                        //但是此时的e.next.next的key=3了
                                                        //（被线程2修改了）
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

假设HashMap初始化大小为4，插入个3节点，恰巧这3个节点都hash到同一个位置

HashMap 死循环

并发下的ReHash

在多线程环境下有线程一和线程二，同时对该map进行扩容执行扩容。

　　transfer代码中的这个细节：

do {
        Entry<K,V> next = e.next;   // 假设线程一执行到这里就被调度挂起了
                                    // 此时e=key(3)，next=key(7)
        int i = indexFor(e.hash,newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    } while(e != null);

HashMap 死循环