ConcurrentHashMap computeIfAbsent

Question

Java8中引入了一个新的computeIfAbsent API。ConcurrentHashMap对它的影响状态的javadocs：

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

那么，在密钥已经存在且不需要计算的情况下，它对这个实现的锁定有什么看法呢？整个方法computeIfAbsent是否像文档中所述的那样同步，即使不需要计算，或者只是对映射函数调用进行同步，以防止两次调用函数？

Answer 1

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

试着回答你的问题：

那么，在密钥已经存在且不需要计算的情况下，它对这个实现的锁定有什么看法呢？

我们有理由认为，与任何读取操作一样，不需要锁定来检查密钥是否已经存在，并且映射函数也不需要执行。

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

不，该方法在锁定方面不是同步的，但是从调用方的角度来看，它是原子地执行的(也就是说，映射函数最多应用一次)。如果找不到密钥，则必须使用映射函数计算的值执行更新操作，并在调用该函数时涉及某种类型的锁定。可以合理地认为，这种锁定是非常细粒度的，只涉及表中很小的一部分(嗯，必须存储密钥的特定数据结构)，这就是为什么(引用javadoc，着重挖掘)“__--一些尝试由其他线程执行的更新操作--可能会在计算过程中阻止”。

Answer 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上运行，结果(经过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)

Answer 3

提到的bugfix @RolandIllig指出，如果键不是bin中的第一个键，仍然会发生争用。我使用JMH和Java 10进行了测试。

luckyKey的吞吐量：

Result: 324172.798 ±(99.9%) 15244.448 ops/ms [Average]

unluckyKey的吞吐量：

Result: 15386.202 ±(99.9%) 526.877 ops/ms [Average]

基准码

@Threads(8)
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class ComputeIfAbsentBenchmark {

  @State(Scope.Benchmark)
  public static class MyState {
    private final Map<String, Integer> map = new ConcurrentHashMap<>();

    public MyState() {
      for (int i = 0; i < 100; i++)
        map.put(Integer.toString(i), i);
    }
  }

  @Benchmark
  public void luckyKey(final MyState state) {
    state.map.computeIfAbsent("1", key -> 100);
  }

  @Benchmark
  public void unluckyKey(final MyState state) {
    state.map.computeIfAbsent("98", key -> 100);
  }

}