Capacity expansion mechanism of ArrayList

Today, let's learn about ArrayList Capacity expansion mechanism of .

1. Let's take a look at ArrayList Construction method of , There are three kinds of

（1） Constructor with initial capacity parameter , Users can define their own capacity

（2） Default constructor , Use initial capacity 10 Construct an empty list ( Parameterless construction )

（3） The construct contains the specified collection List of elements , These elements use the iterator of the collection to return... In order

Source code is as follows ：

    /**
     *  Default initialization size ,10
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     *  Shared empty array instances for empty instances 
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     *  Shared empty array instances for empty instances of default size . We distinguish it from empty element data , To see how much to add when adding the first element 
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList  Size 
     */
    private int size;

    /**
     *  Constructor with initial capacity parameter .（ The user specifies the capacity ）
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }

    /**
     *  Default constructor , Use initial capacity 10 Construct an empty list ( Parameterless construction )
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     *  The construct contains the specified collection List of elements , These elements use the iterator of the collection to return... In order 
     * If the specified set is null,throws NullPointerException.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

Copy

2. Through source code analysis ArrayList Capacity expansion mechanism of

Through the above , You can find Create with parameterless construction method ArrayList when , In fact, initializing the assignment is an empty array . When you actually add elements to an array , To really allocate capacity . When you add the first element to an array , Expand the array capacity to 10

Next, let's analyze the process of adding elements and expanding capacity .

When calling add(E e) Method , The first call ensureCapacityInternal f Method

    /**
     *  Appends the specified element to the end of this list 
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //  increase  modCount!!
        elementData[size++] = e;
        return true;
    }

Copy

analysis ensureCapacityInternal Method , When you add the first element ,size by 0, obtain minCapacity by 1, Determine whether the data of the array is empty , If it is empty, compare the passed in value with the default size value , Get the maximum of two , Now you can get minCapacity Turn into 10. And then execute ensureExplicitCapacity Method , Determine whether capacity expansion is needed .

    /**
     *  Get the minimum expansion capacity 
     * @param minCapacity
     */
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //  Get the default capacity and the maximum value of the passed in parameters 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

Copy

When the first element is inserted ,elementData.length by 0, here minCapacity by 10,10>0, Need to expand , perform grow Method , The expanded capacity is 10. When inserted is the 2 To 10 Element time ,minCapacity - elementData.length > 0 Will not be established , Not execute grow Scale operation , When it comes to 11 It will start to expand when there are four elements .

    /**
     *  Determine whether capacity expansion is needed 
     * @param minCapacity
     */
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //  When the index of the element to be inserted exceeds the original length , super-popular 
        if (minCapacity - elementData.length > 0)
            //  super-popular 
            grow(minCapacity);
    }

Copy

When the first element is inserted ,minCapacity by 10, here elementData.length=0, so int newCapacity = oldCapacity + (oldCapacity >> 1); The calculated value is still 0; therefore newCapacity - minCapacity < 0 establish ,newCapacity = minCapacity; The capacity of the first expansion is 10.

The capacity expansion mechanism is as follows ： First, get the old capacity of the array , Then calculate the value of the new capacity , Computation uses bit operations , Expand it to the original 1.5 times . After getting the value of the new capacity , Verify whether the expanded capacity is greater than the required capacity , If it is less than , The minimum required capacity is taken as the new capacity after expansion . And ensure that the capacity after expansion does not exceed the maximum size that the array can set . Finally, copy the data from the old array to the new array .

    /**
     *  The maximum size allocation of the array .
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     *  Add capacity , To ensure that it can hold at least the specified number of elements .（ Expansion core ）
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        //  Get old capacity 
        int oldCapacity = elementData.length;
        //  Use bitwise operation , Capacity expansion 1.5 times , Get new capacity 
        //  >> 1  Equivalent to  /2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //  Verify whether the expanded capacity is greater than the required capacity , If it is less than , The minimum required capacity is taken as the new capacity after expansion 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //  Ensure that the capacity after expansion does not exceed the maximum size that the array can set 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            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();
        //  If the new capacity is greater than the maximum capacity , The new capacity is  Integer.MAX_VALUE; Otherwise  Integer.MAX_VALUE - 8
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

Copy

I drew a picture , It's not very accurate , You can probably see

Reference resources ：

• https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

Copyright: use Creative Commons signature 4.0 International license agreement to license Links:https://lixj.fun/archives/arraylist Capacity expansion mechanism of