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

Question

Is there a java data-structure that can store an arbitrary large number of elements? Let's suppose that the elements are also BigIntegers for simplicity.

Theoretically using an array with a BigInteger index would be OK since setting and getting values will be the only operations required. But an array cannot contain more than Integer.MAX_VALUE.(Or even less depending on the VM dependent, see this question).

To implement such a data structure a simple (naive) solution would be to create one from a LinkedList and have an external BigInteger counter.

Something like that:

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

}

However it should be possible to make several optimizations. For instance not initializing elements that have not been set or get, or caching frequently requested elements. In that sense a Map implementation could also be a good implementation. However maps return an int size and I could not find a reference on whether a map can handle more than Integer.MAX_VALUE. I searched for TreeMap and HashMap. Is there such an arbitrary size data structure available?

Some other constraints. 1 - The memory size is not considered as a constraint, however saving memory would be a plus. 2 - The data-structure would preferably be stored in memory, so databased backed solutions are not considered. For instance the above could also be implemented by saving the values in a database with the index of the element converted to a String and used as a String key.

Do you actually have a situation where you need to hold over 2 billion items in of some kind in memory or is this some kind of a theoretical question? — Joni, Apr 04 '20 at 19:45
Actually both. It is based on a true situation, where however the memory would not be enough. But it is interesting to see if there is something like that . — Spyros K, Apr 05 '20 at 08:00

score 0 · Accepted Answer · answered Aug 24 '20 at 04:27

The motivation behind the question was to identify a simple solution without relying to an in memory database. E.g when a 64bit array would be a good solution. An in memory database offers more features that may not be needed and perhaps can be avoided.

Without any answers, and not having found a solution that would be easy to implement and efficient myself I would say that using an in memory database is the simplest way to go. A list of in memory databases can be found in Wikipedia.

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

1 Answers1