我有以下代码:
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
memo 只有 25 个元素,但 size 返回 31。怎么办?这是 HashMap 实现中的错误吗?
我将 hashmap 更改为 ConcurrentHashMap,如果我要求第 9 个或更多斐波那契数,它就会挂起。
但这有效并正确返回 fibanocci 数字,即使是 1000!
最佳答案
是的,HashMap.computeIfAbsent(K, Function)
Javadoc请注意,您不应在计算期间修改 map 。如果将方法修改为首先检查 map 是否包含 x
作为键然后返回 like
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
关于java - 当我使用 computeIfAbsent 计算斐波那契数时,hashmap size() 返回不正确的值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53998845/