ConcurrentHashMap 和 Fibonacci 数 - 不一致的结果

Question

我写了一个递归计算斐波那契数的程序，使用 ConcurrentHashMap 和 computeIfAbsent() 方法：

当我使用像 8,9,10 这样的小值时，程序工作得非常好，但是当值从 10 to 20 增加时陷入无限循环 程序永远不会停止

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

    public static void main(String[] args) {
        System.out.println("Fibonacci result for 20 is" + fibonacci(20));
    }

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

        if (i == 1)
            return 1;

        return concurrentMap.computeIfAbsent(i, (key) -> {
            System.out.println("Value is " + key);
            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}

谁能告诉我为什么它永远卡住了？

Answer 1

你陷入了僵局。

ConcurrentHashMap 上的

computeIfAbsent 将锁定相应键将转到的存储桶。如果您尝试计算高于地图中桶数的斐波那契数列，则递归调用将尝试锁定一个已经在调用堆栈中进一步锁定的桶。但是当然，在所有递归调用完成之前，无法释放该锁。因此，你的僵局。

我会重新考虑你在这里使用 ConcurrentHashMap 的决定。

Answer 2

这种计算斐波那契数的递归方法是指数复杂度。通过缓存，您可以将其减少回线性，或者您可以使用简单循环而不是递归来获得线性算法。

我想知道你为什么要使用 ConcurentHashMap 进行缓存。我会使用简单的地图或数组进行缓存。

当值稀疏时，Maps 相对于数组有优势，但是当你有数字序列时，你可以使用简单的数组。

Answer 3

我进行了线程转储，我们可以看到带锁 0x000000076b70bba0 的线程导致了死锁问题。

如有错误请指正

main - priority:5 - threadId:0x00000000021af000 - nativeId:0x2798 - state:RUNNABLE
    stackTrace:
    java.lang.Thread.State: RUNNABLE
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674)
    - locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70c720> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70c5c0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70c460> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70c300> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70c1a0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70c040> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70bee0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.lambda[=10=](Test.java:20)
    at Test$$Lambda/834600351.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
    - locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at Test.fibonacci(Test.java:18)
    at Test.main(Test.java:8)
    Locked ownable synchronizers:
    - None

Answer 4

根据 Oracle Doc

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

正如 Joe C 在最上面的答案中所说的那样，ConcurrentHashMap 的默认初始化在实例化时分配了少量的桶。

使用 ConcurrentHashMap 的目的是允许多个线程同时修改 Map 而无需阻塞它们 (link)。

如果您仍想继续为您的应用程序使用 ConcurrentHashMap，那么我建议在其创建期间增加 initialCapacity。

static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>(11);

可以计算斐波那契数列直到并包括 25

根据文档，

ConcurrentHashMap()
Creates a new, empty map with the default initial table size (16).

但是，我对此持不同意见，因为我注意到默认尺寸要小得多。
这样做的原因是当你从 ConcurrentHashMap<>(11) 得到 fibonacci(25) 然后 ConcurrentHashMap<>() <-- 这里应该是默认的 16..但它不是。

ConcurrentHashMap 和 Fibonacci 数 - 不一致的结果

ConcurrentHashMap and Fibonacci Numbers - Inconsistent result

java

fibonacci

concurrenthashmap