In 1.8, when an ArrayList is created with a parameterless constructor, an empty array is actually initialized and assigned. The capacity is only allocated when the element is actually added to the array. That is, when the first element is added to the array, the capacity of the array is expanded to 10.

Supplement: When JDK7 new an ArrayList object constructed without parameters, an Object[] array elementData with a length of 10 is directly created. The creation of the ArrayList object in jdk7 is similar to the singleton style, while the creation of the ArrayList object in jdk8 is similar to the singleton lazy style

Here is an example of an ArrayList created by a no-argument constructor

First look at the add method

    /**
     * Appends the specified element to the end of this list.
     */
    public boolean add(E e) {
   //Before adding elements, call the ensureCapacityInternal method
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //Seeing here that the essence of adding elements to ArrayList is equivalent to assigning values ​​to the array
        elementData[size++] = e;
        return true;
    }

Note: JDK11 removed ensureCapacityInternal() and ensureExplicitCapacity() methods

Let's take a look at the ensureCapacityInternal() method

(JDK7) You can see that the add method first calls ensureCapacityInternal(size + 1)

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

        ensureExplicitCapacity(minCapacity);
    }

When the first element is to be add ed, minCapacity is 1, and after the Math.max() method comparison, minCapacity is 10.

The formatting of the code here is slightly different from the subsequent JDK8 code, and the core code is basically the same.

ensureExplicitCapacity() method

If you call the ensureCapacityInternal() method, you will definitely enter (execute) this method. Let's study the source code of this method!

  //Determine if expansion is required
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //Call the grow method to expand, calling this method means that the expansion has begun
            grow(minCapacity);
    }

Let's take a closer look:

• When we want to add the first element into the ArrayList, elementData.length is 0 (because it is still an empty list), because the ensureCapacityInternal() method is executed, so minCapacity is now 10. At this point, minCapacity - elementData.length > 0 is established, so it will enter the grow(minCapacity) method.
• When adding the second element, minCapacity is 2, and elementData.length (capacity) is expanded to 10 after adding the first element. At this time, minCapacity - elementData.length > 0 does not hold, so it will not enter (execute) the grow(minCapacity) method.
• When adding the 3rd, 4th... to the 10th element, the grow method is still not executed, and the array capacity is all 10.

Until the 11th element is added, minCapacity (which is 11) is larger than elementData.length (which is 10). Enter the grow method to expand.

grow() method

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

    /**
     * ArrayList The core method of scaling.
     */
    private void grow(int minCapacity) {
        // oldCapacity is the old capacity, newCapacity is the new capacity
        int oldCapacity = elementData.length;
        //Shift oldCapacity to the right by one, the effect is equivalent to oldCapacity /2,
        //We know that the bit operation is much faster than the integer division operation, and the result of the whole sentence operation is to update the new capacity to 1.5 times the old capacity,
        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, then take 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, enter (execute) the `hugeCapacity()` method to compare minCapacity and MAX_ARRAY_SIZE,
       //If minCapacity is greater than the maximum capacity, the new capacity is `Integer.MAX_VALUE`, otherwise, the new capacity size is MAX_ARRAY_SIZE which is `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), so the capacity of ArrayList will become about 1.5 times the original capacity after each expansion (oldCapacity is an even number is 1.5 times, otherwise it is about 1.5 times)! The parity is different, for example: 10+10/2 = 15, 33+33/2=49. If it is an odd number, the decimal will be dropped.

"> >" (shift operator): > > shifting 1 to the right is equivalent to dividing 2, and shifting n to the right is equivalent to dividing 2 to the nth power Here oldCapacity is obviously shifted right by 1 bit so it is equivalent to oldCapacity /2. For binary operations of big data, the displacement operator is much faster than those of ordinary operators, because the program only moves a bit and does not calculate, which improves efficiency and saves resources

Let's explore the grow() method with an example:

• When add ing the first element, oldCapacity is 0, after the comparison, the first if is judged to be true, newCapacity = minCapacity(10). But the second if judgment will not hold, that is, if newCapacity is not greater than MAX_ARRAY_SIZE, it will not enter the hugeCapacity method. The array capacity is 10, the add method returns true, and the size is increased to 1.
• When the 11th element of add enters the grow method, newCapacity is 15, which is larger than minCapacity (which is 11), and the first if judgment does not hold. The new capacity is not greater than the maximum size of the array and will not enter the hugeCapacity method. The array capacity is expanded to 15, the add method returns true, and the size is increased to 11.
• And so on...

Here is a little more important, but easily overlooked knowledge points:

• The length property in java is for arrays. For example, if you declare an array, if you want to know the length of the array, you use the length property.
• The length() method in java is for strings. If you want to see the length of the string, use the length() method.
• The size() method in java is for generic collections. If you want to see how many elements there are in this generic type, call this method to check!

hugeCapacity() method.

From the source code of the grow() method above, we know that if the new capacity is greater than MAX_ARRAY_SIZE, enter (execute) hugeCapacity() method to compare minCapacity and MAX_ARRAY_SIZE. If minCapacity is greater than the maximum capacity, the new capacity is integer MAX_ Value, otherwise, the new capacity is MAX_ARRAY_SIZE is integer MAX_ VALUE - 8.

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //Compare minCapacity and MAX_ARRAY_SIZE
        //If minCapacity is large, use Integer.MAX_VALUE as the size of the new array
        //If MAX_ARRAY_SIZE is large, use 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;
    }

