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 .

You can do with with a memory mapped file to provide the storage with one bit per boolean you need 128 GB of disk. Obvious you would like to have the same amount of memory, but it will work without this much (but at a reduced speed) — Peter Lawrey, Mar 26 '13 at 07:56

T.J. Crowder · Answer 1 · 2013-03-26T07:07:57.717

11

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.

edited Mar 26 '13 at 07:07

answered Mar 26 '13 at 06:50

T.J. Crowder

1,031,962
187
1,923
1,875

1

Actually, you can create a `LinkedList` that is larger than that. But you would not want to use `get(int)` on it :-) – Stephen C Mar 26 '13 at 06:53
1

@StephenC: Have you ever tried doing it? I have a strong suspicion it would break. In any case, the memory use would be huge (all those double-linking pointers). – T.J. Crowder Mar 26 '13 at 06:56
2

I haven't tried it. But the List javadoc for `size()` specifically allows for lists > MAX_INT – Stephen C Mar 26 '13 at 07:05
@StephenC: Oooh, so it does. – T.J. Crowder Mar 26 '13 at 07:06
Thanks :) Got the idea.Taking a diff. approach. – Tahniat Ashraf Mar 26 '13 at 07:44

NPE · Accepted Answer · 2013-03-26T06:55:30.353

8

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.

edited Mar 26 '13 at 06:55

answered Mar 26 '13 at 06:50

NPE

486,780
108
951
1,012

2

And even if you did have a system that had that much addressable memory, Java arrays are limited to (2^31 - 1) elements. That limit is even more fundamental. – Stephen C Mar 26 '13 at 06:55
@StephenC: That's why I say "data structure" rather than "array". One could easily create an array of arrays or some such, but that would just postpone the inevitable. – NPE Mar 26 '13 at 06:56
1

2,147,483,647 word-sized entries is only about 4G of memory. Lots of systems have that. Not saying I disagree with your *main* point, though. :-) – T.J. Crowder Mar 26 '13 at 06:57
@T.J.Crowder: Where did this number come from? The OP is talking about 1,000,000,000,000 elements. – NPE Mar 26 '13 at 06:58
Actually, you said "array". – Stephen C Mar 26 '13 at 06:59
@NPE: Sorry, quite true. That number is `Integer.MAX_VALUE`. I was focussing on an array exceeding that, ignoring the sample number. But again, you're quite right to use the sample value from the OP. – T.J. Crowder Mar 26 '13 at 06:59

score 1 · Answer 3 · answered Mar 26 '13 at 06:52

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.

Yan Khonski · Answer 4 · 2016-03-25T11:04:09.100

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!!!:)

score 0 · Answer 5 · edited May 23 '17 at 12:17

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

How to make a big array in java

5 Answers5

Linked