Alternatives for problems involving very large array indexing storing very large values

Question

Please suggest some alternatives for resolving problems in which brute force solution is using Arrays with very large index and storing very large values(Very large means beyond the range of INT). I am using Java to solve this problem.

Sample problem: Putting large no of pebbles in a very large group of buckets, and then calculating average pebbles in each bucket.

One way is to declare a big array and keep placing pebbles according to the indexes specified by user and then calculating average. But this way we'll be using a large space for such array.

Answer 1

If the array is sparse, one option could be a Map of index to value.

If all the data can still fit into memory, the index is just beyond the range of int, you could consider an array of arrays. The primary array can contain arrays of size let's say 1000000000. The 0th index in this array would contain values 0-999999999, the 1st index, 1000000000-1999999999, etc.

Another alternative is using files. A RandomAccessFile might help to do this manually, or there may be some libraries that give you an array interface and takes care of the file I/O behind the scenes.