Initial capacity

ArrayList has several different constructors, each of which has a different initial capacity. Take a quick look at the ArrayList source code for a few private attributes about element storage:

// The default capacity is 10
private static final int DEFAULT_CAPACITY = 10;
// Return the array if the capacity is 0
private static final Object[] EMPTY_ELEMENTDATA = {};
// If the default size is 10, this array is returned
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// An array of elements
transient Object[] elementData;
// Number of elements
private int size;

// Record the number of changes
protected transient int modCount = 0;
// The maximum value of the array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
Copy the code

ArrayList has three constructors, each of which has a different capacity (see JDK source code for details).

  • If no initial capacity is passed in, the default capacity is used and setelementDataforDEFAULTCAPACITY_EMPTY_ELEMENTDATA
  • If the initial capacity is passed in, the value is evaluated. If it is greater than 0, a new Object array is created. If it is equal to 0, it is setelementDataforEMPTY_ELEMENTDATA.
  • Is called if a Collection is passed intoArray()Method turns it into an array and assigns a value toelementData. It will also determine whether its length is 0, if so, setelementDataforEMPTY_ELEMENTDATA.

What exactly does expansion mean?

As you can see, ArrayList has two concepts: capacity, which represents the “capacity” of the array elementData. Size refers to the number of elements stored.

In Java, array operations cannot be out of bounds, so we must ensure that we do not throw an out of bounds exception during insert operations.

How does ArrayList scale up?

At the bottom are these three private methods:

// Add a new one
private Object[] grow() {
	return grow(size + 1);
}

// Ensure capacity expansion to minCapacity or greater than the expected capacity
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

// Calculate the capacity to be expanded based on the expected capacity minCapacity
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // Get the old capacity
    int newCapacity = oldCapacity + (oldCapacity >> 1); // Set the new capacity to 1.5 times the old capacity
    if (newCapacity - minCapacity <= 0) { // If the new capacity is still smaller than the expected capacity
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // If the default capacity is used
            return Math.max(DEFAULT_CAPACITY, minCapacity); // Return the larger values of the default and expected capacities
        if (minCapacity < 0) // overflow // check if desired capacity is out of bounds (int scope)
            throw new OutOfMemoryError();
        return minCapacity; // Return the desired capacity
    }
    // If the new capacity is larger than the expected capacity, determine whether the new capacity is out of bounds
    return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity : hugeCapacity(minCapacity); }Copy the code

The arrays.copyof method is called to extend the array capacity. Here we will focus on the implementation of the last method, newCapacity(int minCapacity).

By default, the new capacity is 1.5 times as large as the original capacity, using bitwise operations to improve efficiency. In general, if the desired capacity is increased by 1.5 times, the value of 1.5 times the old capacity is returned. If it is less than the expected capacity, the expected capacity is returned. There is special treatment for the default capacity 10.

Using the value of 1.5 rather than the desired capacity is to prevent frequent expansion from affecting performance. Imagine if every add operation had to be expanded, performance would be very low.

The above grow method is mainly used for automatic expansion. Users can also call the following methods to manually expand capacity:

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}
Copy the code

Why do I need to manually expand capacity? Imagine if the user already knows that a large number of elements are going to be stored, such as 2000 elements, out of 20. At this point, automatic expansion will be used multiple times. Manual capacity expansion improves performance by expanding capacity to 2000 at a time.

Does ArrayList shrink?

ArrayList does not shrink. Neither the remove method nor the clear method changes the length of the existing array elementData. However, they both set the element at the corresponding location to null so that the garbage collector can reclaim unused elements and save memory.