ArrayList source analysis (expansion mechanism jdk8)

ArrayList overview

(1) ArrayList is a variable length collection class, based on fixed-length array implementation.

(2) ArrayLists allow null values and duplicate elements. When the number of elements added to an ArrayList is greater than the capacity of the underlying array, it will generate a larger array through an expansion mechanism.

(3) Because ArrayList is implemented based on array, it can guarantee to complete random search operation in O(1) complexity.

(4) ArrayList is a non-thread-safe class. In a concurrent environment, multiple threads operate ArrayList simultaneously, which may cause unexpected exceptions or errors.

Member properties of an ArrayList

Let’s take a look at the underlying property members before introducing the various methods of an ArrayList. The difference between DEFAULTCAPACITY_EMPTY_ELEMENTDATA and EMPTY_ELEMENTDATA is that DEFAULTCAPACITY_EMPTY_ELEMENTDATA will know how much the array should be expanded when we add the first element to it.

// Initialize the capacity by default
private static final int DEFAULT_CAPACITY = 10;

// The default is an empty array. This is used when the constructor initializes an empty array
private static final Object[] EMPTY_ELEMENTDATA = {};

// Use the default size of an empty array instance, distinguished from EMPTY_ELEMENTDATA,
// This lets you know how much to expand when the first element is added
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList stores the underlying data in the form of an array, ArrayList length is the length of the array.
// An empty instance of elementData for DEFAULTCAPACITY_EMPTY_ELEMENTDATA when the first element is added
// The capacity will be expanded. The capacity will be the default capacity DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access

/ / the size of the arrayList
private int size;
Copy the code

Static modified EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA

The ArrayList constructor

(1) A constructor with an initialized capacity

• If the parameter is greater than 0, elementData is initialized to an array of size initialCapacity
• If the parameter is less than 0, elementData is initialized to an empty array
• If the parameter is less than 0, an exception is thrown

