由于Java 9 HashMap.computeIfAbsent()在尝试记录递归函数结果时引发ConcurrentModificationException [英] Since Java 9 HashMap.computeIfAbsent() throws ConcurrentModificationException on attempt to memoize recursive function results

问题描述

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

Today I learned from some JS course what memoization is and tried to implement it in Java. I had a simple recursive function to evaluate n-th Fibonacci number:

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

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

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

Then I decided to use HashMap in order to cache results of recursive method:

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

这按我预期的那样工作，它使我能够像这样memoize(this::fib)

This worked as I expected and it allowed me to memoize fib() like this memoize(this::fib)

然后，我在Java中搜索了记忆的主题，并发现了一个问题: Java记忆方法其中，<提出了c2>，它比我的条件表达式短得多.

Then I googled the subject of memoization in Java and found the question: Java memoization method where computeIfAbsent was proposed which is much shorter than my conditional expression.

所以我期望的最终代码是:

So my final code which I expected to work was:

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以来，我得到了:

Since I used Java 11, I got:

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)

这个问题很快使我想到了一个非常相似的以下问题:

The problem quickly brought me to the following question which is very similar: Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

除了Lukas使用ConcurrentHashMap之外，循环永无休止.在与Lukas建议的问题有关的文章中:

except Lukas used ConcurrentHashMap and got never ending loop. In the article related to the question Lukas advised:

针对此具体问题的最简单的使用现场解决方案是不使用ConcurrentHashMap，而只使用HashMap:

The simplest use-site solution for this concrete problem would be to not use a ConcurrentHashMap, but just a HashMap instead:

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

这正是我想要做的，但是在Java 11上没有成功.我凭经验发现，自Java 9以来，HashMap抛出ConcurrentModificationException(感谢SDKMAN):

That's exactly what I was trying to do, but did not succeed with Java 11. I found out empirically that HashMap throws ConcurrentModificationException since Java 9 (thanks 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->有效！
• Java 9&& HashMap->抛出 ConcurrentModificationException输入> = 3
后

• Java 8 && ConcurrentHashMap -> works if input < 13, otherwise endless loop
• Java 9 && ConcurrentHashMap -> works if input < 13, hangs if input = 14, throws IllegalStateException: Recursive update if input is 50
• Java 8 && HashMap -> Works!
• Java 9 && HashMap -> Throws ConcurrentModificationException after input >= 3

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

I would like to know why ConcurrentModificationException gets thrown on attempt to use HashMap as a cache for recursive function? Was it a bug in Java 8 allowing me to do so or is it another in Java > 9 which throws ConcurrentModificationException?

推荐答案

ConcurrentModificationException的原因是slowFib正在修改多个键和值.如果您查看

ConcurrentModificationException is thrown because slowFib is modifying multiple keys and values. If you look at Java 9 HashMap.computeIfAbsent() code you will find that the exception is thrown here:

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

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

Each invocation of slowFib attempts to modify values mapped to keys n-1 and n-2.

在Java 8 HashMap.computeIfAbsent()代码中未执行modCount检查.这是Java 8中的错误，根据 JDK- 8071667 HashMap.computeIfAbsent()添加了HashMap.get()未找到的条目，该条目在Java 9中添加了modCount检查:

The modCount check is not performed in Java 8 HashMap.computeIfAbsent() code. This is a bug in Java 8, your approach doesn't work in all cases as per JDK-8071667 HashMap.computeIfAbsent() adds entry that HashMap.get() does not find which added the modCount check in Java 9:

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

If the function supplied to computeIfAbsent adds items to the same HashTable on which the function is called from and the internal table is enlarged because of this, the new entry will be added to the wrong place in the Map's internal table making it inaccessible.

这篇关于由于Java 9 HashMap.computeIfAbsent()在尝试记录递归函数结果时引发ConcurrentModificationException的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！