ConcurrentHashMap computeIfAbsent

concurrency multithreading java

2022-09-02 09:38:43

Java 8 中引入了一个新的 computeIfAbsent API。ConcurrentHashMap的javadocs对它的植入状态：

如果指定的键尚未与值关联，则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非为 null。整个方法调用以原子方式执行，因此每个键最多应用一次函数。在计算过程中，其他线程在此映射上尝试的一些更新操作可能会被阻止，因此计算应简短明了，并且不得尝试更新此映射的任何其他映射。

那么，当密钥已经存在并且不需要计算时，锁定此实现意味着什么？即使不需要计算，或者只是同步映射函数调用以防止调用函数两次，整个方法 computeIfAbsent 是否如文档中所述同步？

答案 1

ConcurrentHashMap的实现非常复杂，因为它专门设计用于允许并发可读性，同时最大限度地减少更新争用。在非常高的抽象级别，它被组织为一个桶式哈希表。所有读取操作都不需要锁定，并且（引用javadoc）“不支持以阻止所有访问的方式锁定整个表”。为了实现这一点，内部设计非常复杂（但仍然优雅），键值映射保存在节点中，这些节点可以以各种方式（例如列表或平衡树）排列，以利用细粒度锁。如果您对实现细节感兴趣，还可以查看源代码。

尝试回答您的问题：

那么，当密钥已经存在并且不需要计算时，锁定此实现意味着什么？

可以合理地认为，与任何读取操作一样，不需要锁定来检查密钥是否已存在，并且不需要执行映射功能。

即使不需要计算，整个方法 computeIfAbsent 是否如文档中所述同步，或者只是同步映射函数调用以防止调用函数两次？

不，该方法在锁定方面不是同步的，但从调用方的角度来看，它是以原子方式执行的（即映射函数最多应用一次）。如果未找到该键，则必须使用映射函数计算的值执行更新操作，并且在调用该函数时涉及某种锁定。有理由认为，这种锁定是非常细粒度的，只涉及表的一小部分（好吧，必须存储密钥的特定数据结构），这就是为什么（引用javadoc，强调我的）“其他线程的一些尝试更新操作可能会在计算过程中被阻止”。

答案 2

当值已存在时，您可能会遇到争用。

如果你看一下 computeIfAbsent（）的源代码，它非常复杂，但你会看到检查值是否已经存在，就在同步块内。考虑这个替代版本（不以原子方式运行）：

/**
 * Alternate implementation that doesn't block when map already
 * contains the value
 */
public V computeIfAbsent2(K key, Function<? super K, ? extends V> mappingFunction) {
    V value = get(key);
    if (value == null) {
        value = mappingFunction.apply(key);
        put(key, value);
    }
    return value;
}

我运行了一个JMH测试，将此替代实现与原始实现进行比较。我运行了20个线程，并使用了包含20个已存在值的 ConcurrentHashMap。每个线程将使用所有 20 个值。测试仅执行该值已存在的情况。它在OS X上运行。结果（2分钟热身后）是

Benchmark                                     Mode  Cnt       Score   Error   Units
ComputIfAbsentTest.benchComputeAbsent        thrpt    2   77966.354          ops/ms
ComputIfAbsentTest.benchComputeAbsent2       thrpt    2  463096.033          ops/ms

我还尝试在启用飞行录制的情况下运行此功能，并且争用清晰可见。下面是一个示例堆栈跟踪：

"local.ComputIfAbsentTest.benchComputeAbsent-jmh-worker-11" #25 daemon prio=5 os_prio=31 tid=0x00007f89da10b000 nid=0x7203 waiting for monitor entry [0x00007000021f8000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674)
    - waiting to lock <0x0000000795f80540> (a java.util.concurrent.ConcurrentHashMap$Node)
    at local.ComputIfAbsentTest.benchComputeAbsent(ComputIfAbsentTest.java:87)
    at local.generated.ComputIfAbsentTest_benchComputeAbsent_jmhTest.benchComputeAbsent_thrpt_jmhStub(ComputIfAbsentTest_benchComputeAbsent_jmhTest.java:116)
    at local.generated.ComputIfAbsentTest_benchComputeAbsent_jmhTest.benchComputeAbsent_Throughput(ComputIfAbsentTest_benchComputeAbsent_jmhTest.java:76)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:483)
    at org.openjdk.jmh.runner.BenchmarkHandler$BenchmarkTask.call(BenchmarkHandler.java:430)
    at org.openjdk.jmh.runner.BenchmarkHandler$BenchmarkTask.call(BenchmarkHandler.java:412)
    at java.util.concurrent.FutureTask.run(FutureTask.java:266)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)