ConcurrentHashMap 和斐波那契数列 - 结果不一致

java concurrenthashmap fibonacci

2022-09-03 04:28:11

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

当我使用小值时，程序工作绝对正常，但是当从程序增加的值从未停止时，程序会陷入无限循环8,9,1010 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);
        });
    }
}

有人能告诉我为什么它永远被困住了吗？

答案 1

您遇到了僵局。

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

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

答案 2

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

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

映射相对于数组具有优势，当值稀疏时，但当您具有数字序列时，可以使用简单数组。