Java Collections automatic reallocation when size is reached

Question

I'm not sure if I'm using the correct terms, but I am curious how it's determined how much to increase the size of a Collection in Java when it gets full? I've tried searching but I'm not really coming up with anything useful.

So, if I have something like

List l = new ArrayList(1);
l.add("1");
l.add("2");

How does it determine how much to increase the size of the list? Is it always a set value and if so, what is that value? I'd also be interested in this information for BitSet if it differs.

Thanks and let me know if I should clarify any.

Answer 1

it calls ensureCapacity:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

so as you can see the newCapacity is the (oldCapacity * 3) / 2 + 1

Answer 2

The source for ArrayList holds some clues:

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}


/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

This line: int newCapacity = (oldCapacity * 3)/2 + 1; shows the amount by which ArrayList changes.

Answer 3

ArrayList contains an array of objects that grows if the size to ensure that an element can grow in the array.

Inside ArrayList.ensureCapacity() .

Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

The add(E e) calls ensureCapacity()

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

Answer 4

According to the javadoc,

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

So while it's nice that people are posting the JDK source code, it could be different in different versions; there is no guaranteed growth factor.

Answer 5

Usually the capacity is doubled (or multiplied by a constant). This ensures that the time taken to insert a new element is roughly O(n) (independent of the size of n).

Answer 6

It depends on the JDK implementation you are using. I found the following algorithm (used in Apache Harmony):

int increment = size / 2;
if (required > increment) {
    increment = required;
}
if (increment < 12) {
    increment = 12;
}

Means that the size is increased by half of the old size, 12 minimum.

But as I said, this is implementation specific, so all JVM can handle this their own way.

Answer 7

ArrayList capacity increases as needed. When you set the capacity on it, you're setting the initial capacity - you're providing a guess to the constructor so that the collection can have a good initial size. ArrayList != Array.

Answer 8

The ArrayList in Java will never get full, its size will grow when it is full and need to add more data into it.

If you want to ask about low level implementation, which I assume an ArrayList can use an array to contain the data. Then, I think that when the array that the ArrayList holds is full, the ArrayList create a new array with double size and copy all elements from the old array to the new array. But this is my assumption and you need to read the java doc