计算机并发哈希映射表中的computeIfAbsent方法中，什么是原子性？原子性与同步锁的区别是什么？

Question

计算机并发哈希映射表中的computeIfAbsent方法中，什么是原子性？原子性与同步锁的区别是什么？

javamultithreading

5

我知道有很多关于computeIfAbsent的问题。

具体而言，我想了解并发哈希映射中原子性语句的含义。

来自JavaDoc：

整个方法调用是原子性的，因此该函数最多应用于每个键一次。

如果两个线程尝试使用不同的键执行computeIfAbsent并发现在两种情况下映射都不包含它们，那么计算缺失函数的结果执行是否会并发？我理解如果两个线程都尝试添加相同的键，则它们不会同时进行。

虽然使用了“原子”一词，并且提到这意味着每个键最多只应用一次，但没有具体说明该方法的同步行为。

顺便说一句，对我而言，这与由computeIfAbsent调用的修改类字段的方法有关。

我想了解在两个不同的键的computeIfAbsent方法的两个不同线程执行中是否存在线程安全问题。

基本上，我需要查看类似于在访问字段变量及其后续在调用computeIfAbsent方法时进行同步的内容。*（调用的computeIfAbsent方法是唯一修改该字段的方法。除了来自哈希映射computeIfAbsent方法的调用之外，没有其他调用者。只有一个并发哈希映射实例调用computeWithAbsent方法，调用涉及的“原子”方法）*我的字段是易失性的，以避免原子可见性的潜在问题。

- Shawn

2个回答

2

有些情况下，映射函数可能会针对不同的键值同时执行，因此您的映射函数必须是线程安全的。

computeIfAbsent 方法仅保证不会同时为相同的键值调用映射函数。同时，请注意，Map 是通过将多个键哈希到条目桶中工作的，如果使用一对映射到 ConcurrentHashMap 的子表的同步调用 computeIfAbsent(a, mapFunc) 和 computeIfAbsent(b, mapFunc)，则每个键的 mapFunc 将一个接一个地运行而不是同时运行。

然而，如果不同的键不解析为在 ConcurrentHashMap 中解析为同一子表，则您应该期望您的映射函数被不同的线程同时调用，以处理不同的键值。

以下是一个示例，展示了一个检测并发调用器的线程安全的映射函数：

public static void main(String[] args) throws InterruptedException {
    ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>(2096, 1.0f);
    AtomicInteger concurrent = new AtomicInteger();
    Function<String, String> mappingFunction = s -> {
        int c = concurrent.incrementAndGet();
        String value = "Value:"+s +" concurrent="+c+" thread="+Thread.currentThread().getName();
        if (c != 1)
            System.out.println("Multiple callers for "+value);
        try { Thread.sleep(50); } catch (InterruptedException ignore) { }
        concurrent.decrementAndGet();
        return value;
    };
    Runnable task = () -> {
        Random r = new Random();
        for (int i = 0; i < 10_000; i++)
            map.computeIfAbsent(String.valueOf(r.nextInt(10240)), mappingFunction);
    };

    Thread a = new Thread(task, "one");

    a.start();
    task.run();
    a.join();
    map.values().stream().limit(32).forEach(System.out::println);
}

如果运行足够长时间，mappingFunction内部的计数器会出现两个实例在一对线程上同时运行的情况。

编辑：

回答您关于synchronized (r)的评论：

请注意，computeIfAbsent中有一个无限循环，只有在break或return时才退出，并且mappingFunction.apply(key)在两个位置被调用：

1. 当键是子表中的第一个条目时，它运行到synchronized(r)块。由于前一行声明了Node<K,V> r = new ReservationNode<K,V>()，因此从不会有不同线程对r的争用，但仅有一个线程成功进入if (casTabAt(...)) { binCount = 1; ... } 块并返回，其他失败的线程恢复循环。

2. 当键不是子表中的第一个条目时，它运行到synchronized(f)块，该块将阻止尝试为哈希到同一子表的不同键计算computeIfAbsent的所有线程，除了一个线程。当每个线程进入该块时，它会验证f是否未更改，如果是，则返回现有值或计算的新值-否则恢复循环。

- DuncG

这正是我所担心的！因为键不同，我必须确保我的computeIfAbsent方法是线程安全的。出于对Github中open JDK的computeIfAbsent代码的兴趣，“https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java”，你能指出哪些行使用子表来打败“r”上的同步吗？ - Shawn

谢谢 @DuncG。我注意到了 synchronized (r) ，它是一个误导。 - Shawn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Diego · Accepted Answer

TL;DR：当两个线程执行computeIfAbsent时，只有一个线程会成功。第二个线程将被阻塞，直到第一个线程结束。一旦第一个线程完成，第二个线程现在将找到该键，并且不会应用映射函数。

现在进入细节：

据说computeIfAbsent是原子的，因为它使用同步和比较交换机制的混合物来搜索和设置映射中的值。这确保了两个线程在设置新键时不会发生冲突，这就是文档确保此方法将最多执行一次的原因。

如果您快速查看JDK中computeIfAbsent源代码，您会发现以下内容：

synchronized (r) {
                if (casTabAt(tab, i, null, r)) {
                    binCount = 1;
                    Node<K,V> node = null;
                    try {
                        if ((val = mappingFunction.apply(key)) != null)
                            node = new Node<K,V>(h, key, val);
                    } finally {
                        setTabAt(tab, i, node);
                    }
                }
            }

那段代码将会粒度地阻塞并尝试原子性地应用映射函数。

如果您想深入了解，且对HashMap的工作原理和CAS有很好的理解，您还可以查看更详细的ConcurrentHashMap代码解释，链接在此：JDK8中ConcurrentHashmap的代码解释。