java library similar to c++ map

Question

To find nth fibonacci number using memoization I found one code which uses map in c++.

I have tried to convert this code in java but it fails .

code in c++:

#include <bits/stdc++.h>   

typedef long long int ll;  

map<ll, ll> mp;  
ll M = 1000000007;       

long long fibonacci(long long n) {  
   if (mp.count(n))return mp[n];  
   long long k=n/2;  
   if (n%2==0) {   
      return mp[n] = fibonacci(k)*(fibonacci(k+1)+fibonacci(k-1)) % M;  
    } else {   
       return mp[n] = (fibonacci(k+1)*fibonacci(k+1) + fibonacci(k)*fibonacci(k)) % M;  
    }  
 }  

 int main()  
{  
   mp[0]=mp[1]=1;  
   ll t;  
   scanf("%lld",&t);
   printf("%lld\n",fibonacci(t));  
}   

I have tried same code in java using HashMap.

code in java:

static HashMap<Long,Long> hm=new HashMap<Long,Long>();

static long  f(long n) {
  if (hm.containsKey(n)) return hm.get(n);
  long k=n/2;
  if (n%2==0) {
     return hm.put(n,f(k)*(f(k+1)+f(k-1)) % M);        
  } else { 
     return hm.put(n, (f(k+1)*f(k+1) + f(k)*f(k)) % M);
   }
 }



  public static void main(String[] args) throws IOException {
    hm.put(1L,1L);
    hm.put(0L,1L);
    long b=f(2L);
  }

but this code in java gives StackOverflowError.

I have tried this code using LinkedHashMap and TreeMap in java both gives same error.

Which class I have to use which works same as map in c++?

Please someone explain how map work in c++.

EDIT
look at the output of code in java and c++
c++: c++ code
java: java code

Answer 1

To memorize all the possible fibonacci numbers which fit into a long you can use a simple array.

static final int[] FIB = new int[100_000_000];
static final intM = 1000000007;

static {
    long start = System.currentTimeMillis();
    FIB[1] = FIB[2] = 1;
    for (int i = 3; i < FIB.length; i++) {
        int l = FIB[i - 1] + FIB[i - 2];
        while (l >= M)
            l -= M;
        FIB[i] = l;
    }
    long time = System.currentTimeMillis() - start;
    System.out.printf("Took %.3f seconds to build table of %,d fibonacci values%n", time/1e3, FIB.length);
}

public static long fibonacci(int n) {
    return FIB[n];
}

public static void main(String[] args) {
}

prints

Took 0.648 seconds to build table of 100,000,000 fibonacci values

This would use 400 MB of memory for the array which is more efficient than any map implementation.

Answer 2

A StackOverflowError happens when you have too many methods calls stacked, it's thrown by the virtual machine. It's not a HashMap problem at all.

From the docs:

Thrown when a stack overflow occurs because an application recurses too deeply.

You could either increase the stack size of your JVM by using the -Xss flag, or you could try to use a better algorithm, or review this one to check if it's really equivalent to the c++ version... But either way, I think you're just overcomplicating this, there are simpler ways of getting the same result.

You can also check this question on how a recursive fibonacci method looks like.

---

EDIT: Check this link, it shows how you can get the nth number using memoization and Java.

Also, check this question, there are lots of answers with different methods on how to get a large nth fibonacci number.

---

Another way of doing this

Use a List<Long> as a cache.

private static List<Long> cache = new ArrayList<Long>();

/*
 * Java Program to calculate Fibonacci numbers with memorization
 * This is quite fast as compared to previous Fibonacci function
 * especially for calculating factorial of large numbers.
 */
public static int improvedFibo(int number){
    Integer fibonacci = cache.get(number);
    if(fibonacci != null){
        return fibonacci; //fibonacci number from cache
    }
    //fibonacci number not in cache, calculating it
    fibonacci = fibonacci2(number);

    //putting fibonacci number in cache for future request 
    cache.put(number, fibonacci); 
    return fibonacci;
}

Taken from here.

You can also check this question for another example.