title: Since Java 9 HashMap.computeIfAbsent() throws ConcurrentModificationException on attempt to memoize recursive function results
body: <p>Today I learned from some JS course what memoization is and tried to implement it in Java. I had a simple recursive function to evaluate n-th Fibonacci number:</p>
  
  <pre><code>long fib(long n) {
      if (n &lt; 2) {
          return n;
      }
  
      return fib(n - 1) + fib(n - 2);
  }
  </code></pre>
  
  <p>Then I decided to use HashMap in order to cache results of recursive method:</p>
  
  <pre><code>private static &lt;I, O&gt; Function&lt;I, O&gt; memoize(Function&lt;I, O&gt; fn) {
      final Map&lt;I, O&gt; cache = new HashMap&lt;&gt;();
      return in -&gt; {
          if (cache.get(in) != null) {
              return cache.get(in);
          } else {
              O result = fn.apply(in);
              cache.put(in, result);
              return result;
          }
      };
  }
  </code></pre>
  
  <p>This worked as I expected and it allowed me to memoize <code>fib()</code> like this <code>memoize(this::fib)</code></p>
  
  <p>Then I googled the subject of memoization in Java and found the question: <a href="https://stackoverflow.com/questions/27549864/java-memoization-method">Java memoization method</a> where <code>computeIfAbsent</code> was proposed which is much shorter than my conditional expression.</p>
  
  <p>So my final code which I expected to work was:</p>
  
  <pre><code>public class FibMemo {
      private final Function&lt;Long, Long&gt; memoizedFib = memoize(this::slowFib);
  
      public long fib(long n) {
          return memoizedFib.apply(n);
      }
  
      long slowFib(long n) {
          if (n &lt; 2) {
              return n;
          }
  
          return fib(n - 1) + fib(n - 2);
      }
  
      private static &lt;I, O&gt; Function&lt;I, O&gt; memoize(Function&lt;I, O&gt; fn) {
          final Map&lt;I, O&gt; cache = new HashMap&lt;&gt;();
          return in -&gt; cache.computeIfAbsent(in, fn);
      }
  
      public static void main(String[] args) {
          new FibMemo().fib(50);
      }
  }
  </code></pre>
  
  <p>Since I used Java 11, I got:</p>
  
  <pre><code>Exception in thread "main" java.util.ConcurrentModificationException
      at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1134)
      at algocasts.matrix.fibonacci.FibMemo.lambda$memoize$0(FibMemo.java:24)
      at algocasts.matrix.fibonacci.FibMemo.fib(FibMemo.java:11)
      at algocasts.matrix.fibonacci.FibMemo.slowFib(FibMemo.java:19)
      at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1133)
      at algocasts.matrix.fibonacci.FibMemo.lambda$memoize$0(FibMemo.java:24)
  </code></pre>
  
  <p>The problem quickly brought me to the following question which is very similar: <a href="https://stackoverflow.com/questions/28840047/recursive-concurrenthashmap-computeifabsent-call-never-terminates-bug-or-fea">Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or &quot;feature&quot;?</a></p>
  
  <p>except Lukas used ConcurrentHashMap and got never ending loop. In the article related to the question Lukas advised:</p>
  
  <blockquote>
    <p>The simplest use-site solution for this concrete problem would be to not use a ConcurrentHashMap, but just a HashMap instead:</p>
  </blockquote>
  
  <p><code>static Map&lt;Integer, Integer&gt; cache = new HashMap&lt;&gt;();</code></p>
  
  <p>That's exactly what I was trying to do, but did not succeed with Java 11. I found out empirically that HashMap throws ConcurrentModificationException since Java 9 (thanks SDKMAN):</p>
  
  <pre><code>sdk use java 9.0.7-zulu &amp;&amp; javac Test.java &amp;&amp; java Test # throws ConcurrentModificationException
  sdk use java 8.0.202-zulufx &amp;&amp; javac Test.java &amp;&amp; java Test # works as expected
  </code></pre>
  
  <p>Here are the summary of my attempts:</p>
  
  <ul>
  <li>Java 8 &amp;&amp; ConcurrentHashMap -> works if input &lt; 13, otherwise endless
  loop  </li>
  <li>Java 9 &amp;&amp; ConcurrentHashMap -> works if input &lt; 13, hangs if
  input = 14, throws <code>IllegalStateException: Recursive update</code> if input
  is 50 </li>
  <li>Java 8 &amp;&amp; HashMap -> Works! </li>
  <li>Java 9 &amp;&amp; HashMap -> Throws
  <code>ConcurrentModificationException</code> after input >= 3</li>
  </ul>
  
  <p>I would like to know why ConcurrentModificationException gets thrown on attempt to use HashMap as a cache for recursive function? Was it a bug in Java 8 allowing me to do so or is it another in Java > 9 which throws ConcurrentModificationException?</p>