由于Java9中的HashMap.ComputeIFEstant（）在尝试记忆递归函数结果时抛出ConcurrentModificationException

Question

今天我从一些JS课程中学习了什么是memoization，并尝试用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;
        }
    };
}

这正如我所期望的那样起作用了，它允许我像Thismemoize(This::fib)那样，将fib()进行memoize(This::fib)

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

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

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);
    }
}

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,而只使用HashMap：

静态映射 缓存=新HashMap<>()；

这正是我想要做的，但在Java11中没有成功。我根据经验发现，HashMap从Java9开始抛出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

null

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

Answer 1

引发ConcurrentModificationException是因为SlowFib正在修改多个键和值。如果您查看Java9hashmap.computeIFENTACE()代码，您会发现在下面抛出异常：

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

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

在Java8HashMap.ComputeIfAstent()代码中不执行modcount检查。这是Java 8中的一个bug，您的方法并不能在所有情况下都起作用，因为根据JDK-8071667，hashmap.computeIFEstant（）添加了hashmap.get（）没有找到的条目，该条目在Java 9中添加了modcount检查：

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