ArrayList automatic capacity expansion principle

Preface

ArrayList The underlying data structure is Array ,

• Array is characterized by ： Quick query , Add or delete slowly
  The reason is ： Sequential storage , There is an index , According to the index , Navigate directly to the element , So the inquiry is fast ; Because it's sequential storage , Add or delete , Will have an impact on subsequent elements .

1. First, create a ArrayList Assembly begins , Set it up as follows ：

       ArrayList<String> list = new ArrayList();

2. After entering the source code, you can see the following source code ：

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

    transient Object[] elementData; // non-private to simplify nested class access

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };

1. First ArrayList There is an assignment code in the construction method of , To the left of the equals sign is a customized source code Object Array of constants of type , Then assigned to transient A retouched one Object Type of elementData Array .
2. The above conclusion is when creating objects ArrayList The bottom layer creates an array , The initial capacity of the array is empty .

ArrayList For the first time in the set add Elements ：

1. First call add What do you see as methods , You also need to enter the source code .

       list.add("aa");

2.add The source code of the method is as follows ：

    public boolean add(E e) {
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

1. call add Method to pass in a string “aa”.

2. add The first sentence in the method body calls ensureCapacityInternal Method , Chinese means ：（ Determine internal capacity ） The minimum capacity passed to the inside is 1, because size It is a customized source code int The variable of type has no initial value, so size by 0.

3. The second sentence is in the empty array size++, here elementData The array is 0, Assign the passed value to the array 0 Subscript .

4. Get into （ Determine internal capacity ） Method , The minimum capacity at this time is 1.

    private void ensureCapacityInternal(int minCapacity) {
    
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

5. Another... Is called in the method of determining the internal capacity （ Computing capacity ） Two parameters are passed in the method ： One is an empty array , One is the minimum capacity . And then catch up with the source code .

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    /** * Default initial capacity. */
    private static final int DEFAULT_CAPACITY = 10;

6. At this point, a judgment is made in this method , Condition is true, because This statement is the one called at the bottom when creating the collection object .
7. call Math Class to compare the maximum value , The minimum capacity is 1,DEFAULT_CAPACITY The constant is 10, Because the source code defines and assigns the initial value to 10.

    private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

8. Do judgment 10 reduce 0 Greater than 0 Conditions established , call grow Method will have the minimum capacity 10 Put it in .

    private void grow(int minCapacity) {
    
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

9. here minCapacity by 10. The second and last sentences of the source code are the core .
newCapacity = minCapacity; After the old capacity is assigned to the new capacity , The new capacity is now 10.
The last sentence is to add new capacity 10 adopt Arrays In a tool class copyof Method is copied to elementData, And assigned to elementData, To the left of the equal sign elementData Point to the original empty array . At this point, the new array length becomes 10 了 .

Conclusion ： First call add When the method is used , The array length is 10.

ArrayList The second call of the collection add Method add element ：

       list.add("bb");

    public boolean add(E e) {
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

1. The array length is 10,aa Has been deposited in 0 Subscript ,size++ Now become 1 了 . The minimum capacity is now 2.

    private void ensureCapacityInternal(int minCapacity) {
    
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }


    private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
        return minCapacity;
    }

    // The meaning of the secondary code is whether to confirm the capacity expansion ,if If the condition is satisfied, the capacity expansion shall be implemented .
    private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

1. here elementData by 10,minCapacity by 2.
2. If the condition does not hold, it will not call grow Method . When the 11 It will only be called when the data is retrieved grow Capacity expansion method .

minCapacity by 11 Call the capacity expansion method ： Let's expand it to the original 1.5 times .

The expansion code is selected from the box above .

The final summary ：

1. ArrayList The underlying data structure is an array , When creating a ArrayList Object time , The bottom layer initializes an empty array , An array is Object type , The array name is elementData. When you first add an element , The array length is expanded to 10.

2. When the first 11 Add times , Will trigger the expansion mechanism , In fact, it's called grow Method , Expand to the length of the original array 1.5 times .

3. At each expansion , Is to create a new array , Pass the elements of the old array through Arrays The tool class is copied to the new array .elementData Points to the new array

4. *** The expansion is not based on the splicing of old arrays , And create a 1.5 A new array of times the length , And copy the elements of the old array to the new array .