Когда я использую computeIfAbsent для вычисления чисел Фибоначчи, hashmap size () возвращает неверное значение - PullRequest
Новая
       13

Когда я использую computeIfAbsent для вычисления чисел Фибоначчи, hashmap size () возвращает неверное значение

0 голосов
/ 01 января 2019

У меня есть следующий код: 

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class DynamicFib
{
    private static Map<Integer, BigInteger> myMap = new HashMap<>();

    static {
        myMap.put(0, BigInteger.ZERO); //fibonacci(0)
        myMap.put(1, BigInteger.ONE); //fibonacci(1)
    }

    public static BigInteger fibonacci(int x)
    {
//        System.out.println("x = [" + x + "]");
        return myMap.computeIfAbsent(x, n -> fibonacci(n - 2).add(fibonacci(n - 1)));
    }

    public static void main(String[] args)
    {

        System.out.println("l = " + fibonacci(25));
        System.out.println("myMap = " + myMap);
        System.out.println("myMap = " + myMap.keySet().size());

    }

}

консольный вывод: 

l = 75025

myMap = {0=0, 1=1, 2=1, 3=2, 4=3, 5=5, 6=8, 7=13, 8=21, 9=34, 10=55, 11=89, 12=144, 13=233, 14=377, 15=610, 16=987, 17=1597, 18=2584, 19=4181, 20=6765, 21=10946, 22=17711, 23=28657, 24=46368}

myMap = 31

памятка содержит только 25 элементов, но размер возвращается 31. Как?это ошибка в реализации хэш-карты?

Я изменил hashmap на ConcurrentHashMap, он просто зависает, если я спрашиваю 9-ое или более число Фибоначчи.

Но это работает и правильно возвращает число Фибанокки даже для1000!

1 Ответ

0 голосов
/ 02 января 2019

Да, HashMap.computeIfAbsent(K, Function) Javadoc отмечает, что вам не следует изменять карту во время вычислений.Если вы измените метод, чтобы сначала проверить, содержит ли карта x в качестве ключа, а затем вернуть как 

public static BigInteger fibonacci(int x) {
    if (!myMap.containsKey(x)) {
        myMap.put(x, fibonacci(x - 2).add(fibonacci(x - 1)));
    }
    return myMap.get(x);
}

Тогда вы увидите (как я думаю, вы ожидали) 

l = 75025
myMap = {0=0, 1=1, 2=1, 3=2, 4=3, 5=5, 6=8, 7=13, 8=21, 9=34, 10=55, 11=89, 12=144, 13=233, 14=377, 15=610, 16=987, 17=1597, 18=2584, 19=4181, 20=6765, 21=10946, 22=17711, 23=28657, 24=46368, 25=75025}
myMap = 26
...