java - 递归 ConcurrentHashMap.computeIfAbsent() 调用永远不会终止。错误或 "feature"？

Question

前段时间，I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively ，带有 ConcurrentHashMap 缓存和新的有用的 computeIfAbsent() 方法:

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);
        });
    }
}

我选择 ConcurrentHashMap 是因为我正在考虑通过引入并行性来使这个示例更加复杂(我最终没有这样做)。

现在，让我们将数字从 8 增加到 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, a reader of that blog post also confirmed the issue (he actually found it) .

这很奇怪。我会期待以下两种中的任何一种:

• 有效
• 它抛出一个 ConcurrentModificationException

但只是从不停止？这似乎很危险。它是一个错误吗？还是我误解了某些契约(Contract)？

Answer 1

这当然是一个“功能”。 ConcurrentHashMap.computeIfAbsent() Javadoc 内容如下:

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. 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.

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

有趣的是没有ConcurrentModificationException .相反，程序永远不会停止 - 在我看来这仍然是一个相当危险的错误(即 infinite loops. or: anything that can possibly go wrong, does )。

注意:

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