深入 Java 源码:ArrayList 的神秘世界

在 Java 丰富的类库中，ArrayList 犹如一颗璀璨的明珠，为开发者提供了便捷高效的数据存储和操作方式。让我们一同揭开它源码的神秘面纱，探索其内部的精妙机制。

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.RandomAccess;

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

    // 默认的初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 表示空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 另一种表示空数组，用于特定情况
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 用于存储元素的数组
    transient Object[] elementData;

    // 列表中实际元素的数量
    private int size;

    // 无参构造函数，初始化时使用特定的空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // 带初始容量参数的构造函数
    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);
        }
    }

    // 基于另一个集合创建 ArrayList 的构造函数
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length)!= 0) {
            // 确保数组类型是 Object[]
            if (elementData.getClass()!= Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    // 获取列表中元素的数量
    @Override
    public int size() {
        return size;
    }

    // 判断列表是否为空
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断列表是否包含指定元素
    @Override
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    // 查找指定元素在列表中的索引，如果不存在则返回 -1
    @Override
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i] == null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    // 查找指定元素在列表中最后出现的索引，如果不存在则返回 -1
    @Override
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size - 1; i >= 0; i--)
                if (elementData[i] == null)
                    return i;
        } else {
            for (int i = size - 1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    // 获取指定索引位置的元素
    @Override
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

    // 检查索引是否合法
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    // 根据索引获取元素，并进行类型转换
    E elementData(int index) {
        return (E) elementData[index];
    }

    // 将列表转换为数组
    @Override
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    // 将列表元素复制到指定的数组中
    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 如果给定的数组长度不够，创建一个新的合适长度的数组
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());

        System.arraycopy(elementData, 0, a, 0, size);

        if (a.length > size)
            a[size] = null;

        return a;
    }

    // 设置指定索引位置的元素值
    @Override
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    // 在指定索引位置添加元素
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // 检查并确保容量足够
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    // 检查添加元素时索引的合法性
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    // 向列表末尾添加元素
    @Override
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保容量足够
        elementData[size++] = e;
        return true;
    }

    // 确保内部容量足够，如果不够则进行扩容
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    // 明确地确保容量足够，如果需要则进行扩容操作
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // 扩容方法
    private void grow(int minCapacity) {
        // 获取当前容量
        int oldCapacity = elementData.length;
        // 新容量为旧容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 复制元素到新的扩容后的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    // 从列表中删除指定索引位置的元素
    @Override
    public E remove(int index) {
        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;  // 让垃圾回收器可以回收

        return oldValue;
    }

    // 根据元素值删除列表中的第一个匹配元素
    @Override
    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;  // 让垃圾回收器可以回收
    }

    // 清空列表
    @Override
    public void clear() {
        modCount++;

        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    // 克隆方法
    @Override
    public ArrayList<E> clone() {
        try {
            ArrayList<E> v = (ArrayList<E>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }
}

关键要点解析：

1. 成员变量：DEFAULT_CAPACITY = 10：定义了默认的初始容量，当创建 ArrayList 时如果未指定初始容量，且后续添加元素导致需要扩容时，会以 10 为初始容量进行扩容。EMPTY_ELEMENTDATA = {} 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}：用于表示空数组，在不同的初始化场景中使用。elementData：实际存储元素的数组。size：记录数组中实际存储的元素数量。
2. 构造函数：无参构造函数中，将 elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，表示初始时数组为空，后续添加元素时再进行容量分配。带初始容量参数的构造函数，根据传入的容量值创建相应大小的数组，如果容量值不合法则抛出异常。基于另一个集合创建的构造函数，将传入集合的元素复制到新的数组中，并处理数组类型的转换。
3. 添加元素：add 方法：首先调用 ensureCapacityInternal 方法确保有足够的容量来添加新元素。ensureCapacityInternal 方法：如果当前数组是默认的空数组，会将所需最小容量与默认容量比较并取较大值。然后调用 ensureExplicitCapacity 方法。ensureExplicitCapacity 方法：检查所需容量是否超过当前数组长度，如果是则调用 grow 方法进行扩容。grow 方法：计算新的容量（通常为原容量的 1.5 倍），并通过 Arrays.copyOf 方法将原数组元素复制到新的扩容后的数组。

4. 获取元素：get 方法：通过 rangeCheck 方法检查索引是否合法，然后通过数组索引直接获取元素，并进行类型转换返回。
5. 删除元素：remove 方法：通过 rangeCheck 方法检查索引合法性。然后将指定索引后面的元素向前移动，最后将数组末尾的元素置为 null 以方便垃圾回收，并减少数组的实际元素数量。
6. 迭代器的快速失败机制：内部有一个 modCount 变量，在对集合进行结构修改操作（如添加、删除元素）时会增加其值。迭代器在遍历过程中会检查 modCount 是否被修改，如果被修改则抛出 ConcurrentModificationException 异常，以保证在迭代过程中集合的结构不被意外修改。

ArrayList 适用于需要快速随机访问和频繁添加 / 删除元素末尾操作的场景，但在频繁插入和删除元素中间位置时，可能会有性能开销，因为需要移动大量元素。