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

Question

今天我从一些JS课程中学到了什么是memoization并尝试用Java实现它。我有一个简单的递归函数来评估第n个Fibonacci数：

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)

然后我用Java搜索了memoization的主题并发现了一个问题：Java memoization method，其中提出了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)

这个问题很快就让我回到了以下非常相似的问题：Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

除了Lukas使用ConcurrentHashMap并且永远不会结束循环。在与Lukas提出的问题有关的文章中：

针对这个具体问题的最简单的使用站点解决方案是不使用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 - >在输入> = 3后抛出ConcurrentModificationException

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

Answer 1

ConcurrentModificationException被抛出，因为slowFib正在修改多个键和值。如果你看一下Java 9 HashMap.computeIfAbsent() code，你会发现这里引发了异常：

int mc = modCount;
V v = mappingFunction.apply(key);
if (mc != modCount) { throw new ConcurrentModificationException(); }

每次调用slowFib都会尝试修改映射到键n-1和n-2的值。

modCount检查不在Java 8 HashMap.computeIfAbsent()代码中执行。这是Java 8中的一个错误，根据JDK-8071667 HashMap.computeIfAbsent() adds entry that HashMap.get() does not find在Java 9中添加了modCount检查，你的方法并不适用于所有情况：

如果提供给computeIfAbsent的函数将项添加到调用函数的同一HashTable并且内部表因此而被放大，则新条目将被添加到Map的内部表中的错误位置，使其无法访问。