jdk7 hashmap并发put造成链表闭环

多个线程并发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, 出现了数据链闭环
}






参考 https://coolshell.cn/articles/9606.html

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容