在多線程環(huán)境下，使用HashMap進(jìn)行put操作會(huì)引起死循環(huán)，導(dǎo)致CPU利用率接近100%，HashMap在并發(fā)執(zhí)行put操作時(shí)會(huì)引起死循環(huán)，是因?yàn)槎嗑€程會(huì)導(dǎo)致HashMap的Entry鏈表
形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，Entry的next節(jié)點(diǎn)永遠(yuǎn)不為空，在get操作時(shí)遍歷鏈表就會(huì)產(chǎn)生死循環(huán)。那么這個(gè)死循環(huán)是如何生成的呢？我們來(lái)具體分析下。
HashMap擴(kuò)容流程
引發(fā)死循環(huán)，是在HashMap的擴(kuò)容操作中，正常的擴(kuò)容操作是這個(gè)流程。HashMap的擴(kuò)容在put操作中會(huì)觸發(fā)擴(kuò)容，主要是三個(gè)方法：
綜合來(lái)說(shuō)，HashMap一次擴(kuò)容的過(guò)程：
1、取當(dāng)前table的2倍作為新table的大小
2、根據(jù)算出的新table的大小new出一個(gè)新的Entry數(shù)組來(lái)，名為newTable
3、輪詢?cè)璽able的每一個(gè)位置，將每個(gè)位置上連接的Entry，算出在新table上的位置，并以鏈表形式連接
4、原table上的所有Entry全部輪詢完畢之后，意味著原table上面的所有Entry已經(jīng)移到了新的table上，HashMap中的table指向newTable
案例分析
這里我們寫(xiě)個(gè)簡(jiǎn)單的demo模擬一下transfer方法中的邏輯
public class HashMap {
private transient Entry[] table;
public void test() {
Entry c = new Entry("c", null);
Entry b = new Entry("b", c);
Entry a = new Entry("a", b);
table = new Entry[4];
table[1] = a;
System.out.println("原始鏈表：" + a.toString());
Thread thread = new Thread(new Runnable() {
@Override
public void run() {
Entry[] newTable = new Entry[8];
for (Entry e : table) {
if (null != e) {
System.out.println("線程1讓出CPU時(shí)間片前,操作的entry為：" + e.toString());
}
while (null != e) {
Entry next = e.next;
//產(chǎn)生死循環(huán)主要在這里，第一次遍歷上述的next為 b->c->null,
// 下一次遍歷 b時(shí)，由于線程2修改成了 c->b->a->null導(dǎo)致 b 節(jié)點(diǎn)的next又重新指向 a節(jié)點(diǎn)
//線程1讓出CPU時(shí)間片,等線程二操作完
sleep(5000);
System.out.println("線程1繼續(xù)執(zhí)行,操作的entry為：" + e.toString());
e.next = newTable[1];
newTable[1] = e;
// System.out.println("執(zhí)行后的entry為："+e.toString());
System.out.println("=============================");
e = next;
}
}
table = newTable;
}
});
thread.start();
new Thread(new Runnable() {
@Override
public void run() {
Entry[] newTable = new Entry[8];
for (Entry e : table) {
if (null != e) {
System.out.println("線程2開(kāi)始,操作的entry為：" + e.toString());
}
while (null != e) {
sleep(500);
Entry next = e.next;
e.next = newTable[1];
newTable[1] = e;
e = next;
}
}
System.out.println("線程2擴(kuò)容完,entry為：" + newTable[1].toString());
sleep(6000);
table = newTable;
}
}).start();
sleep(20000);
System.out.println("2個(gè)線程擴(kuò)容完畢后,最終entry為：" + table[1].value + "->" + table[1].next.value + "->" + table[1].next.next.value);
}
private void sleep(long time) {
try {
Thread.sleep(time);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void transfer(Entry[] newTable) {
}
private int indexFor(int hash, int length) {
return hash & (length - 1);
}
///////////// HashMap節(jié)點(diǎn)移動(dòng)相關(guān)邏輯 //////////////////
// 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;
// }
// }
// }
static class Entry {
private String value;
private Entry next;
private int hash = 1;
public Entry(String value, Entry next) {
this.value = value;
this.next = next;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Entry getNext() {
return next;
}
public void setNext(Entry next) {
this.next = next;
}
@Override
public String toString() {
if (null != value) {
return value + "->" + (null == next ? null : next.toString());
}
return null;
}
}
}
調(diào)用上述test方法，輸出結(jié)果為
我們看到最終的一個(gè)結(jié)果是a->b->a的一個(gè)循環(huán)鏈表，其中節(jié)點(diǎn)c也丟失了。由此能看到hashmap線程不安全不僅體現(xiàn)在循環(huán)鏈表，還有可能數(shù)據(jù)丟失。
debug調(diào)試如下圖
總結(jié)
在并發(fā)的情況，發(fā)生擴(kuò)容時(shí)，可能會(huì)產(chǎn)生循環(huán)鏈表，在執(zhí)行g(shù)et的時(shí)候，會(huì)觸發(fā)死循環(huán)，引起CPU的100%問(wèn)題，所以一定要避免在并發(fā)環(huán)境下使用HashMap。
