Начиная с Java 9 HashMap.computeIfAbsent () генерирует исключение ConcurrentModificationException при попытке запоминания результатов рекурсивной функции - PullRequest
Новая
       10

Начиная с Java 9 HashMap.computeIfAbsent () генерирует исключение ConcurrentModificationException при попытке запоминания результатов рекурсивной функции

0 голосов
/ 22 февраля 2019

Сегодня я узнал из некоторого курса JS, что такое запоминание, и попытался реализовать его на 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 , где 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 () никогда не прекращается.Ошибка или «фича»?

, за исключением того, что Лукас использовал ConcurrentHashMap и получил бесконечный цикл.В статье, связанной с вопросом, Лукас посоветовал:

Самым простым решением для конкретной проблемы использования сайта было бы не использовать ConcurrentHashMap, а вместо этого просто HashMap:

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, в противном случае бесконечный цикл </li>
  • Java 9 && ConcurrentHashMap -> работает, если ввод<13, зависает, если input = 14, выдает <code>IllegalStateException: Recursive update, если input 50
  • Java 8 && HashMap -> Работает!
  • Java 9 && HashMap -> Throws ConcurrentModificationException после ввода> = 3

Я хотел бы знать, почему возникает исключение ConcurrentModificationException при попытке использовать HashMap в качестве кэша для рекурсивной функции?Была ли это ошибка в Java 8, позволяющая мне сделать это, или это другая ошибка в Java> 9, которая вызывает исключение ConcurrentModificationException?

1 Ответ

0 голосов
/ 22 февраля 2019

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 () добавляет запись о том, что HashMap.get () не находит , которая добавила modCountпроверьте в Java 9: ​​

Если функция, предоставленная для computeIfAbsent, добавляет элементы в тот же HashTable, для которого вызывается функция, и внутренняя таблица увеличивается из-за этого, новая запись будет добавлена ​​внеправильное место во внутренней таблице карты, что делает ее недоступной.

...