HashMap多线程下死循环的问题

参考文章

HashMap多线程下可能会产生死循环的问题。我们知道，当HashMap的容量不够的时候（0.75倍最大容量的时候）会进行数组扩容，然后把HashMap中的所有元素rehash一遍，放在各个位置中。

构造成死循环的几个前提条件：

1. 链表
2. 多线程下同时进行数组扩容
3. 数据在链表插入中发生时间片轮转

我们先看一下核心的扩容代码。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //遍历哈希表(也就是数组的每一个元素)
    for (Entry<K,V> e : table) {
        //遍历每个元素下的链表(hash冲突后的链表)
        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;
        }
    }
}

这里通过链表的插入来举例说明为什么会产生死循环。

原始链表：数组->A->B->C->NULL

线程一的新表：数组->B->A->NULL

线程二的新表：数组->A->NULL

当线程一在插入B的时候，首先先把B的next结点指向A，而这时候，时间片用完，线程二直接抢夺，他现在要插入B，所以当前的结点是B，而next结点注意了，他不再是最开始的C了，他已经被线程一修改成B的下一个指向为A了，所以next的指向为A，所以最后，B.next = A，线程二继续，next(A).next=B，那么此时，这里就会出现一个死循环了。

原始哈希表

线程一插入B结点插到一半或者插入完毕都行，关键是B结点的next被修改。现在，当前结点是B，next是C（因为在修改B的next之前已经记录了）

线程二开始插入B结点，首先先获取next结点，因为B的next结点被修改过了，所以获取的是A。

接着线程二继续插入next结点，首先第一步会把A结点的next指向B，所以，已经发生了死循环。

通过分析，其实这可能还会造成数据丢失的问题，你可以模拟插入A的时候，next指向null的时候，就已经被其他线程抢占，那么最后第二个线程只会最多插入A结点而已。