HashMap在并发环境下的死循环分析[copy]

今天在看《分布式java应用》这本书的时候看到作者提到HashMap在多线程并发的环境下有可能出现死循环，导致cpu100%的现象，看了下源码结合网上的分析说明下这种可能性。可能出现问题的地方是在扩容的时候

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

 

这个方法本身没有问题，问题出在transfer(newTable);这个方法是用来移动oldTable里的数据到newTable里。

/**
    * Transfers all entries from current table to newTable.
    */
   void transfer(Entry[] newTable) {
       Entry[] src = table;
       int newCapacity = newTable.length;
       for (int j = 0; j < src.length; j++) {
        //(1)
           Entry<K,V> e = src[j];
           if (e != null) {
               src[j] = null;
               do {
                //(2)
                   Entry<K,V> next = e.next;
                   int i = indexFor(e.hash, newCapacity);
                //(3)
                   e.next = newTable[i];
                   newTable[i] = e;
                   e = next;
               } while (e != null);
           }
       }
   }

 

下面分析可能出现的情况，假设原来table里存放的entry链表顺序是：

oldTable[i]:a1,a2,null

线程P1运行到(1)下面这行时，e=a1(a1.next=a2),执行到(2)下面时：next=e.next=a2。这个时候切换到线程P2，线程P2执行完这个链表的循环,如果刚好a1和a2在newTable里的i值相同（int i = indexFor(e.hash, newCapacity);），那么此时的链表顺序是：

newTable[i]:a2(next=a1),a1,null

现在cpu重新切回P1，在（3）这行：e.next = newTable[i];即：a1.next=newTable[i]=a2;

然后：newTable[i]=e=a1;e = next=a2;可以看到这个时候a1.next=a2,a2.next=a1,形成回环了，这样就造成了死循环.下面是针对各个线程各变量的情况

init(初始值):a1.next=a2,a2.next=null
 P1:e=a1,next=e.next=a2; waiting
 P2:a2.next=a1,a1.next=null ;notify
 P1:e.next=a1.next=newTable[i]=a2; newTable[i]=a1,e=next=a2
 end:a1.next=a2;a2.next=a1(P2结束后产生的结果)

可以看到很偶然的情况下会出现死循环，不过一旦出现后果是非常严重的，多线程的环境还是应该用ConcurrentHashMap。