Memoized Fibonacci that crashes on Java 9
A hard Java puzzle in the modifying while iterating family. One line below contains a real bug. Try to spot it first, then read why it fails and how to fix it.
Highlighted: line 8. Play this one as a puzzle without the answer.
What is wrong
The mapping function modifies the same HashMap while computeIfAbsent is still running. Since Java 9, HashMap detects this and throws ConcurrentModificationException; before that it could silently corrupt the map. computeIfAbsent must not touch the map from its function.
The fix
How to avoid it next time
Never update a map from inside computeIfAbsent, compute or merge on that same map. Read, compute, then put.
Want the background? Read Map idioms: merge, compute, entrySet in the Java concepts library.
About modifying while iterating
Collections detect structural changes made during iteration and throw ConcurrentModificationException, but only some of the time, and not at all for certain patterns. Removing in a loop is a classic way to skip elements or crash.
In code review: Any call to add or remove on the collection being looped over deserves suspicion. Use Iterator.remove, removeIf, or build a new collection.
More puzzles in this family
Frequently asked questions
What is the bug in "Memoized Fibonacci that crashes on Java 9"?
The mapping function modifies the same HashMap while computeIfAbsent is still running. Since Java 9, HashMap detects this and throws ConcurrentModificationException; before that it could silently corrupt the map. computeIfAbsent must not touch the map from its function. The faulty line is line 8: return memo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2));
How do I fix it?
Replace it with: Long cached = memo.get(n); if (cached != null) return cached; long v = fib(n - 1) + fib(n - 2); memo.put(n, v); return v;. Never update a map from inside computeIfAbsent, compute or merge on that same map. Read, compute, then put.
How do I catch modifying while iterating in code review?
Any call to add or remove on the collection being looped over deserves suspicion. Use Iterator.remove, removeIf, or build a new collection.
Is there a new puzzle every day?
Yes. The daily Spot the Bug puzzle picks one of these snippets for each UTC day, with the difficulty set by the weekday. Your streak is stored only in your browser.