Avoid recursive invocation on computeIfAbsent() in HashMap

Posted on by

Categories:       

100DaysOfProgramming_Day002

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,

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)

                   

Share on:

Author: A N M Bazlur Rahman

Java Champion | Software Engineer | JUG Leader | Book Author | InfoQ & Foojay.IO Editor | Jakarta EE Ambassadors| Helping Java Developers to improve their coding & collaboration skills so that they can meet great people & collaborate

100daysofcode 100daysofjava access advance-java agile algorithm arraylist article bangla-book becoming-expert biginteger book calculator checked checked-exceptions cloning code-readability code-review coding coding-convention collection-framework compact-strings completablefuture concatenation concurrency concurrentmodificationexception concurrentskiplistmap counting countingcollections critical-section daemon-thread data-race data-structure datetime day002 deliberate-practice deserialization design-pattern developers duration execute-around executors export fibonacci file file-copy fork/join-common-pool functional future-java-developers groupby hash-function hashmap history history-of-java how-java-performs-better how-java-works http-client image import inspiration io itext-pdf java java-10 java-11 java-17 java-8 java-9 java-developers java-performance java-programming java-thread java-thread-programming java11 java16 java8 lambda-expression learning learning-and-development linkedlist list local-type-inference localdatetime map methodology microservices nio non-blockingio null-pointer-exception object-cloning optional packaging parallel pass-by-reference pass-by-value pdf performance prime-number programming project-loom race-condition readable-code record refactoring review scheduler scrum serialization serversocket simple-calculator socket software-development softwarearchitecture softwareengineering sorting source-code stack string string-pool stringbuilder swing thread threads tutorial unchecked vector virtual-thread volatile why-java zoneid