Avoiding Recursive Invocation on ComputeIfAbsent() in HashMap

If a value doesn’t exist in the map, we calculate. We do it imperatively.

We first check if a value exists or not using containsKey() in an “if block.” If not found, we then calculate as follows:

static Map<Integer, BigInteger> cache = new HashMap<>(
          Map.of(0, BigInteger.ZERO, 1, BigInteger.ONE)
  );

  public static BigInteger fibonacci(int n) {
    if (!cache.containsKey(n)) {
      var computed = fibonacci(n - 1).add(fibonacci(n - 2));
      cache.put(n, computed);
    }

    return cache.get(n);
  }

However, the above code can be done in one line with a declarative approach usingcomputeIfAbsent method. For example:

  public static BigInteger fibonacci(int n) {
    return cache.computeIfAbsent(n,
            key -> fibonacci(key - 1).add(fibonacci(key - 2)));
  }

Although the above code is intuitive and functional, it doesn’t go along with the recursive invocation.

If we do the above, we will end up getting a ConcurrentModificationException exception. Because of fibonacci()’s invocation, we are attempting to modify values mapped to keys (key-1) and (key -2).

There is a modification count checking in the computeIfAbsent() method:

int mc = modCount;
V v = mappingFunction.apply(key);
if (mc != modCount) { throw new ConcurrentModificationException(); }

The expectation is, the mapping function should not modify this map during computation, which we are doing in the recursion.

Why does it throw ConcurrentModificationException? The idea is that it is not permissible for one thread to modify a Map while another thread is iterating on collection views of the HashMap. It will create inconsistencies and non-deterministic behavior at an undetermined time. The fail-fast approach is taken into consideration over here.

But, in the above, we didn’t use this code in the different thread, right? Well, it’s more of a contract. If the contract is violated the exception is thrown, even if the code runs in a single thread.

So what are the solutions? I've listed them below.

• Use the traditional imperative approach; that works fine.
• Use ConcurrentSkipListMap. ConcurrentSkipListMap is a thread-safe map and it will not through ConcurrentModificationException in recursive method while using computeIfAbsent().