递归 ConcurrentHashMap.computeIfAbsent() 调用永远不会终止。错误还是“功能”？

前一段时间，我在博客中介绍了一种递归计算斐波那契数的 Java 8 函数方法，有一个ConcurrentHashMap缓存和新的、有用的computeIfAbsent() method:

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Test {
    static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        System.out.println(
            "f(" + 8 + ") = " + fibonacci(8));
    }

    static int fibonacci(int i) {
        if (i == 0)
            return i;

        if (i == 1)
            return 1;

        return cache.computeIfAbsent(i, (key) -> {
            System.out.println(
                "Slow calculation of " + key);

            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}

I chose ConcurrentHashMap因为我正在考虑通过引入并行性来使这个示例变得更加复杂（我最终没有这样做）。

现在，让我们增加数量8 to 25并观察会发生什么：

        System.out.println(
            "f(" + 25 + ") = " + fibonacci(25));

程序永远不会停止。在该方法内部，有一个永远运行的循环：

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

我在用着：

C:\Users\Lukas>java -version
java version "1.8.0_40-ea"
Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23)
Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)

该博文的读者 Matthias 也证实了这个问题（他确实找到了）.

这很奇怪。我本来期望以下两个中的任何一个：

• It works
• 它抛出一个ConcurrentModificationException

但就是从不停止？这看起来很危险。这是一个错误吗？还是我误解了一些合同？

这当然是一个“特征”. The ConcurrentHashMap.computeIfAbsent()Javadoc 内容如下：

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

The “一定不”措辞是一个明确的契约，我的算法违反了它，尽管不是出于相同的并发原因。

仍然有趣的是，没有ConcurrentModificationException。相反，该程序永远不会停止——在我看来，这仍然是一个相当危险的错误（即无限循环。或者：任何可能出错的事情都会发生).

Note:

The HashMap.computeIfAbsent() or Map.computeIfAbsent()Javadoc 不禁止这种递归计算，这当然是荒谬的，因为缓存的类型是Map<Integer, Integer>, not ConcurrentHashMap<Integer, Integer>。子类型彻底重新定义超类型合约是非常危险的（Set vs. SortedSet是问候）。因此，在超类型中也应该禁止执行此类递归。