Analyze the capacity expansion mechanism of ArrayList

Reprinted from ： Bai Chunyu （https://www.cnblogs.com/baichunyu/p/12965241.html）

One 、 First from ArrayList The constructor of

ArrayList There are three ways to initialize , Here is the most commonly used parameterless method ：

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


    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };
	
	transient Object[] elementData; // non-private to simplify nested class access

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

The construction method will elementData Point to an internally empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA, 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.

Two 、 Step by step analysis ArrayList Expansion mechanism

This is created with a parameterless constructor ArrayList For example, analyze ：

1、 First look add Method

	/** *  Appends the specified element to the end of this list . */
    public boolean add(E e) {
    
   // Before adding elements , First call ensureCapacityInternal Method 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // See here ArrayList The essence of adding elements is to assign values to arrays 
        elementData[size++] = e;
        return true;
    }

2、 Look again. ensureCapacityInternal() Method

You can see add Method First, I call ensureCapacityInternal(size + 1)

	// Get the minimum expansion capacity 
    private void ensureCapacityInternal(int minCapacity) {
    
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
              //  Get the default capacity and larger values of the incoming parameters 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

3、ensureExplicitCapacity() Method

If the ensureCapacityInternal() The method will definitely go through （ perform ） This method , Let's study the source code of this method ！

 	protected transient int modCount = 0;
	// Determine whether capacity expansion is needed 
    private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            // call grow Methods to expand capacity , Calling this method means that the expansion has started 
            grow(minCapacity);
    }

Let's analyze it carefully ：

• When we want to add Go to No 1 Elements to ArrayList when ,elementData.length by 0 （ Because it's still an empty list）, Because of the execution ensureCapacityInternal() Method , therefore minCapacity This is the case 10. here ,minCapacity - elementData.length > 0 establish , So it's going to enter grow(minCapacity) Method .
• When add The first 2 Element time ,minCapacity by 2, here e lementData.length( Capacity ) Expand to... After adding the first element 10 了 . here ,minCapacity - elementData.length > 0 Don't set up , So it won't enter （ perform ）grow(minCapacity) Method .
• Add para 3、4··· To the first 10 Element time , Still won't execute grow Method , The array capacity is 10.

Until... Is added 11 Elements ,minCapacity( by 11) Than elementData.length（ by 10） Be big . Get into grow Methods to expand capacity .

4、grow() Method

/** *  Maximum array size to allocate  */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /** * ArrayList The core method of capacity expansion . */
    private void grow(int minCapacity) {
    
        // oldCapacity Old capacity ,newCapacity New capacity 
        int oldCapacity = elementData.length;
        // take oldCapacity  Moves to the right one , The effect is equivalent to oldCapacity /2,
        // We know that bit operations are much faster than division operations , The result of the whole expression is to replace the new capacity with the old one 1.5 times ,
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // Then check whether the new capacity is greater than the minimum required capacity , If it is still less than the minimum required capacity , Consider the minimum required capacity as the new capacity of the array ,
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       //  If the new capacity is greater than  MAX_ARRAY_SIZE, Get into ( perform ) `hugeCapacity()`  Method to compare  minCapacity  and  MAX_ARRAY_SIZE,
       // If minCapacity Greater than maximum capacity , The new capacity is `Integer.MAX_VALUE`, otherwise , The new capacity is  MAX_ARRAY_SIZE  That is to say  `Integer.MAX_VALUE - 8`.
        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);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1), therefore ArrayList After each expansion, the capacity will change to the original 1.5 About times （oldCapacity Even is 1.5 times , It is 1.5 About times ）！ Parity is different , such as ：10+10/2 = 15, 33+33/2=49. If it's odd, you lose the decimal .

Let's explore through examples grow() Method ：

• When add The first 1 Element time ,oldCapacity by 0, After comparison, the first one if Judgment holds ,newCapacity = minCapacity( by 10). But the second if Judgment doesn't hold , namely newCapacity No comparison MAX_ARRAY_SIZE Big , Will not enter hugeCapacity Method . The array capacity is 10,add In the method return true,size Add to 1.
• When add The first 11 Elements enter grow When the method is used ,newCapacity by 15, Than minCapacity（ by 11） Big , first if The judgment doesn't hold . The new capacity is not greater than the maximum of the array size, Will not enter the hugeCapacity Method . Expand the array capacity to 15,add In the method return true,size Add to 11.
  And so on ······

It's important to add here , But knowledge points that are easy to be ignored ：

1.java  Medium  length  Properties are for arrays , For example, you declare an array , If you want to know the length of this array, you need  length  This attribute .
2.java  Medium  length()  Method is for strings , If you want to see the length of this string, you use  length()  This method .
3.java  Medium  size()  The method is for generic sets , If you want to see how many elements this generic has , Call this method to see !

5、hugeCapacity() Method

Finally, let's talk about when the array size is larger than MAX_ARRAY_SIZE When did it happen hugeCapacity() Method .

private static int hugeCapacity(int minCapacity) {
    
	if (minCapacity < 0) // overflow
	    throw new OutOfMemoryError();
	// Yes minCapacity and MAX_ARRAY_SIZE Compare 
	// if minCapacity Big , take Integer.MAX_VALUE As the size of the new array 
	// if MAX_ARRAY_SIZE Big , take MAX_ARRAY_SIZE As the size of the new array 
	//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	return (minCapacity > MAX_ARRAY_SIZE) ?
	    Integer.MAX_VALUE :
	    MAX_ARRAY_SIZE;
}

This method refers to when the capacity is expanded size Greater than specified MAX_ARRAY_SIZE There are two possibilities at this time

1. At present ArrayList Deposited size Less than MAX_ARRAY_SIZE That is to call add The array capacity after insertion is not greater than MAX_ARRAY_SIZE, namely minCapacity Less than or equal to MAX_ARRAY_SIZE So at this point , Get into hugeCapacity Method returns MAX_ARRAY_SIZE;
2. The above capacity has been expanded to the maximum , What will happen if you are inserting ？ This is the time minCapacity be equal to MAX_ARRAY_SIZE+1, The last thing to come back is Integer.MAX_VALUE;

So the biggest thing is that we can only get to Integer.MAX_VALUE;

another ：ensureCapacity Method

ArrayList There is one in the source code ensureCapacity I don't know if you noticed , This method ArrayList The interior has not been called , So it's obviously provided for users to call , So what's the use of this method ？

	/**  If necessary, , Increase this  ArrayList  Capacity of the instance , To ensure that it can at least be accommodated by minimum capacity The number of elements specified by the parameter . * * @param minCapacity  Minimum capacity required  */
    public void ensureCapacity(int minCapacity) {
    
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
    
            ensureExplicitCapacity(minCapacity);
        }
    }

The purpose is to reduce the expansion times , When we know the specific capacity , Directly use the parametric construction method , Instead of using the default constructor , default 10 Capacity makes programs expand frequently , Greatly reduces program efficiency , Empathy Hashmap When you know the specific capacity, you should also avoid .