为什么这个 Memoized Fibonacci 的实现不起作用？

Question

class Fib {
  public Map<Integer, Integer> memo = new HashMap<Integer, Integer>();

  Fib() {
    memo.put(0, 1);
    memo.put(1, 1);
  }

  public Integer fibonacciMemoized(Integer n) {
    if (memo.containsKey(n)) {
      return memo.get(n);
    } else {
      int fibo = fibonacciMemoized(n-1) + fibonacciMemoized(n-2);
      return memo.put(n, fibo);
    }
  }
}

这段代码给出了NullPointerException。但是，如果我将最后一个 return 语句分解为：

 memo.put(n, fibo);
 return fibo;

然后就可以了。怎么来的？ put() return 不是放入地图的值吗？

Answer 1

不，它没有。您可以在 JavaDocs 中阅读，其中明确指出 put returns 与键关联的 previous 值，或者 null 如果没有键映射。

V put(K key, V value)

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)

Parameters:
key - key with which the specified value is to be associated
value - value to be associated with the specified key

Returns: the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key, if the implementation supports null values.)

因此，对于您的代码，必须使用以下内容：

memo.put(n, fibo); // will NOT return the value
return fibo;       // and here it is returned

Answer 2

Map.put returns 给定键的先前值，而不是您现在分配给它的值。在您的情况下，您会在第一次遇到每个键时调用 put，因此它将 return null.

为什么这个 Memoized Fibonacci 的实现不起作用？

Why does this Implementation of Memoized Fibonacci not work?

java

dictionary

hashmap

fibonacci