Java: Fibonacci use HashMap or TreeMap?

Question

I was asked to implement a Fibonacci program that can be reused again. I used a Hashmap below. Just curious, if I should have actually implemented a TreeMap to help performance? I was looking through resources and keep reading that Hashmap is better for performance, Treemap is for iterating and memory saving. What would be the ideal data structure, or does it matter?

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);
    }
}

Note: I do not know how big the hashmap will be, as program can be used multiple times.

Answer 1

I would suggest using neither and use an int[] instead, doubling the size if needed.

Rationale:

1. Auto(un)boxing costs time.
2. The insertion to the map costs time. It is specified as O(1), but the actual cost is noticeable.
3. The doubling-strategy guarantees amortized cost for inserting n elements of O(n) (we cannot do better, adding n elements will always have a baseline cost of O(n), it is the same as the insert costs of ArrayList (docs.oracle.com)).

Putting it all together leads to the following linear time algorithm for calculating the n-th Fibonacci-number:

class Scratch {
  public static final int INITIAL_CACHE_CAPACITY = 8;
  private static int[] cache = new int[INITIAL_CACHE_CAPACITY];
  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) {
      resizeCache(n);
    }
    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 void resizeCache(int minCapacity) {
    int newCapacity = calculateNewCacheCapacity(minCapacity);
    int currentCapacity = cache.length;
    if (newCapacity < currentCapacity) {
      throw new IllegalArgumentException("newCapacity must be larger than the current capacity");
    }
    int[] newCache = new int[newCapacity];
    System.arraycopy(cache, 0, newCache, 0, currentCapacity);
    cache = newCache;
  }
  
  
  private static int calculateNewCacheCapacity(int minCapacity) {
    int newSize = cache.length;
    while (newSize <= minCapacity) {
      newSize *= 2;
    }
    return newSize;
  }
}

ideone.com example