ConcurrentHashMap竟然也有死循环问题?

前几天和拼多多及政采云的架构师们闲聊,其中拼多多架构师说遇到了一个ConcurrentHashMap死循环问题,当时心里想这不科学呀?ConcurrentHashMap怎么还有死循环呢,毕竟它已经解决HashMap中rehash中死循环问题了,但是随着深入的分析,发现事情并没有之前想的那么简单~ (以下分析基于jdk版本:jdk1.8.0_171)

保险起见,不能直接贴出出现问题的业务代码,因此将该问题简化成如下代码:

ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
// map默认capacity 16,当元素个数达到(capacity - capacity >> 2) = 12个时会触发rehash
for (int i = 0; i < 11; i++) {
    map.put(i, i);
}

map.computeIfAbsent(12, (k) -> {
    // 这里会导致死循环 :(
    map.put(100, 100);
    return k;
});

// 其他操作

感兴趣的小伙伴可以在电脑上运行下,话不说多,先说下问题原因:当执行computeIfAbsent时,如果key对应的slot为空,此时会创建ReservationNode对象(hash值为RESERVED=-3)放到当前slot位置,然后调用mappingFunction.apply(key)生成value,根据value创建Node之后赋值到slow位置,此时完成computeIfAbsent流程。但是上述代码mappingFunction中又对该map进行了一次put操作,并且触发了rehash操作,在transfer中遍历slot数组时,依次判断slot对应Node是否为null、hash值是否为MOVED=-1、hash值否大于0(list结构)、Node类型是否是TreeBin(红黑树结构),唯独没有判断hash值为RESERVED=-3的情况,因此导致了死循环问题。

问题分析到这里,原因已经很清楚了,当时我们认为,这可能是jdk的“bug”,因此我们最后给出的解决方案是:

1.如果在rehash时出现了slot节点类型是ReservationNode,可以给个提示,比如抛异常;2.理论上来说,mappingFunction中不应该再对当前map进行更新操作了,但是jdk并没有禁止不能这样用,最好说明下。

最后,另一个朋友看了computeIfAbsent的注释:

/**
 * If the specified key is not already associated with a value,
 * attempts to compute its value using the given mapping function
 * and enters it into this map unless {@code null}.  The entire
 * method invocation is performed atomically, so the function is
 * applied at most once per key.  Some attempted update operations
 * on this map by other threads may be blocked while computation
 * is in progress, so the computation should be short and simple,
 * and must not attempt to update any other mappings of this map.
 */
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

我们发现,其实人家已经知道了这个问题,还特意注释说明了。。。我们还是too yong too simple啊。至此,ConcurrentHashMap死循环问题告一段落,还是要遵循编码规范,不要在mappingFunction中再对当前map进行更新操作。其实ConcurrentHashMap死循环不仅仅出现在上述讨论的场景中,以下场景也会触发,原因和上述讨论的是一样的,代码如下,感兴趣的小伙伴也可以本地跑下:

ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
map.computeIfAbsent(12, (k) -> {
    map.put(k, k);
    return k;
});

System.out.println(map);
// 其他操作

最后,一起跟着computeIfAbsent源码来分下上述死循环代码的执行流程,限于篇幅,只分析下主要流程代码:

public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    if (key == null || mappingFunction == null)
        throw new NullPointerException();
    int h = spread(key.hashCode());
    V val = null;
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
            Node<K,V> r = new ReservationNode<K,V>();
            synchronized (r) {
                // 这里使用synchronized针对局部对象意义不大,主要是下面的cas操作保证并发问题
                if (casTabAt(tab, i, null, r)) {
                    binCount = 1;
                    Node<K,V> node = null;
                    try {
                        // 这里的value返回可能为null呦
                        if ((val = mappingFunction.apply(key)) != null)
                            node = new Node<K,V>(h, key, val, null);
                    } finally {
                        setTabAt(tab, i, node);
                    }
                }
            }
            if (binCount != 0)
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            boolean added = false;
            synchronized (f) {
                // 仅仅判断了node.hash >=0和node为TreeBin类型情况,未判断`ReservationNode`类型
                // 扩容时判断和此处类似
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek; V ev;
                            if (e.hash == h &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                val = e.val;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                if ((val = mappingFunction.apply(key)) != null) {
                                    added = true;
                                    pred.next = new Node<K,V>(h, key, val, null);
                                }
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        binCount = 2;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null &&
                            (p = r.findTreeNode(h, key, null)) != null)
                            val = p.val;
                        else if ((val = mappingFunction.apply(key)) != null) {
                            added = true;
                            t.putTreeVal(h, key, val);
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (!added)
                    return val;
                break;
            }
        }
    }
    if (val != null)
        // 计数统计&阈值判断+扩容操作
        addCount(1L, binCount);
    return val;
}

本文分享自微信公众号 - TopCoder(gh_12e4a74a5c9c)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-29

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

一文读懂Python复杂网络分析库networkx | CSDN博文精选

networkx是一个用Python语言开发的图论与复杂网络建模工具,内置了常用的图与复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。

56630
来自专栏码客

Sublime text 安装 及 插件安装

从菜单 View - Show Console 或者ctrl + ~ 快捷键,调出 console。将以下 Python 代码粘贴进去并 enter 执行,不出...

12830
来自专栏码客

Electron中调用DLL

NodeJS地址:https://nodejs.org/en/download/ Electron版本: https://electronjs.org/rele...

62130
来自专栏二狗的DBA之路

PostgreSQL 多个同步复制服务器

在PG10及以后版本中,引入了 synchronous_standby_names 这种基于 Quorum的同步复制优选提交的机制。

13420
来自专栏java一日一条

Java 经典面试题:为什么 ConcurrentHashMap 的读操作不需要加锁?

我们知道,ConcurrentHashmap(1.8)这个并发集合框架是线程安全的,当你看到源码的get操作时,会发现get操作全程是没有加任何锁的,这也是这篇...

8920
来自专栏二狗的DBA之路

使用 redis-shake 迁移 redis-cluster集群

    IDC上云, 有2套redis-cluster需要迁移到云上。 这里我们使用 redis-shake 来做迁移操作。

11620
来自专栏码客

Vue开始使用NUXT框架开发

Nuxt.js 为 客户端/服务端 这种典型的应用架构模式提供了许多有用的特性,例如服务端渲染、SEO、中间件支持、布局支持等。

12120
来自专栏大数据学习笔记

Neo4J:创建带关系的节点

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

29220
来自专栏相约机器人

识别自动驾驶的深度

有许多传感器可用于在车辆行驶时捕获信息。捕获的各种测量结果包括速度,位置,深度,热等。这些测量结果被输入到反馈系统中,该系统训练并利用运动模型来遵守车辆。本文重...

13210
来自专栏码客

Electron启程

Electron 可以让你使用纯 JavaScript 调用丰富的原生(操作系统) APIs 来创造桌面应用。 你可以把它看作一个 Node. js 的变体,它...

18130

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励