Avoid 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, this above code can be done in one line with a declarative approach using-computeIfAbsent 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, 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 behaviour at an undetermined time. 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,

• 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().

References:

1. https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/ConcurrentModificationException.html
2. https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/HashMap.html#computeIfAbsent(K,java.util.function.Function)