并發場景下HashMap.get導緻cpu耗光

最近公司同僚消息隊列出現此種情況，以下分析

一、并發場景下HashMap.get導緻cpu耗光

Java中HashMap.get導緻cpu耗光bug，是由于HashMap.get裡面的for循環出現了無限循環，出現死循環是因為map中的桶連結清單出現了循環連結清單，循環連結清單是因為并發put操作造成的，同時進行了resize()；如果隻有一個線程進行put操作，是不會出現循環連結清單，是以讀寫并發不會出現死循環，隻有寫寫并發才有可能出現死循環。

void transfer(Entry[] newTable) {

Entry[] src = table;

    int newCapacity = newTable.length;

    for (int j = 0; j < src.length; j++) {

     Entry<K,V> e = src[j];

        if (e != null) {

            src[j] = null;

            do {

                Entry<K,V> next = e.next;

                int i = indexFor(e.hash, newCapacity);

                e.next = newTable[i];

                newTable[i] = e;

             e = next;

         } while (e != null);

      }

}

}

假設一個初始容量大小為2的HashMap（大多數人應該知道HashMap是采用數組的方式來存儲key，value對象，基于對key的hashcode的hash來決定存儲到數組的位置，沖突的情況下采用開放連結清單的方式來解決），目前裡面有兩個Entry，假設其存儲在數組的同一位置，存儲結構類似如下：

Entry[0] = A(.next) –> B(.next) –> null

假設同時有兩個線程調用了put，同時觸發resize。

第二個線程目前執行到Entry next = e.next這一行，此時其擷取到的e為A，next為B。

第一個線程已執行完transfer動作，但還沒執行完resize的剩餘動作，如A和B在容量擴大為4時hash到的位置仍然相同，那麼此時transfer中的newTable的結構變成：

Entry[0] = B(.next) –> A(.next) –> null

此時第二個線程繼續執行，進入這段代碼：

do {

    // 此時e為A，e.next為B，此行相當于next = B;

    Entry<K,V> next = e.next;  

    // 假設i=0

    int i = indexFor(e.hash, newCapacity); 

    // newTable[0]為null，此行相當于A.next = null;

    e.next = newTable[i]; 

    // 此行相當于newTable[0] = A;

    newTable[i] = e; 

    // 此行相當于e = B;

    e = next;

} while (e != null);

此時newTable的結構為：

Entry[0] = A(.next) –> null

e不為null，繼續執行：

do {

    // 此時e為B，e.next為A（第一個線程修改的），此行相當于next = A;

    Entry<K,V> next = e.next;  

    // 假設i = 0

    int i = indexFor(e.hash, newCapacity); 

    // newTable[0]為A，此行相當于B.next = A;

    e.next = newTable[i]; 

    // 此行相當于newTable[0] = B;

    newTable[i] = e; 

    // 此行相當于e = A;

    e = next;

} while (e != null);

此時newTable的結構為：

Entry[0] = B(.next) –> A(.next) –> null

e不為null，繼續執行：

do {

    // 此時e為A，A.next為null，此行相當于next = null

    Entry<K,V> next = e.next;  

    // 假設i = 0

    int i = indexFor(e.hash, newCapacity); 

    // newTable[0]為B，此行相當于A.next = B;

    e.next = newTable[i]; 

    // 此行相當于newTable[0] = A;

    newTable[i] = e; 

    // 此行相當于e = null;

    e = next;

} while (e != null);

此時newTable的結構為：

Entry[0] = A(.next) <--> B(.next)

無限循環就此造成，此時如果有線程要執行HashMap.get(A) ，就會直接進入無限循環，耗光CPU。

從上面的分析可以看出，要導緻HashMap.get出現無限循環，還真有些不容易，至少要有兩個線程在同時進行put，同時觸發resize，并且之前一個桶裡的兩個相鄰的對象在容量變了後仍然hash到了同樣的數組位置中，這樣才有可能導緻問題，是以這現象隻偶爾出現（不過我們以前曾經悲催的出現過一個叢集重新開機，全部碰到了Velocity的那個錯誤使用HashMap的bug，導緻嚴重故障）

并發那點事

1、list線程安全類CopyOnWriteArrayList

java.util.concurrent.CopyOnWriteArrayList<E>

Add/Set

public boolean add(E e) {

final ReentrantLock lock = this.lock;

lock.lock();

try {

    Object[] elements = getArray();//擷取目前數組

    int len = elements.length;

    Object[] newElements = Arrays.copyOf(elements, len + 1);//數組拷貝

    newElements[len] = e;

    setArray(newElements);

    return true;

} finally {

    lock.unlock();

}

}

周遊

public Iterator<E> iterator() {

//傳回一個new對象,類内部參數數組為目前數組,即如果目前list數組出現新增、删除

而周遊時不會出現同步異常，但會有髒資料出現 ex: CopyOnWriteArrayListTest

return new COWIterator<E>(getArray(), 0);

}