のConcurrentHashMapとフィボナッチ数 - 一貫性のない結果

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

デッドロックが発生しています。

computeIfAbsent（コンカレントハッシュマップ）は、対応するキーが移動するバケットをロックします。マップ内のバケットの数よりも高いフィボナッチを計算しようとすると、再帰呼び出しはすでに呼び出しスタックの上にロックされているバケットをロックしようとします。もちろん、すべての再帰呼び出しが完了するまでロックを解放することはできません。したがって、あなたのデッドロック。

ここでConcurrentHashMapを使用することを決定しました。

Answer 2

フィボナッチ数を計算するためのこの再帰方法は、指数関数的な複雑さを持っています。キャッシングを使用すると、線形に戻すことができます。また、線形アルゴリズムを得るために、再帰の代わりに単純なサイクルを使用することもできます。

キャッシングになぜConcurentHashMapを使用しているのでしょうか。私はシンプルなマップ、またはキャッシングのために配列を使用します。

マップには配列に対して利点がありますが、値が疎である場合でも数字のシーケンスがある場合は単純な配列を使用できます。

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$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 

Answer 4

演算中は他のスレッドによってこのマップ上のいくつか試みた更新操作がブロックされることがあり、その計算は短く、シンプルであるべき、としないでなければなりませんOracle Doc

を1としてこのマップの他のマッピングを更新

は当然ジョー・C最上位の答えでで言ったように、ConcurrentHashMapのデフォルトの初期化は、SMAを持って インスタンス化時に割り当てられたバケット数。

ConcurrentHashMapを使用する目的は、それらをブロックする必要なく複数のスレッドからマップを同時に変更できるようにすることです（link）。

---

あなたはまだあなたのアプリケーションのためのConcurrentHashMapを使用して滞在したい場合は、私は、その作成中InitialCapacityの値を増やすことをお勧めします。

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

は件までフィボナッチ数列を計算し、DOC 1として25

---

含む、

できConcurrentHashMapの（）
は、デフォルトの初期テーブルサイズで、新しい空のマップを作成します（16）。

しかし、デフォルトサイズがはるかに小さいことに気付いたので、私はこれを尋ねます。
fibonacci(25)をConcurrentHashMap<>(11)からConcurrentHashMap<>() <に変更した場合の理由は、ここではデフォルト16にする必要がありますが、そうではありません。