也许我发现了 concurrenthashmap 的一个错误

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[=13=](Pow.java:28)
    at interview.Pow$$Lambda/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[=13=](Pow.java:28)
    at interview.Pow$$Lambda/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;;) {...}

并无限循环。

是bug还是故意设计的？

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 实现中的错误，而是您的代码中的错误。

也许我发现了 concurrenthashmap 的一个错误

Maybe I've found a bug of concurrenthashmap

java-8

concurrenthashmap