// The parameter is the initial capacity
public ArrayList(int initialCapacity) {
    // Determine the validity of the capacity
    if (initialCapacity > 0) {
        //elementData is the array that actually holds the elements
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // If the length is 0, we use the member variable we already defined (an empty array)
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

(2) No-parameter structure

• The constructor initializes elementData as an empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA
• When the add method is called to add the first element, it expands
• Expand the capacity to DEFAULT_CAPACITY=10

// The constructor uses an empty array with the default size of 10. The constructor does not set the size of the array, so it will be expanded in subsequent calls to the add method
public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

(3) The constructor that takes the type Collection

// Convert a Collection with arguments Collection to an ArrayList (in effect, convert the elements of the Collection to an array). if
// If null is passed in, a null pointer exception is thrown (when c.array () is called).
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if((size = elementData.length) ! =0) {
        // c.array () might not correctly return an Object[] array, so use the arrays.copyof () method
        if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
        // If the array length is 0 after the collection is converted to an array, we initialize elementData directly with our own empty member variable
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

The above constructors are relatively simple to understand. Focus on what the first two constructors do, which is to initialize the underlying array elementData(this.elementData=XXX). The difference is that the no-argument constructor initializes an empty array with elementData, and when an element is inserted, the expansion will reinitialize the array with the default value. Constructors with parameters, on the other hand, initialize elementData as an array of the size of the parameter value (>= 0). In general, we use the default constructor. If you know how many elements will be inserted into the ArrayList, you can use a parameter constructor.

As mentioned above, when using no-parameter constructs, the add method is expanded when called, so let’s look at the add method and the details of the expansion

Add method of ArrayList

The add method flows roughly

// Add the specified element to the end of the list
public boolean add(E e) {
    // If you want to add an element, you may not have enough capacity.
    ensureCapacityInternal(size + 1);  // Increments modCount!! (We'll talk about fast-fail in a moment)
    elementData[size++] = e;
    return true;
}
Copy the code

We saw that the add method determines the size before adding an element, so let’s look at the details of the ensureCapacityInternal method

Analysis of the ensureCapacityInternal method

private void ensureCapacityInternal(int minCapacity) {
    // If the elementData array is empty, the array is null
    // (elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    // If so, compare size+1(size+1=1 when the first call to add) to DEFAULT_CAPACITY.
    // So obviously the capacity is 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
Copy the code

** minCapacity = (size+1=0+1=)1 when the first element is added; after math.max (), minCapacity = 10. ** Then call ensureExplicitCapacity to update the modCount value and determine whether to expand

EnsureExplicitCapacity method analysis

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // Here is the Increments modCount annotated in the add method
    / / overflow
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);// Here is how to perform the expansion
}
Copy the code

Let’s take a look at the main method of expansion, grow.

Analysis of GROW method

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    // oldCapacity specifies the capacity of the old array
    int oldCapacity = elementData.length;
    // newCapacity is the capacity of the new array (oldCap+oldCap/2: update to 1.5 times the old capacity)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // Check whether the size of the new capacity is less than the minimum required capacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the new capacity is larger than MAX_ARRAY_SIZE, use hugeCapacity to compare the two
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // Copy the elements from the original array
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

HugeCapacity method

Here’s a quick look at the hugeCapacity method

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // Compare 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, 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;
}
Copy the code

The add method performs the process summary

Let’s take a quick look at the flow of execution after the first call to the add method when the no-parameter construct is used

This is the procedure for calling the add method for the first time. After capacity is set to 10,

• Continue adding the second element (notice that the ensureCapacityInternal method is passed as size+1=1+1=2)

• In the ensureCapacityInternal method, elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA does not hold, so the ensureExplicitCapacity method is executed directly

• MinCapacity in the ensureExplicitCapacity method is the 2 just passed, so the second if judgment (2-10=-8) will not hold, that is, newCapacity is not larger than MAX_ARRAY_SIZE, so the grow method will not be entered. The size of the array is 10, and the add method returns true, increasing the size to 1.

• Suppose 3 and 4 are added…… 10 elements (where the process is similar, but the grow scaling method is not executed)

• NewCapacity = 15, which is larger than minCapacity (10+1=11). If the new capacity is not larger than the array maximum size, it does not enter the hugeCapacity method. The size of the array is increased to 15. The add method returns true, and the size is increased to 11.

Add (int index,E element) method

// Insert the element sequence at index
public void add(int index, E element) {
    rangeCheckForAdd(index); // Check whether the index parameter passed is valid
    // 1. Check whether the capacity needs to be expanded
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. Move index and all subsequent elements back one bit
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 3. Insert the new element at index
    elementData[index] = element;
    size++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) // Select index>size and index < 0
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code

The add(int index, E element) method, which inserts elements at the specified position in the sequence (assuming that position is reasonable), goes something like this

1. Check whether the array has enough space (implementation here and above)
2. Moves index and all the elements that follow it back one bit
3. Insert the new element at index.

To insert a new element into a specified position in the sequence, you first move that position and all subsequent elements back one bit to make room for the new element. The time complexity of this operation is O(N), and moving the elements frequently can cause efficiency problems, especially with a large number of elements in the collection. In everyday development, we should try to avoid calling a second insert method in a large collection unless we need to.

The remove method of the ArrayList

ArrayList supports two ways to delete elements

1. Remove (int index) Delete according to the subscript

public E remove(int index) {
    rangeCheck(index); / / check the subscript is legal, if the index > size, old thrown IndexOutOfBoundsException exception)
    modCount++;// To change the list structure, you need to update this value
    E oldValue = elementData(index); // Look for the value directly in the array

    int numMoved = size - index - 1;// Here count the number of moves needed
    // If this value is greater than 0, the following elements need to be shifted to the left (size=index+1)
    // 0 indicates that the object to be removed is the last element (no other elements need to be moved).
    if (numMoved > 0)
        // All elements of index are shifted one bit to the left to cover the elements at index position
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // After the move, the size position in the original array is null
    elementData[--size] = null; // clear to let GC do its work
    // Return the old value
    return oldValue;
}
/ / SRC: source array
//srcPos: move from the srcPos position in the source array
//dest: destination array
//desPos: elements that start moving at srcPos of the source array and start filling at desPos of the destination array
//length: moves the length of the source array
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
Copy the code

