HashMap 多线程下死循环分析及JDK8修复

简介

当HashMap的容量告急时,HashMap会 resize 进行扩容,扩容的过程就是将 table[] 数组放大两倍,然后通过 transfer 方法进行数据转移,从老的 table 转移到新的 table 数组里。

以下就是 transfer 代码:

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

重现

当两个线程同时进行 put 操作时,基本同时会达到 HashMap 的存储阈值,所以也就会并发进行 resize,各自有一个新的 table[] 数组,但是老的数组是同一个。

补充HashMap结构

HashMap 是一个数组加链表的结构,一个数据put入 HashMap 先计算它的 hashcode, 然后取模后得到其在 table 数组的下标 index, 再将该数据节点放到 index 处的链表中。

(图片来源:http://www.cnblogs.com/ITtangtang/p/3948406.html)

情景假设

现假设 table 某下标 i 处的链表如下:

i =>  A => B => C

单线程正常情况 resize 后会变为:

i => B => A
...
j => C

多线程Resize

开始执行 transfer(下面 e 和 next 都是 transfer 中变量)

第一步:

Thread1:

e = A
next = B

=========

newtable[i] => null

Thread2:

e = A
next = B

=========

newtable[i] => null

 第二步:

Thread1:(没有抢到CPU时间所以没变化)

e = A
next = B

=========

newtable[i] => null

Thread2:

e = B
next = C

=========

newtable[i] => A

 第三步:

Thread1:(没有抢到CPU时间所以没变化)

e = A
next = B

=========

newtable[i] => null

Thread2:

注意:这里B的 next 已经变成 A 了,下面线程2在执行时会取 B.next

e = C
next = null

=========

newtable[i] => B => A 

第四步:

Thread1:

e = B
next = A

=========

newtable[i] => A

Thread2:(没抢到CPU时间没变化)

e = C
next = null

=========

newtable[i] => B => A 

 第五步:

Thread1:

e = A
next = null

=========

newtable[i] => B => A

Thread2:(没抢到CPU时间没变化)

e = C
next = null

=========

newtable[i] => B => A 

 第六步:

Thread1:

因为 A 已经插入了,B.next = A,再把 A 插入一次,A.next = B,这里产生了循环

e = null
next = null

=========

newtable[i] => A <=> B

Thread2:(没抢到CPU时间没变化)

e = C
next = null

=========

newtable[i] => B => A 

死循环

当执行 get 时,当key 正好被分到那个 table[i] 上时,遍历链表就会产生循环。

JDK8的修复

JDK8 将 HashMap 的结构作了下修改,将原来的链表部分改为数据少时仍然链表,当超过一定数量后变换为红黑树,这里主要讨论在链表时跟之前有什么不同。

链表部分

链表部分对应上面 transfer 的代码:

    Node<K,V> loHead = null, loTail = null;
    Node<K,V> hiHead = null, hiTail = null;
    Node<K,V> next;
    do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {
            if (loTail == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
        }
        else {
            if (hiTail == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
        }
    } while ((e = next) != null);
    if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;
    }
    if (hiTail != null) {
        hiTail.next = null;
        newTab[j + oldCap] = hiHead;
    }

由于扩容是按两倍进行扩,即 N 扩为 N + N,因此就会存在低位部分 0 - (N-1),以及高位部分 N - (2N-1), 所以这里分为 loHead (low Head) 和 hiHead (high head)。

通过上面的分析,不难发现循环的产生是因为新链表的顺序跟旧的链表是完全相反的,所以只要保证建新链时还是按照原来的顺序的话就不会产生循环。

JDK8是用 head 和 tail 来保证链表的顺序和之前一样,这样就不会产生循环引用。

树部分

树部分处理基本跟链表一直,先建立新链表,然后使用新链表进行树化。

        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }


============================ 一直到这里逻辑跟链表几乎一样,核心还是保持顺序、分高低位

            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);   <============= 这里进行树化转化
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

总结:

虽然修复了死循环的BUG,但是HashMap 还是非线程安全类,仍然会产生数据丢失等问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

16830
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

26230
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

27040
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

31080
来自专栏王亚昌的专栏

A*算法C实现

参考 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html 实现了A*算法,模拟了一下,...

10620
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

40090
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

13720
来自专栏小樱的经验随笔

BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题,n^4大暴力】

1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1689  So...

31080
来自专栏算法修养

HOJ 2133&POJ 2964 Tourist(动态规划)

Tourist Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1503...

37080
来自专栏机器学习原理

示例三(3)——人物画像特征提取

47730

扫码关注云+社区

领取腾讯云代金券