HashMap 源码解析-番外（为何1.7hash会死循环）

之前说过hashmap在jdk1.7的时候会造成链表头插法导致的死循环，那么是怎么造成的呢？本文会详细解释。

扩容的核心源码如下：

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
              //1， 获取旧表的下一个元素
                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;
            }
        }
    }

1、假设旧表的初始长度为2，此时已经在下标为1的位置存放了两个元素，再put第三个元素的时候考虑需要扩容；

2, 此刻有两个线程A,B都进行put操作，线程A先扩容，执行到代码Entry<K,V> next = e.next;执行完这段代码，线程A挂起；

然后线程B开始执行transfer函数中的while循环，会把原来的table变成一个table（线程B自己的栈中），再写入到内存中。

注意，因为线程A的e指向了key(3), next指向了key(7), 其在线程B rehash后，指向了线程B重组后的链表。我们可以看到链表的顺序被反转了。

3, 线程A被唤醒，继续执行：

先是执行newTable[i] = e ;

然后是e = next , 导致了e指向了key(7);

而下一次循环的next = e.next 导致next指向了key(3)

如下图：

4， 当前循环：

e.next = newTable[i[];

newTable[i] = e ;

e = next;

将key(7)摘下来采用头插法，放到newTable[i]的第一个元素中，下一个结点指向key(3)

下一次循环：

next = e.next; 此时e为key(3)

此时next = null; 不会在往下循环了。

5，此时key(3)采用头插法又放到newTable[i]的位置，导致key(3)指向key(7)，注意此时key(7).next已经指向了key(3)，所以环形链表就出现了。如下图：

于是当我们的线程A调用get()方法时，如果下标映射到3处，则会出现死循环。

总结：

线程A先执行，执行完Entry<K,V> next = e.next;这行代码后挂起，然后线程B完整的执行完整个扩容流程，接着线程A唤醒，继续之前的往下执行，当while循环执行3次后会形成环形链表。