ArrayLIst source code analysis – Java8

Article directory

  • ArrayList
    • Inheritance and implementation
    • Attributes
    • static constant
    • Construction method
    • Add to
    • delete
      • index deletion
      • Delete specified element
    • Iterator
        • hasNext
        • next method
        • remove method
      • list iterator
    • think

ArrayList

  1. When creating a collection using empty parameters, an array with a default length of 0 is created at the bottom
  2. When adding the first element, the underlying creates a new array of length 10
  3. When the deposit is full, the capacity will be expanded by 1.5 times.
  4. If multiple data are added at one time and cannot be accommodated 1.5 times, the length of the newly created array shall be subject to actual conditions.

Inheritance and implementation

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • RandomAccess interface: Mark interface, which can support fast random access after implementation
  • Cloneable: Implementing this interface requires overriding the clone method, indicating that it can be cloned

Properties

//Array to save ArrayList data
transient Object[] elementData; // non-private to simplify nested class access

private int size; //Contains the number of elements and is also the position where the next element is inserted.

Static constants

private static final long serialVersionUID = 8683452581122892189L;

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

/**
 * Shared empty array instance used for empty instances.
 * Shared empty array instance for default size empty instance.
 * Distinguish it from an array that creates an empty instance to know how much the capacity needs to increase when the first element is added.
 * Used when constructing with parameters
 */
private static final Object[] EMPTY_ELEMENTDATA = {<!-- -->};

//Empty array, used to create empty instances, used when constructing without parameters
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {<!-- -->};
//The theoretical maximum value that the array can allocate
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Construction method

Empty ginseng

When creating a collection using empty parameters, an array with a default length of 0 is created at the bottom

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {<!-- -->};

