并行操作HashMap可能会丢失数据并发生死循环。
由于HashMap重新散列的过程会转置列表，由于不同线程转置进度不一致，慢线程会将快线程的转置结果切断并反方向连接形成闭环。
一、简述
设一哈希表map，散列表table长度为1，表示为：
map = [ {} ]
table[0]= {}
散列三个元素a、b、c，假设刚好全部散列在table[0]，表示为
map = [ { a -> b -> c -> NUL } ]
table[0] = { a -> b -> c -> NUL }
主线程启动两个线程，线程1，线程2，分别向map插入数据，又假设刚好散列在table[0]。
假设阀值为3，此时需要调整table长度避免数据扎堆，很不幸，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...略
相当于将table[0]置换顺序头插到newTable[i]。
最终结果为：
newTable[i] = { c-> b -> a -> NUL }。
2.2 对于线程2：
假设执行中途切换到了线程1，如下：
LOOP1：
Entry<K,V> next = e.next; // e=a,next=b
----线程1执行后----
....
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结束循环
如果最后是线程2的newTable替换了table，那么查找数据的时候就会死循环。
