Even some people say that ArrayList is twice as large. Today, I will take you to tear up the ArrayList source code

ArrayList It is the most commonly used collection in our development , But many people do not know its source code , Lead to interview , A slightly more in-depth question from the interviewer , There is no answer , Let's explore it today ArrayList Source code .

1. brief introduction

• ArrayList At the bottom is an array , Allow elements to be null, Dynamic capacity expansion
• size、isEmpty、get、set、add The time complexity of such methods is O (1)
• Non-thread safety , Concurrent modification , Will throw out ConcurrentModificationException

2. initialization

//  Initial capacity 
private static final int DEFAULT_CAPACITY = 10;

//  An empty array 
private static final Object[] EMPTY_ELEMENTDATA = {};

//  Default empty array 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//  Array of storage elements 
transient Object[] elementData;

//  No parameter initialization , The default is an empty array 
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//  Parameter initialization , Specified capacity 
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

Bear in mind ： During parameterless initialization , The default is an empty array , Capacity size is not initialized , The capacity is initialized only when the element is added for the first time .

3. Additive elements

public boolean add(E e) {
  //  Make sure the array has enough capacity ,size It's the number of elements 
  ensureCapacityInternal(size + 1);
  //  Direct assignment 
  elementData[size++] = e;
  return true;
}

//  Make sure the array has enough capacity 
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//  Calculate the minimum capacity required 
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  	//  If the array equals an empty array , The minimum capacity is 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
  	//  If the required minimum capacity is greater than the array length , Just expand 
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Take a look at the expansion logic ：

//  Capacity expansion , Is to copy the old data into the new array 
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1  It's a oldCapacity Divide 2, intend 1.5 Double expansion 
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  //  If the capacity after expansion is less than the minimum capacity , The capacity after expansion is equal to the minimum capacity 
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  //  If the capacity after expansion is greater than Integer The maximum of , Just use Integer Maximum 
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  //  Expand and assign values to the original array 
  elementData = Arrays.copyOf(elementData, newCapacity);
}

You can see ：

• The expansion is based on the original capacity 1.5 Double expansion , It's not about doubling the capacity
• The maximum capacity is Integer The maximum of
• When adding elements , There is no element validation , It can be null

Take another look at the logic of array copying , It's all here Arrays Class ：

/**
 * @param original   Original array 
 * @param newLength  New capacity size 
 */
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    //  Create a new array , Capacity is the new capacity size 
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  	//  Copy the elements of the original array to the new array 
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

Finally called System Class , yes native Method ：

/**
 * @param src      Original array 
 * @param srcPos   The starting position of the original array 
 * @param dest     Target array 
 * @param destPos  The starting position of the target array 
 * @param length   Length copied 
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

4. Delete single element

public boolean remove(Object o) {
  	//  Determine whether the element to be deleted is null
    if (o == null) {
      	//  Traversal array 
        for (int index = 0; index < size; index++)
          	//  If it is equal to the element in the current position , Just delete the element in the current position 
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
      	//  Traversal array 
        for (int index = 0; index < size; index++)
          	//  If it is equal to the element in the current position , Just delete the element in the current position 
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//  Delete elements at this location 
private void fastRemove(int index) {
    modCount++;
  	//  Count the number of elements that need to be moved 
    int numMoved = size - index - 1;
    if (numMoved > 0)
      	//  from index+1 Position start copy , That is, the following elements move one position to the left as a whole 
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
  	//  The last element of the array is assigned null, Prevent memory leaks 
    elementData[--size] = null;
}

You can know , Remove elements , That's traversing the array , The loop compares whether it is equal to the target value . If equal , Just move the whole element behind this position to the left by one position , Then assign the value of the last element of the array to null.

5. Batch deletion

//  Batch deletion ArrayList And collection c The elements that exist 
public boolean removeAll(Collection<?> c) {
    //  Non empty verification 
    Objects.requireNonNull(c);
    //  Batch deletion 
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement){
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                //  Move the elements that need to be preserved to the left 
                elementData[w++] = elementData[r];
    } finally {
				//  When something goes wrong , It may not be equal 
        if (r != size) {
            // 1： Maybe it's from above for An exception occurred in the loop 
            // 2： Other threads may have added elements 
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
      	//  Assign an element that does not need to be preserved to null
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

You can know , When deleting in batch , Only one copy of the array will be made , Than using for Circular single deletion is more efficient , So when deleting a batch of elements , As far as possible with removeAll() Method .

5. summary

This paper analyzes ArrayList The initialization 、put、add、remove、 Dynamic capacity expansion and other methods of the underlying source code , I'm sure you're interested in ArrayList With a deeper understanding , Let's learn the next chapter LinkedList Source code .