40

As far as I know, when we are creating an ArrayList:

ArrayList<String> list = new ArrayList<String>(SIZE);

The JVM reserves for it a contiguous part of memory. When we are adding new elements into our list, when number of elements reaches 75% of SIZE it reserves a new, contiguous part of memory and copies all of the elements.

Our list is getting bigger and bigger. We are adding new objects and the list has to be rebuilt once again.

What happens now?

The JVM is looking for a contiguous segment of memory, but it does not find enough space.

The Garbage Collector can try to remove some unused references and defragment memory. What happens, if the JVM is not able to reserve space for new instance of list after this process?

Does it create a new one, using maximal possible segment? Which Exception will be thrown?

I read this question Java: How ArrayList manages memory and one of the answers is:

Reference doesn't consume much space. but anyhow, some of space is used. When array is getting bigger, it could be a problem. We cannot also forget that we have got another things which use memory space.

Community
  • 1
  • 1
ruhungry
  • 4,506
  • 20
  • 54
  • 98
  • 13
    `ArrayList` doesn't actually resize when 75% full; it waits until it is completely full and you try to add another element. – Russell Zahniser Apr 23 '14 at 13:29
  • Thank you for your comment. I checked an implementation of `ArrayList`. I started from method `add(E e)` and I cannot understand one condition. In method `ensureCapacityInternal(int minCapacity)` there is something like this: `if (minCapacity - elementData.length > 0) {grow(minCapacity);}`. What does it say? What is the meaning of `minCapacity` in this case? Method `grows` does `Arrays.copyOf(elementData, newCapacity)` and it is clear, but why there is a condition which I mentioned before? – ruhungry Apr 23 '14 at 13:53
  • If you look in, for example, the `addAll(Collection c)` method, you will see that it calls `ensureCapacity(size() + c.size())`. So `minCapacity` is the minimum capacity needed to hold what I want to put in the list. – Russell Zahniser Apr 23 '14 at 13:58
  • Thank you. I took a look at `ArrayList` and `HashMap` implementation. I do not understand 2 things. **QUESTION 1.** Why `DEFAULT_CAPACITY` is different for both of them (HashMap=11, ArrayList=10)? **QUESTION 2.** Why for HashMap, `DEFAULT_LOAD_FACTOR` is defined and `= 0.75f` and in case of `ArrayList` we are waiting untill our array is full? – ruhungry Apr 23 '14 at 15:17
  • 1
    @GirlyGirl Q1 - Hash Table implementations typically use prime numbers for table size. Q2 - You don't want your HashMap to become 100% full as it decreases how quickly it can access items. – C.B. Apr 23 '14 at 15:39
  • 1
    @GirlyGirl [(smaller load factor, less collisions)](http://en.wikipedia.org/wiki/Hash_table) – C.B. Apr 23 '14 at 15:46

5 Answers5

43

If JVM is not able to allocate requested amount of memory it'll throw

OutOfMemoryError

That's it. Actually JVM memory allocation has only two possible outcomes:

  1. Application is given requested amount of memory.
  2. JVM throws OutOfMemoryError.

There is no intermediate options, like some amount of memory is allocated.

It has nothing to do with ArrayList, it's a JVM issue. If you asking whether ArrayList somehow manages this situation in a special way - then answer is "No, it does not." It just tries to allocate amount of memory it needs and lets JVM think about the rest.

Denis Kulagin
  • 8,472
  • 17
  • 60
  • 129
  • 12
    `OutOfMemoryError` doesn't cause the JVM to exit. It is simply a subtype of `java.lang.Error`. It will unwind the stack of the thread it is raised in until it is caught. – Dev Apr 23 '14 at 13:22
  • 2
    @Dev You are right. But its called *Error* mostly because there is no much reason to catch it - reviving application after OutOfMemoryError is hardly possible. – Denis Kulagin Apr 23 '14 at 13:24
  • 4
    From Java Documentation: "An Error is a subclass of *Throwable* that indicates serious problems that a reasonable application **should not try to catch**. Most such errors are abnormal conditions." – Denis Kulagin Apr 23 '14 at 13:28
  • 3
    I agree that it is best practice to treat `Error`s a fatal, however the application may try to respond to the error (logging, best-effort cleanup) before exiting. Additionally, in multi-threaded programs an uncaught error may not cause the JVM to exit by itself, it will simply kill the thread it was raised in. – Dev Apr 23 '14 at 13:29
21

In Java, the referrences to the object are stored in the contiguous memory. The actual objects can stay in a non contiguous manner. So for ex your array might have 10 objects, JVM only needs to reserve the memory for the object references, not the objects. So if each reference takes a Byte(approx not the correct value), but each object takes up a KB, and you have an array of 10 elements, JVm will try to reserve contguous memory of only 1*10 B i.e 10 B. The objects can reside in 10 different memory locations totalling 10KB. Remember that both the contiguous and non contiguous memory spaces are for the memory allocated to the thread.

When it needs to resize the array, the JVM tried to find a contiguos array of the newer length. So if you want to resize the array from 10 to 20 elements, it would try to reserve a contiguous space of 20 KB(using the above example). If it finds this space, it will do a copy of the references from the old array to the new array. If it does not find this space, it will try to do a GC . If it still does not find the space it throws an OutofMemoryException.

Therefore, at any time when you are resizing the array, the JVM needs to find a contiguos memory to store referrences of the new sized array. So if you want to extend the array to a size of say 1000 element, and each reference is a byte each , the JVm will try to find a contiguos memory of 1000* 1KB which is 1 MB. If it finds this memory, it will do a copy of the references, and mark the oldeer contiguos memory for GC , whenever GC runs the next time If it is not able to find the memory , it will try to do a GC, and if it still does not find the contiguos memory , it will throw a Out of memory exception

This is the code in ArrayList which does the resizing. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.ensureCapacity%28int%29

Biswajit_86
  • 3,661
  • 2
  • 22
  • 36
9

This will throw an OutOfMemoryError as soon as there is not enough heap space to allocate the new array.

Garbage collection will always be done before this error is thrown. This will compact memory and eliminate all the arrays of smaller sizes that are no longer used. But there is no way to get around the fact that the old array, the new array, and all the contained objects need to all be in memory at once in order for the old contents to be copied into the new list.

So, if your memory limit is 10 MB, and the array takes up 2 MB and is being sized up to 3 MB, and the strings take up 6 MB, then OOM will be thrown even though after this operation you will only have 3 + 6 = 9 MB in memory. One way to avoid this, if you want to run really close to memory limits with a huge array, is to size the array to the full size to begin with so that it never needs to resize.

Russell Zahniser
  • 16,188
  • 39
  • 30
1

I assume it will run out of memory since there will be no space to use in the case where JVM can extend array size.

user3579257
  • 21
  • 3
0

The very first thing I want to correct is, When we are adding new elements into our list, when number of elements reaches 100% of SIZE it reserves a new, contiguous part of memory and copies all of the elements.

New Size of ArrayList will be:

NewSize of ArrayList = (CurrentSize * 3/2) + 1

But going this way is never recommended, if we have idea how much objects needs to be stored then we can use following constructor of ArrayList:-

ArrayList ar = new ArrayList(int initialCapacity);

If our JVM couldn't specify enough contiguous space on heap for the ArrayList, At runtime we'll get

  • Runtime error: OutOfMemoryError
Abhinavece
  • 119
  • 1
  • 8
  • In about 90% of my work, i'v no idea of the size the ArrayList is going to have, so "never recommended" is false, don't know where you find that ;) – azro Jul 04 '18 at 12:40