关于 ArrayList

发表于 2019-04-03 更新于 2023-12-16 分类于 Java后时代

包括之前的 HashMap 和 LinkedList, 都是基于 JDK 7的(应该全面拥抱JDK 8了)。

ArrayList 的 DOC 注释

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 * (ArrayList) 通过 List 接口实现的容量可变数组。实现了 list 的所有可选操作(方法)，并且允许添加所有元素，包括 null。除了实现了 List 的接口，ArrayList 还提供了修改用来容纳 list 的数组的 size 的方法(ArrayList 是非线程安全的，除此以外大致上与 Vector 相同)。
 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.
 * size，isEmpty，get，set，iterator 方法和 listIterator 操作的时间复杂度是O(1)的(常数级)。add() 方法的时间复杂度是O(1)+的(amortized constant time)(因为涉及到list 扩容，扩容也需要时间，需要把这部分时间平均分摊到每次 add 操作中。)，也就是说，添加元素的时间复杂度为O(n)。其他操作的时间复杂度大致为O(n)，常量值 n 通常要比 LinkedList 的时间复杂度中常量值要小(即，其他操作要比 LinkedList 的其他操作要快一点)。
 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.
 * 每一个 ArrayList 实例都有一个 capacity(容量)属性，该属性不小于 list 的 size。当向 ArrayList 中添加元素时，它的 capacity 会自动增长。除了添加一个元素具有固定的摊余时间成本之外，增长规则的细节没有被指定。
 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 * 在程序中添加大量元素之前，可以调用 ensureCapacity() 方法来对 ArrayList 进行扩容。这样可以减少多次扩容所花费的时间(可以减少扩容的次数)
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 * 需要注意的是，ArrayList 对 List 的实现是非同步的。如果多线程同时请求对 ArrayList 的访问，并且至少会有一个线程对 ArrayList 进行结构性修改(结构性修改是指添加或删除一个以上的元素，或者显式的修改了其数组的大小。仅仅修改元素值并非结构性修改)，那么务必在 ArrayList 外部进行 synchronized 修饰。这通常是通过 synchronized 修饰 封装了 list 的某个对象来实现的。
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 * 如果(手头儿)没有这样的对象，那么应该用 Collections.synchronizedList 包裹 list。该操作最好在创建 list 时进行，以防意外的非同步访问 list。
 * <p><a name="fail-fast"/>
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 * 通过 ArrayList 的 iterator() 方法，或者 listIterator(int) 方法返回的 iterator 都是 fail-fast(快速失效)的：如果在创建 iterator 之后，任何对 list 的结构性修改，都会抛出 ConcurrentModificationException，除了 iterator 本身的 remove() 和 add() 方法。因此，在面临并发对 list 的修改时，iterator 会快速而干净的失效，而不是在未来不确定的时间冒着任意的、不确定的风险。
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 另外，需要注意的是，，iterator 的 fail-fast 行为是不能被保证的，，通常来说，在并发非同步对 list 的修改时，任何硬性的保证都是不可能的。fail-fast 会让 iterator 尽可能抛出 ConcurrentModificationException。因此，在程序中通过依赖抛出 ConcurrentModificationException 异常来保证自身的正常运行是错误的：fail-fast 行为只应该用来 debug。
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
 */

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 的类属性及构造方法

/**
 * Default initial capacity.
 * 默认初始 capacity, 10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 对所有由无参构造函数创建的空实例共享的空数组对象
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 * 临时用来存储 ArrayList 中元素的数组。 ArrayList 对象的长度就是这个缓存数组的长度。任何空 ArrayList ，且 elementData == EMPTY_ELEMENTDATA，在添加第一个元素时，数组将被扩展到默认大小(DEFAULT_CAPACITY, 10)。
 * (因为是临时的，所以用 transient 修饰，不会被序列化)
 */
private transient Object[] elementData;

/**
 * The size of the ArrayList (the number of elements it contains).
 * ArrayList 的 size(包含的元素的数量)。
 * @serial
 */
