Capacity expansion mechanism of ArrayList

ArrayList Capacity expansion mechanism of

1, When the nonparametric construction method was just started

    /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };
    
    /** * Constructs an empty list with an initial capacity of ten. */
     //  The first construction method 
    public ArrayList() {
    
    	//  This actually points to an empty array 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    /** * Shared empty array instance used for empty instances. */
    private static final Object[] EMPTY_ELEMENTDATA = {
    };

	//  The second construction method   Construction method with parameters 
    public ArrayList(int initialCapacity) {
    
        if (initialCapacity > 0) {
    
        	 //  Complete the construction of the array 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
    
        	//  If it is equal to 0 Point to an empty array 
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
    
        //  If it's a negative number   Throw an exception 
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

	/** *  The third construction method  *  Convert the incoming collection into an array , And then through Arrays.copyOf Method to copy the elements in the set  *  Beidao elementData in . Again , If the length of the incoming set is 0, return  * EMPTY_ELEMENTDATA */
    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;
       }
   }

2, Add method

    /** * The size of the ArrayList (the number of elements it contains). * * @serial */
    private int size;
    
    /** * 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}) */
     //  Currently not thread safe 
    public boolean add(E e) {
    
     //  Before adding elements , A capacity expansion process will be performed , Judge whether to expand capacity 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

3, Came to ensureCapacityInternal How to look closely

    private void ensureCapacityInternal(int minCapacity) {
    
    //  Judge whether it is equal to null , At this time elementData  Meet the conditions , because elementData
    //  It's empty ,Math.max  Take the maximum  DEFAULT_CAPACITY = 10
    //  and minCapacity = 1  All final returns 10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
        //  So now minCapacity  be equal to 10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

4, Chase down ensureExplicitCapacity Method

    private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++; //  The number of modifications is increased 

        // overflow-conscious code
        // 10 - 0 > 0 true
        if (minCapacity - elementData.length > 0) //  Meet the conditions 
            grow(minCapacity);//  Call the capacity expansion method 
    }

5, The last step grow Method

    /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
    private void grow(int minCapacity) {
    
        // overflow-conscious code
        // oldCapacity = 0,  because elementData  Array is empty 
        int oldCapacity = elementData.length;
        //  There will be a 1.5 Double expansion 
        //  The following sentence can be understood as  oldCapacity  add  oldCapacity  Divide 2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // nexCapacity = 0 - 1 < 0? false 
        if (newCapacity - minCapacity < 0) //  Meet the conditions 
         // minCapacity  be equal to 10  Assign a value to  newCapacity 
            newCapacity = minCapacity;
            //  Make a maximum value judgment , Is it beyond 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //  At this time, a Arrays.copyOf Complete a capacity expansion 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

6, The illustration , It was like this when I came out for the first time

7, The second time you add

    private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++; //  The number of modifications is increased 

        // overflow-conscious code
        // minCapacity be equal to 2 elementData.length be equal to 10 
        // 2-10 = -8 ,-8  No more than 0  So it doesn't meet the conditions 
        if (minCapacity - elementData.length > 0) //  Not meeting the conditions 
           //  The current method will not be called 
            grow(minCapacity);
    }

8, Suppose the current element bits are used up , Need to expand

    private void grow(int minCapacity) {
    
        // overflow-conscious code
        // elementData.length = 10  therefore oldCapacity  be equal to 10
        int oldCapacity = elementData.length;
        // int newCapacoty = 10 + (10 / 2);
        //  The result is 15
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //  It's the same below , It was explained above that 
        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:
        //  New newCapacity（ New capacity ） And the previous array   Put it in and expand it 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

9, The diagram means

10, Push in , For each increase 1.5 Times the speed to increase