由于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)

然后,我用Google搜索记忆化的Java中的主题,发现了一个问题:Java的记忆化方法,其中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使用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 IllegalStateException: Recursive update则挂起,如果输入为50则抛出
• Java 8 && HashMap - > Works!
• Java 9 && HashMap - > ConcurrentModificationException输入后输入> = 3

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

Answer 1

ConcurrentModificationException因为slowFib正在修改多个键和值而被抛出.如果您查看Java 9 HashMap.computeIfAbsent()代码,您会发现此处抛出异常:

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()添加了HashMap.get()找不到的modCount在Java 9中添加了检查的条目:

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