How to make a big array in java

Question

I want to create a boolean array of a size which the user is going to put as input.For example - The user might put a big number like 1000000000000 ; so then I have to create a boolean array of the size 1000000000000.The problem I am facing is , I cant store the input as int , as it cant hold such a big number - thus I am unable to create the array .Double is an option .I can store the input number as double , but I don't know how to create the array of the size of the double number .This was the idea -

Scanner scanner = new Scanner(System.in);
int target = scanner.nextInt();
boolean [] array_a=new boolean [(target)];

which wont work if target exceeds the int range.Any help is appreciated.

Update : Thanks guys .So you can only create an array of the size of int's max range (which is 2147483648),right?The memory aspect didn't hit me earlier. Going to take a different approach .

Answer 1

You can't create an array in Java that has a size greater than the maximum positive int, because array indexes are int. (The same goes for the various List implementations. You may be able to create one with more entries [a LinkedList, for example], but things like get and size start not quite working right, you could only get at later entries via an iterator [assuming things didn't just plain break], which would take a while.)

It seems unlikely that you really need to create an array of boolean with room for more than 2,147,483,647 entries, but if you really do, you'll have to create multiple arrays and choose the right one by taking the modulus of your index (which will need to be a long). (Or use some non-JDK library, if one exists to do that.) That would take something like 4G of RAM. Feasible, but the odds are pretty high that a different approach entirely would be better.

But 1,000,000,000,000 elements? That would require on the order of 1-2 TB of RAM. As NPE says, if you're not running on a supercomputer, you're not going to have that.

Answer 2

You could create an abstraction, for example array of arrays (you can even modify this).

Object [][] can be boolean or whatever.

class LargeArray {

    private final long size;
    private final int sizeI;
    private final int sizeJ;
    private final Object [][] objects;


    public LargeArray() {
        sizeI = 3;//Any reasonable value;
        sizeJ = Integer.MAX_VALUE;
        objects = new Object [sizeI][sizeJ];
        size = sizeI * sizeJ;
    }

    public long size() {
        return size;
    }

    public Object get(long index) {
         int i = index / sizeJ;
         int j = index % sizeJ;
         return objects[i][j];
    }

    public void set(long index, Object object) {
         int i = index / sizeJ;
         int j = index % sizeJ;
         objects[i][j] = object;
    }
}

You could also change first dimension, say 3. In this case Object [3][Integer.MAX_VALUE], you can create (2^31 -1)*3 = 2,147,483,647 * 3 = 6442450941 elements and you will need (2^31 - 1)*3 * 4 =~ 23 GB RAM, which is actually possible!!!:)

Answer 3

First of all: You really need a good reason to allocate this much memory. As others have said, you may want to rethink the approach.

A few suggestions: Either limit the amount to allocate to some maximum or store it in a file and seek for the data or allocate on an as-needed basis (lazy allocation). If the data is sparse (few actual booleans, but at very widely spread indexes), you are better off with a map. If it's mainly zeroes, consider storing only the ones :)

Second: It's theoretically possible to allocate 8 * the maximum array size booleans if you pack the bits. See this discussion for inspiration: Implementing a C style bitfield in Java

Answer 4

have to create a boolean array of the size 1000000000000. The problem I am facing is , I cant store the input as int

Your problem isn't that. Your main problem is that you won't have enough memory to allocate a data structure with 1,000,000,000,000 elements (even if you overcame the limitations of int indexing).

You'll need to rethink the algorithm.

Answer 5

How about using a HashMap and use long keys and boolean values.

There you have several advantages.
1. You can use indexes within the range of long
2. You don't have to worry about the maximum size of item index that is used. As long as it is a long it will work
3. You don't allocate memory for the entire collection up front. Instead you will only use the memory that you need.