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

Question

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

16

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

当我使用像8,9,10这样的小值时，程序完全正常工作，但是当值从10到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);
        });
    }
}

有人能告诉我为什么它一直卡住吗？

- T-Bag

你可以看下面的解释，但是我关于递归斐波那契数列的说法是正确的；如果你确实需要生成高序列的斐波那契数，那么请使用动态规划。 - Tim Biegeleisen

@TimBiegeleisen- 是的，我会的...我只是在玩并发哈希映射，然后发现了这个... :) - T-Bag

1

@TimBiegeleisen OP正在进行动态规划，只是以一种不太明显的方式。斐波那契数列的每个项仅在未被计算过时才会被计算。如果先前已经计算过，则从“concurrentMap”中查找该值。 - Adrian Shum

1

@AdrianShum 是的，我现在明白了。今天是 Tim 错误的一天。但是看起来这不是一个有效的 DP 方法。 - Tim Biegeleisen

在地图/列表上进行迭代，无论是使用循环还是递归，都必须使用包含整个迭代过程的同步块，否则如果另一个线程第二次执行循环，则会出现并发问题。 - Walfrat

可能是 Recursive ConcurrentHashMap.computeIfAbsent() 调用永远不会终止。是 Bug 还是“特性”？的重复问题。 - UserF40

4个回答

3

这种递归方法计算斐波那契数列的复杂度是指数级别的。使用缓存可以将其降低为线性级别，或者你可以使用简单的循环代替递归来获得线性算法。

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

在值稀疏的情况下，map比数组有优势，但当你有一系列数字时，你可以使用简单的数组。

- Giedrius Tumelis

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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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$0(Test.java:20)
    at Test$$Lambda$1/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

- T-Bag

确实如此 - 在我的jdk1.8.0_121中，ConcurrentHashMap.java的第1674行是synchronized(f) {，其中f是一个Node，在这种情况下是一个ReservationNode - 可能是与栈底部锁定的相同节点，根据哈希值。 - Hulk

2

所有这些都是实现细节，可能随时会更改。重要的是ConcurrentHashMap.computeIfAbsent的契约声明映射函数“不得尝试更新此地图的任何其他映射”。（另请参见我的其他评论https://dev59.com/olcP5IYBdhLWcg3w0tQ0#z7KiEYcBWogLw_1bKD3u） - Hulk

1

根据Oracle Doc，在计算进行时，其他线程对该映射尝试的某些更新操作可能会被阻塞，因此计算应该简短且简单，并且不得尝试更新该映射的任何其他映射。正如最高票答案中Joe C所说，ConcurrentHashMap的默认初始化在实例化时分配了少量桶。使用ConcurrentHashMap的目的是允许多个线程同时修改Map而无需阻塞它们(link)。

如果您仍然想在应用程序中使用ConcurrentHashMap，那么我建议在创建时增加其initialCapacity。

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

可以计算包括 25 在内的斐波那契数列。

根据文档，

ConcurrentHashMap()
创建一个具有默认初始表大小（16）的新空映射。

然而，我对此持有不同意见，因为我注意到默认大小要小得多。
这是因为当您从ConcurrentHashMap<>(11)获取fibonacci(25)时，ConcurrentHashMap<>()<-- 这里应该是默认16...但它不是。

- Devendra Lattu

这里有两个误解：1. ConcurrentHashMap 的默认初始容量是16，如JavaDocs所述。然而，默认的loadFactor是0.75，因此一旦您将第13个元素放入Map中，它就会尝试进行扩容。 - Hulk

仅仅因为你的 Map 容量为 16，并不意味着将 16 个条目放入其中就会将它们放入单独的桶中。

- Hulk

只是一个例子：用键k=[0,1,2,4,9,16,25..100]（值无关紧要）填充HashMap，并且您可以借助调试器验证仅有 16 个默认桶中的 4 个包含值，这些值在索引为 0、1、4、9 的位置。索引为 0 的桶包含键 0、16 和 64 的映射，索引为 1 的桶包含键 1、49 和 81 的映射。 - Hulk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joe C · Accepted Answer

你遇到了死锁。

ConcurrentHashMap中的computeIfAbsent方法将会锁定对应的存储桶。如果你尝试计算一个比你的Map中桶的数量更高的斐波那契数列，那么递归调用会试图锁定已经在调用栈上方锁定的存储桶。但是，这个锁定当然不能在所有递归调用完成之前被释放。因此，你陷入了死锁。

我建议你重新考虑在这里使用ConcurrentHashMap。