0

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.

Improve this question
9
  • 3
    I would use neither and opt to use an int[] as cache instead. Commented Oct 22, 2023 at 18:44
  • 1
    That is what System::arraycopy (docs.oracle.com) is for. Commented Oct 22, 2023 at 18:47
  • So I would keep copying the whole array, everytime the program was called eg 50 times, where a user keeps increasing max index? I feel like just adding a single entry would be better, can you explain further, if I'm incorrect? thanks @Turing85 Commented Oct 22, 2023 at 18:48
  • The typical approach is doubling the size of the array, amortized costs is O(log(n)). Commented Oct 22, 2023 at 18:49
  • interesting? can you write an answer, and I can send points? so we double the size of array everytime max is increased? and yep, array is faster than hashmap,thanks Commented Oct 22, 2023 at 18:50

1 Answer 1

Reset to default
3

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

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

thanks, one last question, if I didn't use array int[] with doubling? what would be the second best choice out of the two (HashMap or TreeMap) ?
I don't know. Why not try it out?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.