public ArrayList() {<!-- -->
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Specify size initialization

public ArrayList(int initialCapacity) {<!-- -->
    //If the specified size is greater than 0, directly create an array of this size
    if (initialCapacity > 0) {<!-- -->
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {<!-- -->
        this.elementData = EMPTY_ELEMENTDATA; //Create an empty array
    } else {<!-- -->
        throw new IllegalArgumentException("Illegal Capacity: " +
                                           initialCapacity);
    }
}

Specify initial data initialization

public ArrayList(Collection<? extends E> c) {<!-- -->
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {<!-- -->
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //see 6260652 is a bug in Java and can be found in the official documentation.
        if (elementData.getClass() != Object[].class)
            //Determine whether c.toArray is of Object type. If not, use Arrays.copyOf to convert it to Object type.
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {<!-- -->
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Reasons to determine whether c.toArray is an Object type array:

public class Test {<!-- -->
    public static void main(String[] args) {<!-- -->
        List<String> list1 = Arrays.asList("hello", "world");
        //The toArray method returns the Object type
        Object[] array = list1.toArray();
        // Print out the String, indicating that the data stored in the array is actually String type data.
        System.out.println(array.getClass().getSimpleName());
        // Store Object type data in the array and report ArrayStoreException
        // Because jvm does not know whether the real type of the Object you save is String, you need to convert the array that is not an Object type into a real Object type.
        array[0] = new Object();
    }
}

This problem has been solved in Java9

Add

  1. Determine whether expansion is needed
  2. If you don’t need it, just assign it directly.
  3. Expand the capacity if necessary, and then assign the value after the expansion. This simple assignment has no lock control and is unsafe for operating threads.
public boolean add(E e) {<!-- -->
    //Check whether expansion is needed
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size + + ] = e;
    return true;
}

public void add(int index, E element) {<!-- -->
     rangeCheckForAdd(index);

     ensureCapacityInternal(size + 1); // Increments modCount!!
     //Move all elements behind the index in the array by one position. A total of size - index elements need to be moved. Then place the new element at the index position in the array, and add 1 to the number of elements in the ArrayList.
     System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
     elementData[index] = element;
     size + + ;
}

private void ensureCapacityInternal(int minCapacity) {<!-- -->
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//Calculate the length of the array
private static int calculateCapacity(Object[] elementData, int minCapacity) {<!-- -->
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {<!-- -->
        //If the array is empty, return the larger of the minimum length required for the array after adding this element and the default initialization length of ArrayList
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//Determine whether expansion is needed
private void ensureExplicitCapacity(int minCapacity) {<!-- -->
    modCount + + ; //Increase the number of structural modifications. Record the number of modifications of the collection, that is, its value will be increased by 1 every time it is added or removed.

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//Expansion
private void grow(int minCapacity) {<!-- -->
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //Expand the array to half its original capacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        //Compare the expanded capacity with the minimum required capacity of the array
        newCapacity = minCapacity;
    //If the capacity after expansion exceeds the maximum capacity
    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);
}

//Processing when the capacity exceeds the maximum capacity after expansion
//If the minimum capacity exceeds the int range, overflow occurs and an exception is thrown.
//Otherwise, if Integer.MAX_VALUE - 8 < minCapacity < Integer.MAX_VALUE, directly expand the capacity to Integer.MAX_VALUE
//If the required minimum capacity has not reached MAX_ARRAY_SIZE, directly expand it to MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {<!-- -->
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Expansion:

  1. Calculate the new length and assign it to 1.5 times the original length
  2. If the calculated new length is less than the minimum length of the required space, assign the new length to the minimum required length.
  3. If new length exceeds maximum capacity (Integer.MAX_VALUE – 8) call hugeCapacity
  4. After finally getting the new expanded capacity, use Arrays.copyOf to create a new array and copy the original array there.

The essence of expansion is to copy the array.

Additional:

Overflow-conscious code refers to preventing overflow, such as using a – b > 0 instead of a > b

There are two array copy methods: Arrays.copyOf() method, System.arraycopy() method

In fact, the bottom layer of the Arrays.copyOf() method calls the System.arraycopy() method, and the System.arraycopy() method is a Native method.

Delete

There is no verification of null when adding, so null values are allowed to be deleted when deleting

Index deletion

  1. Index bounds checking
  2. Increase the number of modifications
  3. Record the deleted element value
  4. If the deleted element is not at the last position, move all subsequent elements forward.
  5. The last element becomes null so that it can be collected by the garbage collector, size – –
  6. Returns the value of the deleted element
public E remove(int index) {<!-- -->
    //index bounds check
    rangeCheck(index);
    modCount + + ;
    E oldValue = elementData(index);

    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

    return oldValue;
}

Delete the specified element

  1. Check if element is null
  2. If it is null, search whether there is a null element in the collection. After finding it, delete it according to the index and return true. If it is not found, it returns false.
  3. If not null, traverse the elements in the collection according to the index and compare them one by one using equals. After the comparison is successful, delete according to the index and return true. If not found, return false.
public boolean remove(Object o) {<!-- -->
    if (o == null) {<!-- -->
        for (int index = 0; index < size; index + + )
            if (elementData[index] == null) {<!-- -->
                fastRemove(index);
                return true;
            }
    } else {<!-- -->
        for (int index = 0; index < size; index + + )
            if (o.equals(elementData[index])) {<!-- -->
                fastRemove(index);
                return true;
            }
    }
    return false;
}

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
}

Iterator

To implement an iterator, you need to implement the java.util.Iterator interface

//Returns the iterator object, pointing to the 0 index of the current collection by default
public Iterator<E> iterator() {<!-- -->
    return new Itr();
}

public interface Iterator<E> {<!-- -->
    //Determine whether there is an element at the current position
    boolean hasNext();
    //Get the current position element and move the iterator object to the next position
    E next();
    //Remove the previous element pointed to by the pointer
    default void remove() {<!-- -->
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {<!-- -->
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

ArrayList’s own iterator is called Itr, which is an internal class of ArrayList

hasNext
//Represents a pointer to the current element, the default is 0
int cursor; // index of next element to return
//1. When adding, it can represent the index of the last operation. 2. Deletion scene: Set it to -1 after the deletion is completed to prevent repeated deletion.
int lastRet = -1; // index of last element returned; -1 if no such
//expectedModCount represents the expected version number during the iteration process; modCount represents the actual version number of the array
//Judgment of concurrent modification exception problems
int expectedModCount = modCount;

Itr() {<!-- -->}

public boolean hasNext() {<!-- -->
    return cursor != size;
}
next method
public E next() {<!-- -->
    checkForCommodification();
    int i = cursor;//Record the current pointer index position
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;//Move the pointer one position backward
    return (E) elementData[lastRet = i];//Return the previous element and change the index of the previous operation
}

//Check whether concurrent modification exceptions occur (so collections cannot be added or deleted during the traversal process, otherwise an exception will be thrown)
final void checkForComodification() {<!-- -->
    if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
}
remove method
//Delete the previous element pointed to by the pointer
public void remove() {<!-- -->
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForCommodification();

    try {<!-- -->
        ArrayList.this.remove(lastRet);
        //Because the deletion of the set is used, the subsequent elements must be moved forward, so the pointer to the current element must become the previous one.
        cursor = lastRet;
        lastRet = -1;//Prevent duplicate deletion
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {<!-- -->
        throw new ConcurrentModificationException();
    }
}

List iterator

Inherited iterator, compared to the iterator, has an add method, which can add elements during traversal, and also has the hasPrevious and previous methods, which can traverse the collection backwards.

Thinking

transient Object[] elementData; // non-private to simplify nested class access
  • ArrayList supports serialization, but why do we ignore the underlying array when serializing using keywords?

Because ArrayList has rewritten the serialization and deserialization methods (writeObject and readObject) itself, the purpose is to prevent expansion from causing the array to have a large capacity, but the number of elements is very small, and the remaining nulls occupy memory, so ArrayList rewrites it itself The serialization method only serializes useful elements.

The past is dark and cannot be pursued, but the road to the future is bright and brilliant.