What are the characteristics of ArrayList as a common set type in java that we need to understand? Based on the jdk1.8 source code, this article will step by step list the important points of ArrayList.

Randomaccess random access interface

The implementation relationship of ArrayList inheritance is as follows:

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

From this figure, we can see that ArrayList implements the RandmoAccess interface, which is as follows:

    public interface RandomAccess {
    }

In fact, there is no implementation in the RandmoAccess interface, which only means that the class implementing the interface can provide fast access.

2 array type at the bottom

ArrayList implements the RandmoAccess interface representative to be able to access quickly. In fact, the fast access function of ArrayList is realized by arrays. The following are the two most important properties in ArrayList:

    //Where ArrayList actually stores data
    transient Object[] elementData; 
    //Size of ArrayList
    private int size;

Let's look at the default construction method of ArrayList:

     public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
     }

The default constructor assigns the elementData property to defaultaccess? Empty? elementData, where the defaultaccess? Empty? elementData property is an empty array

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

Next, let's look at the add and get methods in ArrayList:

    public boolean add(E e) {
        //Confirm whether to expand
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    public E get(int index) {
        //Check for out of line
        rangeCheck(index);

        return elementData(index);
    }

You can see that the underlying Arraylist is operated by arrays.

3 lazy initialization

When ArrayList uses the default constructor to create a class, it creates an empty array. How can ArrayList use the add method to store data? We can look at the source code of the securecapacityinternal method in the add method in detail:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //The value of the default menu capacity constant is 10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        //Record modification times
        modCount++;

        if (minCapacity - elementData.length > 0)
            //Capacity expansion method
            grow(minCapacity);
    }
    

It can be seen from the above source code that when ArrayList is an empty array, a default size of 10 will be given, and then the ArrayList will be expanded in the expansion method. Therefore, when the ArrayList is initialized with the default constructor, the array size will not be initialized immediately, but will not be initialized until the add method is called, and the initialization size is 10.

4-bit operation 1.5 times capacity expansion

We can check the grow th method of ArrayList to see how ArrayList is actually expanded:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //Bit operation 1.5x capacity expansion
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //Determine if minCapacity exceeds the maximum integer value
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

The above code is divided into the following steps:

1. First, the original array is expanded by 1.5 times with bit operation to get a new expansion value, newCapacity.
2. Then the new capacity expansion value newCapacity is compared with the actual capacity expansion value minCapacity. If the new capacity is larger than minCapacity, newCapacity is used. Otherwise, minCapacity is used to determine whether minCapacity is legal. The value thus obtained is a final capacity expansion value.
3. Finally, the final selected expansion value is expanded by means of Arrays.copyOf method.