java-8 - 也许我发现了concurrenthashmap的一个bug

Question

当我想高效地实现a^b时，我使用并发hashmap来存储计算值，代码为

private static final ConcurrentHashMap<String,Long> cache = new ConcurrentHashMap();

public long pow(long a, long b){
    System.out.printf("%d ^ %d%n",a,b);
    if(b == 1L){
        return a;
    }
    if( b == 2L){
        return a*a;
    }
    long l = b/2;
    long r = b - l;

    return cache.computeIfAbsent(a+","+l,k->pow(a,l)) * cache.computeIfAbsent(a+","+r,k->pow(a,r));
}

然后我调用这个方法

pow(2, 30);

但输出后

2 ^ 30
2 ^ 15
2 ^ 7

它被阻止了，通过使用jstack -l pid我得到了以下信息

"main" #1 prio=5 os_prio=31 tid=0x00007f910e801800 nid=0x1703 runnable [0x0000700000217000]
   java.lang.Thread.State: RUNNABLE
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1718)
    at interview.Pow.pow(Pow.java:28)
    at interview.Pow.lambda$pow$0(Pow.java:28)
    at interview.Pow$$Lambda$1/1807837413.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b72d930> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at interview.Pow.pow(Pow.java:28)
    at interview.Pow.lambda$pow$0(Pow.java:28)
    at interview.Pow$$Lambda$1/1807837413.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b72d060> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at interview.Pow.pow(Pow.java:28)
    at interview.Pow.testPow(Pow.java:32)

一开始我怀疑是不是发生了死锁，后来跟踪ConcurrentHashmap的源码才知道其实是死循环。 当 key 为 2,3 时，它与 key 2,15 具有相同的索引 9，但是 fh( fh = f.hash) 为 -3，无法满足

if (fh >= 0) {...}

所以在这种情况下，它无法打破循环

for (Node<K,V>[] tab = table;;) {...}

并无限循环。

这是一个错误还是故意设计的？

Answer 1

正如 C-Otto 已经评论的那样，您可以在第一个 computeIfabsent() 方法调用中调用第二个 computeIfAbsent()。 The documentation for this method明确指出:

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.

所以这不是 ConcurrentHashMap 实现中的错误，而是您的代码中的错误。