The following figure shows the deletion process

Remove (Object O) Remove (Object O) Remove (Object O) remove(Object O) by element

public boolean remove(Object o) {
    // If the element is null, the traversal removes the first null
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                // Call the subscript to remove the element
                fastRemove(index);
                return true; }}else {
        // Find the subscript of the element and call the subscript to remove the element
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}
// Remove the element from the array by its subscript.
private void fastRemove(int index) {
  modCount++;
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  elementData[--size] = null; // clear to let GC do its work
}
Copy the code

Other methods of ArrayList

EnsureCapacity method

It is best to use the ensureCapacity method before adding a large number of elements to reduce the number of incremental reassignments

public void ensureCapacity(int minCapacity) {
    intminExpand = (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); }}Copy the code

ArrayList summary

(1) ArrayList is a varied-length collection class based on a fixed-length array, initialized with a capacity of 10 using the default constructor. (after 1.7, the size of elementData is initialized to 10 when the add method is first called.)

(2) ArrayLists allow null values and duplicate elements. When the number of elements added to an ArrayList is greater than the capacity of the underlying array, it will generate a larger array through an expansion mechanism. The expanded length of the ArrayList is 1.5 times the original length

(3) Because ArrayList is implemented based on array, it can guarantee to complete random search operation in O(1) complexity.

(4) ArrayList is a non-thread-safe class. In a concurrent environment, multiple threads operate ArrayList simultaneously, which may cause unexpected exceptions or errors.

(5) Sequential addition is convenient

(6) Delete and insert requires a copy of the array, poor performance (can use LinkindList)

(7) Integer.MAX_VALUE – 8: If MAX_ARRAY_SIZE is larger than MAX_ARRAY_SIZE, we will compare the minimum required capacity with MAX_ARRAY_SIZE. If MAX_ARRAY_SIZE is larger than MAX_ARRAY_SIZE, The value must be Integer.MAX_VALUE, or Integer.MAX_VALUE -8. This is only available from JDK1.7

Fast – fail mechanism

Fail-fast:

In system design, a system that instantly reports anything that might indicate a failure. Quick-failure systems are usually designed to stop normal operations rather than attempt to continue a potentially defective process. This design typically checks the state of the system at multiple points in the operation, so any failures can be detected early. The responsibility of the fast failure module is to detect errors and then let the next highest level of the system handle them.

When doing system design, consider the exception first, and when the exception occurs, directly stop and report, such as the following simple example

// In the fast_fail_method method, we do a simple check on the dividend, and if it is zero, we throw an exception with a clear reason for the exception. This is the fail-fast idea in action.
public int fast_fail_method(int arg1,int arg2){
    if(arg2 == 0) {throw new RuntimeException("can't be zero");
    }
    return arg1/arg2;
}
Copy the code

This mechanism is used in many parts of Java collection class design, and if used improperly, unexpected things can happen to code that triggers fail-fast mechanism design. By default, when we say fail-fast in Java, we mean an error detection mechanism for Java collections. When multiple threads to the operation of the part of the change in the structure of the collection, is likely to trigger this mechanism, will be thrown after concurrent modification anomalies ConcurrentModificationException * * * *. Of course, if you are not in a multi-threaded environment, it is possible to throw this exception if you use the add/remove method during the foreach traversal. Refer to the fast-fail mechanism for a brief summary here

Will throw ConcurrentModificationException, because our code used in the enhanced for loop, and the enhanced for loop, a collection of traverse was conducted by the iterator, However, the add/remove method of the element is directly used by the collection class itself. This causes the iterator to throw an exception indicating that a concurrent change may have occurred if an element has been deleted/added without the iterator knowing it! So, when using Java collection classes, if there is a ConcurrentModificationException, give priority to fail – fast the relevant circumstances, this might actually didn’t really occur concurrently, only using the Iterator fail – fast protection mechanism, Whenever he finds a modification that he did not make, he throws an exception.