并行操作HashMap可能會丟失數(shù)據(jù)并發(fā)生死循環(huán)。
由于HashMap重新散列的過程會轉(zhuǎn)置列表簸喂，由于不同線程轉(zhuǎn)置進度不一致毙死，慢線程會將快線程的轉(zhuǎn)置結(jié)果切斷并反方向連接形成閉環(huán)。
一喻鳄、簡述
設(shè)一哈希表map扼倘，散列表table長度為1，表示為：
map = [ {} ]
table[0]= {}
散列三個元素a除呵、b再菊、c，假設(shè)剛好全部散列在table[0]颜曾，表示為
map = [ { a -> b -> c -> NUL } ]
table[0] = { a -> b -> c -> NUL }
主線程啟動兩個線程纠拔，線程1，線程2泛豪，分別向map插入數(shù)據(jù)稠诲，又假設(shè)剛好散列在table[0]。
假設(shè)閥值為3诡曙，此時需要調(diào)整table長度避免數(shù)據(jù)扎堆吕粹，很不幸，a岗仑、b匹耕、c又剛好散列在同一位置newTable[i]。
新建一個散列表newTable荠雕，將table的元素往newTable挪稳其。
JDK的源碼：
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, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 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;
}
}
}
二驶赏、簡析
2.1 對于線程1：
遍歷table[0]，重新散列既鞠。
newTable[i]={}
table[0] = { a -> b -> c -> NUL }
LOOP1：
Entry<K,V> next = e.next; // e=a,next=b
....
e.next = newTable[i]; // a.next=NUL
newTable[i] = e; // newTable[i]={ a -> NUL }
e = next; // e=b
LOOP2：
Entry<K,V> next = e.next; // e=b,next=c
....
e.next = newTable[i]; // b.next=a
newTable[i] = e; // newTable[i]={ b -> a -> NUL }
e = next; // e=c
LOOP3...略
相當(dāng)于將table[0]置換順序頭插到newTable[i]煤傍。
最終結(jié)果為：
newTable[i] = { c-> b -> a -> NUL }。
2.2 對于線程2：
假設(shè)執(zhí)行中途切換到了線程1嘱蛋，如下：
LOOP1：
Entry<K,V> next = e.next; // e=a,next=b
----線程1執(zhí)行后----
....
e.next = newTable[i]; // a.next=NUL
newTable[i] = e; // newTable[i]={ a -> NUL }
e = next; // e=b
LOOP2:
Entry<K,V> next = e.next; // e=b,next=a 注意線程1已修改指向
....
e.next = newTable[i]; // b.next=a
newTable[i] = e; // newTable[i]={ b -> a -> NUL }
e = next; // e=a
LOOP3:
Entry<K,V> next = e.next; // e=a,next=NUL
....
e.next = newTable[i]; // a.next=b 注意LOOP2中b.next=a
newTable[i] = e; // newTable[i]={ a -> b -> a -> b -> a -> ...... } 作死成功
e = next; // e=NUL 線程2結(jié)束循環(huán)
如果最后是線程2的newTable替換了table蚯姆，那么查找數(shù)據(jù)的時候就會死循環(huán)。
