java递归ConcurrentHashMap。ComputeFabSent（）调用永远不会终止。Bug还是“功能”？

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

但就是永不停歇？这似乎很危险。是虫子吗？还是我误解了合同

Answer 1

这当然是一个“功能”。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）

注：

^{}或^{}Javadoc并不禁止这种递归计算，这当然是荒谬的，因为缓存的类型是Map<Integer, Integer>，而不是ConcurrentHashMap<Integer, Integer>。对于子类型来说，彻底地重新定义超级类型契约是非常危险的（Set与SortedSet是问候语）<因此，在超级类型中也应该禁止执行这种递归

Answer 2

这在JDK-8062841中是固定的

在2011 proposal中，我在代码审查期间发现了这个问题。JavaDoc已更新，并添加了临时修复程序。由于性能问题，它在进一步重写时被删除

在2014 discussion中，我们探索了更好地检测和失败的方法。请注意，为了考虑低级别的更改，一些讨论被脱机到私人电子邮件。虽然不是每个案例都可以涵盖，但普通案例不会被活锁。这些fixes在Doug的存储库中，但还没有发布到JDK版本中

Answer 3

这与bug非常相似。 因为，如果你用32的容量创建缓存，你的程序将一直工作到49。 有趣的是，参数sizeCtl=32+（32>；>；>；1）+1）=49！ 可能是调整尺寸的原因