占小狼 轉載請注明原創(chuàng)出處旺韭，謝謝氛谜！
問題
最近的幾次面試中，我都問了是否了解HashMap在并發(fā)使用時可能發(fā)生死循環(huán)区端，導致cpu100%值漫，結果讓我很意外，都表示不知道有這樣的問題织盼，讓我意外的是面試者的工作年限都不短杨何。
由于HashMap并非是線程安全的，所以在高并發(fā)的情況下必然會出現(xiàn)問題沥邻，這是一個普遍的問題危虱，雖然網上分析的文章很多，還是覺得有必須寫一篇文章谋国，讓關注我公眾號的同學能夠意識到這個問題槽地，并了解這個死循環(huán)是如何產生的。
如果是在單線程下使用HashMap芦瘾，自然是沒有問題的，如果后期由于代碼優(yōu)化集畅，這段邏輯引入了多線程并發(fā)執(zhí)行近弟，在一個未知的時間點，會發(fā)現(xiàn)CPU占用100%挺智，居高不下祷愉，通過查看堆棧，你會驚訝的發(fā)現(xiàn)，線程都Hang在hashMap的get()方法上二鳄，服務重啟之后赴涵，問題消失，過段時間可能又復現(xiàn)了订讼。
這是為什么髓窜？
原因分析
在了解來龍去脈之前，我們先看看HashMap的數(shù)據結構欺殿。
在內部寄纵，HashMap使用一個Entry數(shù)組保存key、value數(shù)據脖苏，當一對key程拭、value被加入時，會通過一個hash算法得到數(shù)組的下標index棍潘，算法很簡單恃鞋，根據key的hash值，對數(shù)組的大小取模 hash & (length-1)亦歉，并把結果插入數(shù)組該位置山宾，如果該位置上已經有元素了，就說明存在hash沖突鳍徽，這樣會在index位置生成鏈表资锰。
如果存在hash沖突，最慘的情況阶祭，就是所有元素都定位到同一個位置绷杜，形成一個長長的鏈表，這樣get一個值時濒募，最壞情況需要遍歷所有節(jié)點鞭盟，性能變成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要瑰剃。
當插入一個新的節(jié)點時齿诉，如果不存在相同的key，則會判斷當前內部元素是否已經達到閾值（默認是數(shù)組大小的0.75）晌姚，如果已經達到閾值粤剧，會對數(shù)組進行擴容，也會對鏈表中的元素進行rehash挥唠。
實現(xiàn)
HashMap的put方法實現(xiàn)：
1抵恋、判斷key是否已經存在
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
// 如果key已經存在，則替換value宝磨，并返回舊值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// key不存在弧关，則插入新的元素
addEntry(hash, key, value, i);
return null;
}
2盅安、檢查容量是否達到閾值threshold
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
如果元素個數(shù)已經達到閾值，則擴容世囊，并把原來的元素移動過去别瞭。
3、擴容實現(xiàn)
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
...
Entry[] newTable = new Entry[newCapacity];
...
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
這里會新建一個更大的數(shù)組株憾，并通過transfer方法蝙寨，移動元素。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
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;
}
}
}
移動的邏輯也很清晰号胚，遍歷原來table中每個位置的鏈表籽慢，并對每個元素進行重新hash，在新的newTable找到歸宿猫胁，并插入箱亿。
案例分析
假設HashMap初始化大小為4，插入個3節(jié)點弃秆，不巧的是届惋，這3個節(jié)點都hash到同一個位置，如果按照默認的負載因子的話菠赚，插入第3個節(jié)點就會擴容脑豹，為了驗證效果，假設負載因子是1.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
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;
}
}
}
以上是節(jié)點移動的相關邏輯衡查。
插入第4個節(jié)點時瘩欺，發(fā)生rehash，假設現(xiàn)在有兩個線程同時進行拌牲，線程1和線程2俱饿，兩個線程都會新建新的數(shù)組。
假設 線程2 在執(zhí)行到Entry<K,V> next = e.next;之后塌忽，cpu時間片用完了拍埠，這時變量e指向節(jié)點a，變量next指向節(jié)點b土居。
線程1繼續(xù)執(zhí)行枣购，很不巧，a擦耀、b棉圈、c節(jié)點rehash之后又是在同一個位置7，開始移動節(jié)點
第一步埂奈，移動節(jié)點a
第二步迄损，移動節(jié)點b
注意惰瓜，這里的順序是反過來的妈经，繼續(xù)移動節(jié)點c
這個時候 線程1 的時間片用完，內部的table還沒有設置成新的newTable肩榕， 線程2 開始執(zhí)行垮抗，這時內部的引用關系如下：
這時氏捞，在 線程2 中，變量e指向節(jié)點a冒版，變量next指向節(jié)點b液茎，開始執(zhí)行循環(huán)體的剩余邏輯。
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
執(zhí)行之后的引用關系如下圖
執(zhí)行后辞嗡，變量e指向節(jié)點b捆等，因為e不是null，則繼續(xù)執(zhí)行循環(huán)體续室，執(zhí)行后的引用關系
變量e又重新指回節(jié)點a栋烤，只能繼續(xù)執(zhí)行循環(huán)體，這里仔細分析下：
1挺狰、執(zhí)行完Entry<K,V> next = e.next;明郭，目前節(jié)點a沒有next，所以變量next指向null丰泊；
2薯定、e.next = newTable[i]; 其中 newTable[i] 指向節(jié)點b，那就是把a的next指向了節(jié)點b瞳购，這樣a和b就相互引用了话侄，形成了一個環(huán)；
3学赛、newTable[i] = e 把節(jié)點a放到了數(shù)組i位置年堆；
4、e = next; 把變量e賦值為null罢屈，因為第一步中變量next就是指向null嘀韧；
所以最終的引用關系是這樣的：
節(jié)點a和b互相引用，形成了一個環(huán)缠捌，當在數(shù)組該位置get尋找對應的key時锄贷，就發(fā)生了死循環(huán)。
另外曼月，如果線程2把newTable設置成到內部的table谊却，節(jié)點c的數(shù)據就丟了，看來還有數(shù)據遺失的問題哑芹。
總結
所以在并發(fā)的情況炎辨，發(fā)生擴容時，可能會產生循環(huán)鏈表聪姿，在執(zhí)行get的時候碴萧，會觸發(fā)死循環(huán)乙嘀，引起CPU的100%問題，所以一定要避免在并發(fā)環(huán)境下使用HashMap破喻。
曾經有人把這個問題報給了Sun虎谢，不過Sun不認為這是一個bug，因為在HashMap本來就不支持多線程使用曹质，要并發(fā)就用ConcurrentHashmap婴噩。
END。
我是占小狼羽德。 如果讀完覺得有收獲的話几莽，記得關注和點贊
