ConcurrentHashMap computeIfAbsent

Question

现在没有在java 8的Javadoc推出了一个新的API computeIfAbsent 它的ConcurrentHashMap的impelementation状态:

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

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

Answer 1

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

试着回答你的问题:

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

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

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

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

Answer 2

你可以当值已经存在得到的争夺.

如果你查看computeIfAbsent()的源代码,它会非常复杂,但你会看到检查值是否已经存在于synchronized块内.考虑这个备用版本(不能以原子方式运行):

/**
 * 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

我也试过在启用Flight Recording的情况下运行它,并且争用清晰可见.这是一个示例堆栈跟踪:

"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)