类似于c++ map的java库

Question

为了使用内存法找到第 n 个斐波那契数，我找到了一个使用 C++ 中的 map 的代码。

我试图用 java 转换这段代码，但失败了。

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

我已经尝试使用 HashMap 在 java 中编写相同的代码。

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

但是 java 中的这段代码给出了 StackOverflowError。

我已经在 java 中使用 LinkedHashMap 和 TreeMap 尝试了这段代码，但都给出了相同的错误。

我必须使用哪个类，其工作方式与 C++ 中的 map 相同？

请有人解释一下 map 在 C++ 中是如何工作的。

编辑
查看 java 和 c++
代码的输出C++:c++ code
java: java code

Answer 1

要记住适合 long 的所有可能的斐波那契数，您可以使用一个简单的数组。

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

打印

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

这将为数组使用 400 MB 的内存，这比任何映射实现都更高效。