private int size;

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 * 允许分配给数组的最大的容量。
 * 一些虚拟机实现会在数组预留一些 header words。
 * 视图分配更大的数组可能会造成 OOM：所需数组大小超出虚拟机限制。
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Constructs an empty list with the specified initial capacity.
 * 通过指定初始 capacity 大小来构造一个空 list
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    super();
    // 初始容量小于零时，会抛出 IllegalArgumentException
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    //  初始化指定大小的临时对象数组                                       
    this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 * 构造一个空 list，当向该 list 添加元素时，需先扩展数组到默认初始容量大小，即 10.
 */
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 按照 collection 迭代器返回元素的顺序构造包含指定 collection 的元素的 list。
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    // 如果 c 为 null，此处会抛 NPE
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    // 如果 elementData 不是对象数组，还需要将其复制到新的对象数组中。
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

add()

/**
 * Appends the specified element to the end of this list.
 * 添加指定元素到 list 末尾元素后边。
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    // 确保内部数组容量足够大，初始状态下 size 为 0。
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 如果 ArrayList 由无参构造方法构造，则 minCapacity 为 1。
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 确保扩容到指定大小的容量
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    // 结构修改次数 +1
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 * 扩容，以容纳指定长度的最小数量的元素
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    // 原容量
    int oldCapacity = elementData.length;
    // 新容量 = oldCapacity * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量小于指定的最小容量，则新容量为指定的大小
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于允许的最大容量值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 通常 minCapacity = size + 1，所以大部分情况都是执行到这里
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    // 带符号二进制溢出，符号位为 1，小于零，，即 OOM。
    if (minCapacity < 0) // overflow
       throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
       Integer.MAX_VALUE :
       MAX_ARRAY_SIZE;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 * 添加指定元素到指定位置。将当前索引位置的元素(如果有的话)及其后边的元素统一右移。
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 检查 index 是否不小于零，且小于 size
    rangeCheckForAdd(index);
    // list 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 调用 native 方法复制 插入索引位置之后部分的数组 到原数组中
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
/**
 * A version of rangeCheck used by add and addAll.
 * 为 add() 和 addAll() 方法准备的另一个版本的 rangeCheck 方法。
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * @param      src      the source array.
 * @param      srcPos   starting position in the source array.
 * @param      dest     the destination array.
 * @param      destPos  starting position in the destination data.
 * @param      length   the number of array elements to be copied.
 */
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

get()

/**
 * Returns the element at the specified position in this list.
 * 返回 list 中指定位置的元素
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);
    // 如果索引合规，则至今返回数组相应索引位置的元素。
    return elementData(index);
}

/**
 * Checks if the given index is in range.  If not, throws an appropriate
 * runtime exception.  This method does *not* check if the index is
 * negative: It is always used immediately prior to an array access,
 * which throws an ArrayIndexOutOfBoundsException if index is negative.
 * 检查指定的索引是否在范围内。如果不在，将抛出合适的运行时异常。该方法不会检查索引是否为负：索引总是在访问数组之前立即使用，，如果在索引为负，会抛出 ArrayIndexOutOfBoundsException 异常。
 */
private void rangeCheck(int index) {
    // 如果索引大于数组的实际大小，会抛出数组越界异常。
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * Constructs an IndexOutOfBoundsException detail message.
 * Of the many possible refactorings of the error handling code,
 * this "outlining" performs best with both server and client VMs.
 * 构建数组越界异常的详情信息。在很多错误处理代码可能的重构中，这个详情大纲一直在服务器模式和客户端模式中表现的一直很好。
 */
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

set()

/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 * 用指定的元素替换 list 中指定位置的元素
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    // 是否大于数组的 size
    rangeCheck(index);
    // 记录数组中当前位置的元素
    E oldValue = elementData(index);
    // 替换指定索引位置为新元素
    elementData[index] = element;
    // 返回原索引位置的元素
    return oldValue;
}

