Java 任意大量元素且大于 Integer.MAX_VALUE 的数据结构

Question

有没有java数据结构可以存储任意数量的元素？为简单起见，我们假设元素也是 BigIntegers。

理论上使用带有 BigInteger 索引的数组是可以的，因为设置和获取值将是唯一需要的操作。但是数组不能包含超过 Integer.MAX_VALUE。（或者甚至更少，具体取决于 VM，请参见 this question）。

要实现这样的数据结构，一个简单（天真的）解决方案是从 LinkedList 创建一个并具有外部 BigInteger 计数器。

类似的东西：

class MyArray{

   private final BigInteger size;
   private final LinkedList<BigInteger> list;

   MyArray(BigInteger size){
      //ommited for simplicity
   }

   public BigInteger get(BigInteger index){
      //ommited for simplicity
      //traverse the LinkedList using a BigInteger counter and get the element
   }

   public void set(BigInteger index,BigInteger element){
       //ommited for simplicity. 
      //traverse the LinkedList using a BigInteger counter and set the element
   }

   public BigInteger getSize(){
       return size;
   }

}

不过，应该可以进行多项优化。例如，不初始化尚未设置或获取的元素，或缓存经常请求的元素。从这个意义上说，Map 实现也可能是一个很好的实现。但是映射 return 一个 int 大小，我找不到关于映射是否可以处理超过 Integer.MAX_VALUE 的参考。我搜索了 TreeMap 和 HashMap。有这种任意大小的数据结构可用吗？

一些其他限制。 1 - 内存大小不被视为约束，但节省内存将是一个优势。 2 - 数据结构最好存储在内存中，因此不考虑数据库支持的解决方案。例如，上述内容也可以通过将值保存在数据库中来实现，并将元素的索引转换为字符串并用作字符串键。

Answer 1

问题背后的动机是确定一个不依赖于内存数据库的简单解决方案。例如，当 64 位数组是一个很好的解决方案时。内存数据库提供了更多可能不需要并且也许可以避免的功能。

没有任何答案，也没有找到一个易于实施和高效的解决方案，我会说使用内存数据库是最简单的方法。 in memory databases 的列表可以在维基百科中找到。

Java 任意大量元素且大于 Integer.MAX_VALUE 的数据结构

Java data structure for an arbitrary large number of elements and larger than Integer.MAX_VALUE

java

arrays

data-structures

collections

arbitrary-precision