多个线程并发resize-->transfer会造成数据链表闭环,其原因是多个线程并发transfer时使用同一个old table,并会并发修改old table的元素next指针。但造成数据链表闭环后,get到对应的闭环key时就会造成死循环,从而致使cup到100%使用率。
并发put修改元素的next指针也会造成数据丢失。
thread2: newTable[i]-->k7, k7.next-->k3, k3.next-->null
thread1: e-->k3, next-->k7
void transfer(Entry[]newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry < K, V > e: table) { // 使用同一个old 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]; // 并发修改元素next指针
newTable[i] = e;
e = next;
}
}
}
// 第一遍
for (Entry < K, V > e: table) {
while (null != e) {
Entry < K,
V > next = e.next; // e-->k3, next-->k7, 挂起
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);// 接着唤起 k7.next-->k3
e.next = newTable[i]; // k3.next-->null
newTable[i] = e;// newTable[i]-->k3
e = next; // e-->k7
}// newTable[i]-->k3, e-->k7, k7.next-->k3
}
for (Entry < K, V > e: table) {
while (null != e) { // 第2遍 newTable[i]-->k3, e-->k7, k7.next-->k3
Entry < K,
V > next = e.next; // next-->k3
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // k7.next-->k3
newTable[i] = e; // newTable[i]-->k7
e = next; // e-->k3
} // newTable[i]-->k7, k7.next-->k3, e-->k3, next--k3
}
for (Entry < K, V > e: table) {
while (null != e) {// 第3遍 newTable[i]-->k7, k7.next-->k3, e-->k3, next--k3
Entry < K,
V > next = e.next; // next-->null
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // k3.next--> k7
newTable[i] = e;// newTable[i]-->k3 --------------------!!!
e = next; //e -->null
} // newTable[i]-->k3, k3.next--> k7, k7.next-->k3, 出现了数据链闭环
}