remove()

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 * 移除当前 list 中指定位置上的元素。将该位置后边的元素左移(当前索引减一)
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    // 检查索引是否超出数组的 size
    rangeCheck(index);
    // list 结构性更改次数 +1
    modCount++;
    // 记录数组当前索引原元素
    E oldValue = elementData(index);
    // 计算要移动的数组的长度。
    int numMoved = size - index - 1;
    // 如果删除的不是 list 的末尾元素，则将要删除的索引位之后的元素向左移动一位。
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 数组长度-1，并将更新后的数组末尾元素置空
    // 此处留坑，，在我的印象中，假如数组长度为10，那么即使是只有零索引处有值，其他位置的元素皆为空，其他对象还持有该数组对象的引用，那么GC时也不会将该数组对象回收。
    elementData[--size] = null; // clear to let GC do its work
    // 返回索引位置原元素
    return oldValue;
}

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 * 从当前 list 中删除指定元素的第一个匹配项，如果 list 中存在指定元素的话。严谨来说是删除索引值最小的匹配项，像是满足这样的条件：(o==null?get(i)==null:o.equals(get(i)))，如果 list 中存在 o 的话。如果 list 中存在 o，则返回 true(或者说，本次调用导致了 list 改变)
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    // 遍历删除找到的第一个 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 remove method that skips bounds checking and does not
 * return the value removed.
 * 私有删除方法，该方法跳过了索引是否越界的检查，且不返回删除的元素。精简版的 remove()
 */
private void fastRemove(int index) {
    // 结构性更改次数 +1
    // ...
    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

/**
 * Returns an iterator over the elements in this list in proper sequence.
 * 以正确的顺序返回该 list 中元素的迭代器
 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 * 返回的 iterator 是 fail-fast 的
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}
/**
 * An optimized version of AbstractList.Itr
 * AbstractList.Itr 的优化版本
 */
private class Itr implements Iterator<E> {
    // index of next element to return 要返回的下一个元素的索引
    int cursor;
    // index of last element returned; -1 if no such 上一个返回元素的索引，如果该元素不复存在(调用iterator.remove()删除当前元素)，则赋值为 -1
    int lastRet = -1;
    // 记录当前 list 结构性修改次数
    int expectedModCount = modCount;

    // 是否还有未迭代过的元素
    public boolean hasNext() {
        // 如果下一个要返回的元素的索引值不等于(即，小于)数组长度，则说明未迭代完成
        return cursor != size;
    }

    // 返回下一个要迭代的元素
    @SuppressWarnings("unchecked")
    public E next() {
        // 检查记录 list 结构性更改次数后(即，私有内部类 Itr 初始化完成后)，是否有其他操作对 list 进行过结构性修改。如果有，则抛出 ConcurrentModificationException。
        checkForComodification();
        int i = cursor;
        // 如果要迭代的下一个元素的索引值不小于数组的长度，则抛出 NoSuchElementException
        if (i >= size)
            throw new NoSuchElementException();
        // 复制当前 list 的内部实现数组 elementData
        Object[] elementData = ArrayList.this.elementData;
        // 如果要迭代的下一个元素的索引不小于 elementData 的长度，则抛出 ConcurrentModificationException。
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 将 cursor 指向要迭代的下一个(本次 next 方法调用完成之后)元素的索引
        cursor = i + 1;
        // 更新返回的最后一个元素的索引值，同时返回本次要迭代的元素
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        // 如果当前元素(next 方法中，int i = cursor；lastRet = i;)索引小于零，抛出 IllegalStateException，此时 list 处于非法状态。
        if (lastRet < 0)
            throw new IllegalStateException();
        // 检查 iterator 初始化之后，是否有其他线程对 list 进行了结构性修改。
        checkForComodification();

        try {
            // 调用 ArrayList 的 remove() 移除迭代器当前指向的元素
            ArrayList.this.remove(lastRet);
            // 进行 remove 操作后，目标索引后边的元素左移，即目标索引指向新的(尚未迭代过)元素。将迭代器下次要返回的元素指向目标索引的元素
            cursor = lastRet;
            // 本次迭代的元素已被删除，所以为 lastRet 赋值 -1
            lastRet = -1;
            // 更新 list 结构性更改次数
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

总结

ArrayList 是容量可以改变的非线程安全集合。内部实现使用数组进行存储，集合扩容时会创建更大的数组空间，把原有数据复制到新数组中。ArrayList 支持对元素的快速随机访问，但是插入与删除时速度通常很慢，因为这个过程很有可能需要移动其他元素。

– 码出高效 Java 开发手册 P155