由于Java 9 HashMap.computeIfAbsent（）在尝试记忆递归函数结果时抛出了ConcurrentModificationException。

今天，我从一些JS课程中学到了什么是记忆化，并试图在Java中实现它。我有一个简单的递归函数来评估第n个斐波那契数列：

long fib(long n) {
    if (n < 2) {
        return n;
    }

    return fib(n - 1) + fib(n - 2);
}

然后我决定使用HashMap来缓存递归方法的结果：

private static <I, O> Function<I, O> memoize(Function<I, O> fn) {
    final Map<I, O> cache = new HashMap<>();
    return in -> {
        if (cache.get(in) != null) {
            return cache.get(in);
        } else {
            O result = fn.apply(in);
            cache.put(in, result);
            return result;
        }
    };
}

这像我预期的那样工作，它允许我像这样记忆fib()memoize(this::fib)

然后，我在Google上搜索了Java中的memoization主题，并发现了一个问题：Java memoization方法，其中提出了比我的条件表达式短得多的方法。computeIfAbsent

所以我期望工作的最终代码是：

public class FibMemo {
    private final Function<Long, Long> memoizedFib = memoize(this::slowFib);

    public long fib(long n) {
        return memoizedFib.apply(n);
    }

    long slowFib(long n) {
        if (n < 2) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);
    }

    private static <I, O> Function<I, O> memoize(Function<I, O> fn) {
        final Map<I, O> cache = new HashMap<>();
        return in -> cache.computeIfAbsent(in, fn);
    }

    public static void main(String[] args) {
        new FibMemo().fib(50);
    }
}

由于我使用了Java 11，所以我得到了：

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)

这个问题很快把我带到了下面一个非常相似的问题：递归 ConcurrentHashMap.computeIfAbsent（） 调用永远不会终止。错误或“功能”？

除了Lukas使用CurrentHashMap并获得了永无止境的循环。在与问题相关的文章中，卢卡斯建议：

对于这个具体问题，最简单的使用站点解决方案是不使用 ConcurrentHashMap，而只使用 HashMap：

static Map<Integer, Integer> cache = new HashMap<>();

这正是我想要做的，但在Java 11中没有成功。我从经验上发现，HashMap从Java 9开始就抛出了ConcurrentModificationException（感谢SDKMAN）：

sdk use java 9.0.7-zulu && javac Test.java && java Test # throws ConcurrentModificationException
sdk use java 8.0.202-zulufx && javac Test.java && java Test # works as expected

以下是我尝试的摘要：

• Java 8 && ConcurrentHashMap -> 如果输入< 13，则工作正常，否则无休止循环
• Java 9 && ConcurrentHashMap -> 如果输入< 13，则工作，如果输入 = 14 则挂起，如果输入为 50 则抛出IllegalStateException: Recursive update
• Java 8 && HashMap -> Works！
• Java 9 && HashMap -> 输入后抛出 >= 3ConcurrentModificationException

我想知道为什么ColtleModificationException在尝试使用HashMap作为递归函数的缓存时被抛出？是Java 8中的一个错误允许我这样做，还是Java >9中的另一个错误，它抛出了ConcurrentModificationException？