ConcurrentHashMap and Fibonacci Numbers - Inconsistent result

Question

I wrote a program for calculating fibonacci numbers recursively, with a ConcurrentHashMap and computeIfAbsent() method:

Program works absolutely fine when i used small values like 8,9,10 but stuck in endless loop when value increased from 10 to 20 program never halts

 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);
        });
    }
}

Can some one tell me why it is being stuck forever?

Answer 1

You are hitting a deadlock.

computeIfAbsent on a ConcurrentHashMap will lock the bucket in which the corresponding key will go to. If you are attempting to calculate a Fibonacci that is higher than the number of buckets in your map, then the recursive calls will attempt to lock a bucket that is already locked further up the call stack. But of course, that lock cannot be released until all of the recursive calls have completed. Thus, your deadlock.

I would reconsider your decision to use a ConcurrentHashMap here.