Java：斐波那契使用HashMap还是TreeMap？

Question

我被要求实现一个可以再次重复使用的斐波那契程序。我在下面使用了 Hashmap。只是好奇，我是否应该实际实现 TreeMap 来提高性能？我正在查看资源并继续阅读 Hashmap 的性能更好，Treemap 用于迭代和节省内存。理想的数据结构是什么，或者它重要吗？

public class Fibonacci {

    HashMap<Integer, Integer> map = new HashMap<>() {{
        map.put(0, 0);
        map.put(1, 1);
    }};

    int currentMax = 1;

    public int getFibonacci(int newIndex) {
        if (newIndex > currentMax) {
            for (int i = currentMax + 1; i <= newIndex; i++) {
                int newData = map.get(i - 1) + map.get(i - 2);
                map.put(i, newData);
            }
            currentMax = newIndex;
        }
        
        return map.get(newIndex);
    }
}

注意：我不知道哈希图有多大，因为程序可以多次使用。

Answer 1

我建议两者都不使用，而是使用

int[]

，如果需要的话将大小加倍。

理由：

1. 自动（取消）装箱需要时间
2. 插入地图需要时间。指定为

   O(1)

   ，但实际成本可观
3. 加倍策略保证插入

   n

   的

   O(n)

   元素的摊余成本（我们不能做得更好，添加

   n

   元素将始终具有

   O(n)

   的基线成本，它与的插入成本相同

   ArrayList

   （

   docs.oracle.com

   ））。

将它们放在一起得出以下用于计算第

n

个斐波那契数的线性时间算法：

class Scratch {
  public static final int INITIAL_CACHE_SIZE = 8;
  private static int[] cache = new int[INITIAL_CACHE_SIZE];
  private static int currentMax = 1;

  static {
    cache[1] = 1;
  }

  public static void main(String[] args) {
    System.out.printf("fib(10) = %d%n", fib(10));
    System.out.printf("fib(20) = %d%n", fib(20));
    System.out.printf("fib(30) = %d%n", fib(30));
    System.out.printf("fib(40) = %d%n", fib(40));
  }

  static int fib(int n) {
    if (n < 0) {
      throw new IllegalArgumentException("n must be >= 0");
    }
    if (n <= currentMax) {
      return cache[n];
    }
    if (n >= cache.length) {
      int newSize = calculateNewSize(n);
      resizeCache(newSize);
    }
    for (int index = currentMax + 1; index <= n; ++index) {
      cache[index] = cache[index - 1] + cache[index - 2];
    }
    if (currentMax < n) {
      currentMax = n;
    }
    return cache[n];
  }

  private static int calculateNewSize(int n) {
    int newSize = cache.length;
    while (newSize < n) {
      newSize *= 2;
    }
    return newSize;
  }

  private static void resizeCache(int newSize) {
    int[] newCache = new int[newSize];
    System.arraycopy(cache, 0, newCache, 0, cache.length);
    cache = newCache;
  }
}

ideone.com

示例