問題引出
前一篇文章講解了HashMap的實作原理，講到了HashMap不是線程安全的。那麼HashMap在多線程環境下又會有什麼問題呢？
幾個月前，公司項目的一個子產品線上上運作的時候出現了死循環，死循環的代碼就卡在HashMap的get方法上。盡管最終發現不是因為HashMap導緻的，但卻讓我重視了HashMap在多線程環境下會引發死循環的這個問題，下面先用一段代碼簡單模拟出HashMap的死循環：
public class HashMapThread extends Thread
{
private static AtomicInteger ai = new AtomicInteger(0);
private static Map<Integer, Integer> map = new HashMap<Integer, Integer>(1);
public void run()
{
while (ai.get() < 100000)
{
map.put(ai.get(), ai.get());
ai.incrementAndGet();
}
}
} 這個線程的作用很簡單，給AtomicInteger不斷自增并寫入HashMap中，其中AtomicInteger和HashMap都是全局共享的，也就是說所有線程操作的都是同一個AtomicInteger和HashMap。開5個線程操作一下run方法中的代碼：
public static void main(String[] args)
{
HashMapThread hmt0 = new HashMapThread();
HashMapThread hmt1 = new HashMapThread();
HashMapThread hmt2 = new HashMapThread();
HashMapThread hmt3 = new HashMapThread();
HashMapThread hmt4 = new HashMapThread();
hmt0.start();
hmt1.start();
hmt2.start();
hmt3.start();
hmt4.start();
} 多運作幾次之後死循環就出來了，我大概運作了7次、8次的樣子，其中有幾次是數組下标越界異常ArrayIndexOutOfBoundsException。這裡面要提一點，多線程環境下代碼會出現問題并不意味着多線程環境下一定會出現問題，但是隻要出現了問題，或者是死鎖、或者是死循環，那麼你的項目除了重新開機就沒有什麼别的辦法了，是以代碼的線程安全性在開發、評審的時候必須要重點考慮到。OK，看一下控制台：
紅色方框一直亮着，說明代碼死循環了。死循環問題的定位一般都是通過jps+jstack檢視堆棧資訊來定位的：
看到Thread-0處于RUNNABLE，而從堆棧資訊上應該可以看出，這次的死循環是由于Thread-0對HashMap進行擴容而引起的。
是以，本文就解讀一下，HashMap的擴容為什麼會引起死循環。
正常的擴容過程
先來看一下HashMap一次正常的擴容過程。簡單一點看吧，假設我有三個經過了最終rehash得到的數字，分别是5 7 3，HashMap的table也隻有2，那麼HashMap把這三個數字put進資料結構了之後應該是這麼一個樣子的：
這應該很好了解。然後看一下resize的代碼，上面的堆棧裡面就有：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
} 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);
} 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);
}
}
} 我總結一下這三段代碼，HashMap一次擴容的過程應該是：
- 取目前table的2倍作為新table的大小
- 根據算出的新table的大小new出一個新的Entry數組來，名為newTable
- 輪詢原table的每一個位置，将每個位置上連接配接的Entry，算出在新table上的位置，并以連結清單形式連接配接
- 原table上的所有Entry全部輪詢完畢之後，意味着原table上面的所有Entry已經移到了新的table上，HashMap中的table指向newTable
這樣就完成了一次擴容，用圖表示是這樣的：
HashMap的一次正常擴容就是這樣的，這很好了解。
擴容導緻的死循環
既然是擴容導緻的死循環，那麼繼續看擴容的代碼：
1 void transfer(Entry[] newTable) {
2 Entry[] src = table;
3 int newCapacity = newTable.length;
4 for (int j = 0; j < src.length; j++) {
5 Entry<K,V> e = src[j];
6 if (e != null) {
7 src[j] = null;
8 do {
9 Entry<K,V> next = e.next;
10 int i = indexFor(e.hash, newCapacity);
11 e.next = newTable[i];
12 newTable[i] = e;
13 e = next;
14 } while (e != null);
15 }
16 }
17 } 兩個線程，線程A和線程B。假設第9行執行完畢，線程A切換，那麼對于線程A而言，是這樣的：
CPU切換到線程B運作，線程B将整個擴容過程全部執行完畢，于是就形成了：
此時CPU切換到線程A上，執行第8行~第14行的do...while...循環，首先放置3這個Entry：
我們必須要知道，由于線程B已經執行完畢，是以根據Java記憶體模型（JMM），現在table裡面所有的Entry都是最新的，也就是7的next是3，3的next是null。3放置到table[3]的位置上了，下面的步驟是：
- e=next，即e=7
- 判斷e不等于null，循環繼續
- next=e.next，即next=7的next，也就是3
- 放置7這個Entry
是以，用圖表示就是：
放置完7之後，繼續運作代碼：
- e=next，也就是說e=3
- next=e.next，即3的next，也就是null
- 放置3這個Entry
把3移到table[3]上去，死循環就出來了：
3移到table[3]上去了，3的next指向7，由于原先7的next指向3，這樣就成了一個死循環。
此時執行13行的e=next，那麼e=null，循環終止。盡管此次循環确實結束了，但是後面的操作，隻要涉及輪詢HashMap資料結構的，無論是疊代還是擴容，都将在table[3]這個連結清單處出現死循環。這也就是前面的死循環堆棧出現的原因，transfer的484行，因為這是一次擴容操作，需要周遊HashMap資料結構，transfer方法是擴容的最後一個方法。
3 5 7又會有怎樣的結果
可能有人覺得上面的數字5 7 3太巧了，像是專門為了産生HashMap的死循環而故意選擇的數字。
這個問題，我這麼回答：我記得在《從Paxos到Zookeeper分布式一緻性原理與實踐》有一段話大概是這麼描述的，有一個被反複實踐得出的結論是，任何在多線程下可能發生的錯誤場景最終一定會發生。
5 7 3這個數字可不巧，擴容前相鄰兩個Entry被配置設定到擴容後同樣的table位置是很正常的。關鍵的是，即使這種異常場景發生的可能性再低，隻要發生一次，那麼你的系統就部分甚至全部不可用了----除了重新開機系統沒有任何辦法。是以，這種可能會發生的異常場景必須提前扼殺。
OK，不扯了，前面講了5 7 3導緻了死循環，現在看一下正常的順序3 5 7，會發生什麼問題。簡單看一下，就不像上面講得這麼詳細了：
這是擴容前資料結構中的内容，擴容之後正常的應該是：
現在在多線程下遇到問題了，某個線程先放7：
再接着放5：
由于5的next此時為null，是以擴容操作結束，3 5 7造成的結果就是元素丢失。
如何解決
把一個線程非安全的集合作為全局共享的，本身就是一種錯誤的做法，并發下一定會産生錯誤。
是以，解決這個問題的辦法很簡單，有兩種：
1、使用Collections.synchronizedMap(Mao<K,V> m)方法把HashMap變成一個線程安全的Map
2、使用Hashtable、ConcurrentHashMap這兩個線程安全的Map
不過，既然選擇了線程安全的辦法，那麼必然要在性能上付出一定的代價----畢竟這個世界上沒有十全十美的事情，既要運作效率高、又要線程安全。
==================================================================================
我不能保證寫的每個地方都是對的，但是至少能保證不複制、不黏貼，保證每一句話、每一行代碼都經過了認真的推敲、仔細的斟酌。每一篇文章的背後，希望都能看到自己對于技術、對于生活的态度。
我相信喬布斯說的，隻有那些瘋狂到認為自己可以改變世界的人才能真正地改變世界。面對壓力，我可以挑燈夜戰、不眠不休；面對困難，我願意迎難而上、永不退縮。
其實我想說的是，我隻是一個程式員，這就是我現在純粹人生的全部。