Let's start with the constructor of ArrayList.

ArrayList can be initialized in three ways. The source code of the construction method is as follows:

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

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *Default constructor, using initial capacity 10 to construct an empty list (no parameter construct)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * Constructor with initial capacity parameter. (Users specify their own capacity)
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//Initial capacity greater than 0
            //Create arrays of initial Capacity size
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//Initial capacity equal to 0
            //Create empty arrays
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//Initial capacity less than 0, throw an exception
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *Construct a list containing the specified collection elements, which are returned sequentially using the iterator of the collection
    *If the specified set is null, throws NullPointerException. 
    */
     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;
        }
    }

Careful students will surely find that when creating ArrayList with a parametric construction method, the assignment is actually initialized as an empty array. Only when the elements are added to the array can the capacity be allocated. When the first element is added to the array, the capacity of the array is expanded to 10. Here's what we'll talk about when we analyze the expansion of ArrayList!

Two-step and one-step analysis of ArrayList expansion mechanism

Here we take the Array List created by the parametric constructor as an example.

1. Let's look at the add method first.

    /**
     * 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!!
        //Here you see that the essence of adding elements to ArrayList is equivalent to assigning values to arrays.
        elementData[size++] = e;
        return true;
    }

2. Look again at the ensureCapacityInternal() method

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) {
              // Gets the default capacity and larger values of the incoming parameters
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

When add ing to the first element, minCapacity is 1, compared with the Math.max() method, minCapacity is 10.

3. ensureExplicitCapacity() method

If you call the ensureCapacityInternal() method, you will certainly go through the method. Let's look at the source code of this method.

  //Judging whether expansion is needed
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //Call the group method for expansion, which means that expansion has begun
            grow(minCapacity);
    }

Let's analyze it carefully.

• When we add the first element to the ArrayList, elementData.length is 0 (because it's still an empty list), and minCapacity is 10 because the ensureCapacityInternal() method is executed. At this point, minCapacity - elementData.length > 0 is established, so the minCapacity method is entered.
• When adding the second element, minCapacity is 2, then E lementData. length (capacity) expands to 10 after adding the first element. At this point, minCapacity - elementData. length > 0 is not established, so the minCapacity method is not entered.
• When adding elements 3, 4... to 10, the group method is still not executed, and the array capacity is 10.

Until the eleventh element is added, minCapacity(11) is larger than elementData.length (10). Enter the group method for expansion.

4. Growth () method

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

    /**
     * ArrayList The core method of expansion.
     */
    private void grow(int minCapacity) {
        // Old Capacity is the old capacity, and new Capacity is the new capacity.
        int oldCapacity = elementData.length;
        //Move old Capacity one bit to the right, and the effect is equivalent to old Capacity/2.
        //We know that bit operations are much faster than divisions. The result of whole sentence operations 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 larger than the minimum required capacity, and if it is smaller than the minimum required capacity, then the minimum required capacity is considered as the new capacity of the array.
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // If the new capacity is larger than MAX_ARRAY_SIZE, enter (execute) the `hugeCapacity()'method to compare min Capacity with MAX_ARRAY_SIZE.
       //If minCapacity is larger 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 be 1.5 times the original capacity after each expansion! (After JDK 1.6 version) When JDK 1.6 version, the capacity after expansion is 1.5 times + 1! For more information, please refer to the source code.

Let's explore the growth () method through an example:

• When adding the first element, old Capacity is 0, and the first if judgement is valid after comparison, new Capacity = minCapacity (10). However, the second if judgment does not hold, that is, new Capacity is not larger than MAX_ARRAY_SIZE, and will not enter the hugeCapacity method. The array capacity is 10, return true in add method, and size is increased to 1.
• When the add eleventh element enters the group method, the new Capacity is 15, larger than the minCapacity (11), and the first if judgement is not valid. 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, return true in add method and size to 11.
• By analogy······

Here is a more important but easily overlooked point of knowledge:

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

5. hugeCapacity() method.

From the source code of the above growth () method, we know that if the new capacity is larger than MAX_ARRAY_SIZE, the entry (execution) hugeCapacity() method compares minCapacity with MAX_ARRAY_SIZE, and if minCapacity is larger than the maximum capacity, the new capacity is Integer.MAX_VALUE, otherwise, the new capacity is MAX_ARRAY_SIZE, that is Integer.M. AX_VALUE-8.

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

Three System.arraycopy() and Array. copyOf () methods

If you read the source code, you'll find a lot of calls to these two methods in ArrayList. For example, this method is used in the expansion operations mentioned above and in the methods of add(int index, E element), toArray().

3.1 System.arraycopy() method

    /**
     * Insert the specified element at the specified location in this list. 
     *First, RanCheckForAdd is called to check the boundaries of index, and then ensureCapacityInternational method is called to ensure that capacity is large enough.
     *Then move all members back after index; insert element into index position; and finally add size to 1.
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

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

Let's 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.println(a[i]);
		}
	}

}

Result:

0 1 99 2 3 0 0 0 0 0 

3.2 Arrays.copyOf() method

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

I think that the main purpose of using Arrays.copyOf() method is 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

3.3 Linkages and Differences between the Two

Contact:

Looking at the source code of both, you can see that the System.arraycopy() method is actually called inside copyOf().

Difference:

Araycopy () requires the target array to copy the original array into your own defined array or the original array, and you can choose the starting point and length of the copy and the location of the copy of () in the new array. CopOf () is the system automatically creates a new array internally and returns the array.

Four ensure Capacity method

There is a ensureCapacity method in the source code of ArrayList. I don't know if you have noticed it. This method has not been called inside ArrayList, so it's obviously provided to the user for calling. So what's the effect of this method?

    /**
    If necessary, increase the capacity of this ArrayList instance to ensure that it can accommodate at least the number of elements specified by the minimum capacity 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);
        }
    }

It's better to use the 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));

		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 results:

Before using the ensureCapacity method: 4637
 After using the ensureCapacity method:241

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