由于 Java 9 HashMap.computeIfAbsent() 在尝试记忆递归函数结果时抛出 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;
        }
    };
}

这如我所料，它让我可以像这样记忆 fib() memoize(this::fib)

然后我在 Java 中搜索了记忆的主题，发现了问题：Java memoization method where computeIfAbsent where proposed which is much short than my conditional expression.

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

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

因为我使用了Java11，所以我得到：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1134)
    at algocasts.matrix.fibonacci.FibMemo.lambda$memoize[=15=](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[=15=](FibMemo.java:24)

这个问题很快让我想到了以下非常相似的问题：

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

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。我凭经验发现 HashMap 抛出 ConcurrentModificationException 因为 Java 9（感谢 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

我想知道为什么在尝试使用 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 检查

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.

Answer 2

您可以自己滚动：

public static <K, V> V computeIfAbsent(
    Map<K, V> cache, 
    K key,
    Function<? super K, ? extends V> function
) {
    V result = cache.get(key);

    if (result == null) {
        result = function.apply(key);
        cache.put(key, result);
    }

    return result;
}

此方法假定您没有 null 值。如果这样做，只需更改逻辑以使用 Map.containsKey()

此访问通过再次使缓存值检索和计算值非原子化来解决此问题，Map::computeIfAbsent 试图避免这种情况。 IE。通常的竞争条件问题再次出现。当然，这对你来说可能没问题。

Answer 3

这个怎么样？虽然不确定性能...

public class Fibonacci {

  private static final Map<Integer, Integer> memoized = new ConcurrentSkipListMap<>(Map.of(1,1,2,1));

  public static int fib(int n) {
    return memoized.computeIfAbsent(n, x -> fib(x - 2) + fib(x - 1));
  }

  public static void main(String[] args) {
    System.out.println(fib(12));
  }

}

Answer 4

您可以使用ConcurrentSkipListMap

它是一个 thread-safe 映射，在使用 computeIfAbsent() 时不会通过 ConcurrentModificationException 集合的递归和迭代。

参考：

https://dzone.com/articles/avoid-recursive-invocation-on-computeifabsent-in-h

由于 Java 9 HashMap.computeIfAbsent() 在尝试记忆递归函数结果时抛出 ConcurrentModificationException

Since Java 9 HashMap.computeIfAbsent() throws ConcurrentModificationException on attempt to memoize recursive function results

java

recursion

concurrenthashmap

java-9