System.arraycopy() and Arrays.copyOf() methods

If we read the source code, we will find that these two methods are called a lot in ArrayList. For example, this method is used in the expansion operation we mentioned above, as well as in methods such as add(int index, E element), toArray(), etc.!

System.arraycopy() method

    /**
     * Inserts the specified element at the specified position in this list.
     *First call rangeCheckForAdd to check the index; then call ensureCapacityInternal to ensure that the capacity is large enough;
     *Then move all the members after the index starts by one position; insert the element into the index position; add 1 to the final size.
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //The arraycopy() method implements the array itself to copy itself
        //elementData: source array; index: starting position in source array; elementData: target array; index + 1: starting position in target array; size - index: number of array elements to copy;
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

We write a simple method to test the following:

public class ArraycopyTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}

result:

0 1 99 2 3 0 0 0 0 0

Arrays.copyOf() method

   /**
     Returns an array containing all the elements in this list in the correct order (from the first to the last element); the runtime type of the returned array is that of the specified array.
     */
    public Object[] toArray() {
    //elementData: the array to be copied; size: the length to be copied
        return Arrays.copyOf(elementData, size);
    }

Personally, I think the Arrays.copyOf() method is mainly used to expand the original array. The test code is as follows:

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}

result:

10

connection and difference

connect:

Looking at the source code of the two, you can find that copyOf() actually calls the System.arraycopy() method

the difference:

arraycopy() requires a target array. Copy the original array to your own defined array or the original array, and you can choose the starting point and length of the copy and the position in the new array. copyOf() is an array automatically created internally by the system, and return that array

ensureCapacity method

There is an ensureCapacity method in the ArrayList source code. I don't know if you have noticed it. This method has not been called internally in ArrayList, so it is obviously provided for the user to call. So what does this method do?

    /**
     * Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity parameter.
     * @param   minCapacity   Minimum required capacity
     */
    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);
        }
    }

It is better to use ensureCapacity method before add ing a large number of elements to reduce the number of incremental reallocations

We actually test the effect of the following method through the following code:

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("use ensureCapacity Before the method:"+(endTime - startTime));

    }
}

operation result:

use ensureCapacity Before method: 2158

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("use ensureCapacity After the method:"+(endTime1 - startTime1));
    }
}

operation result:

use ensureCapacity Before method: 1773

By running the results, we can see that it is best to use the ensureCapacity method before adding a large number of elements to the ArrayList to reduce the number of incremental reallocations.