`ArrayList` / `Vector` 动态数组源码

概述

ArrayList 和 Vector 是 Java 集合框架中最基础的两个动态数组实现。它们都基于 Object[] 内部数组实现随机访问，支持自动扩容。

ArrayList 是 Java 集合框架中的主力军，以非同步的方式提供了高效的随机访问和尾部插入。Vector 是 JDK 1.0 遗留的同步类，所有方法都被 synchronized 修饰，性能较低但线程安全。

Arrays 工具类为 ArrayList 提供了底层数组操作支持，Collections.synchronizedList() 则提供了比 Vector 更灵活的同步包装方案。

本文基于 OpenJDK 21 源码，从内部数组结构开始，逐层深入到扩容、增删改查、迭代器、子列表视图等核心操作实现。

本文基于 OpenJDK 21 源码分析，关键实现会对比 JDK 8 到 JDK 21 的版本差异。

核心源码解析

① `ArrayList` 内部数组 `elementData`

ArrayList 使用 transient Object[] elementData 作为底层存储。核心定义如下：

java

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;
    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;
}

transient 修饰：防止默认序列化直接序列化整个数组（可能包含大量 null），由自定义的 writeObject() / readObject() 只序列化实际元素
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：无参构造时使用，首次 add 时扩容到 DEFAULT_CAPACITY=10
EMPTY_ELEMENTDATA：指定初始容量为 0 时使用

无参构造器：

java

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

② `grow()` 的 1.5 倍扩容

当 add() 发现容量不足时，调用 grow() 扩容：

java

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,  // 最小增长量
                oldCapacity >> 1);          // 首选增长量（原容量 1.5 倍）
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

oldCapacity >> 1 = 原容量的一半，加上原容量即为 1.5 倍
ArraysSupport.newLength() 还会确保新容量不小于 minCapacity
Arrays.copyOf() 本质是 System.arraycopy() 的包装，进行数组拷贝

③ `add(E)` 的 `ensureCapacityInternal()`

java

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

懒加载流程：

无参构造 → DEFAULTCAPACITY_EMPTY_ELEMENTDATA
首次 add → grow() 检测到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA → 创建容量为 max(10, minCapacity) 的新数组
后续 add → 已满则调用 grow() 1.5 倍扩容

④ `get(int)` / `set(int, E)` 的 O(1) 直接索引

java

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

Objects.checkIndex() 进行范围检查（越界抛 IndexOutOfBoundsException）
elementData(index) 直接返回 elementData[index] — O(1) 随机访问

⑤ `remove(int)` 的 `System.arraycopy()` 移动

java

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

删除中间元素需要移动后续所有元素：numMoved = size - index - 1
末尾元素置 null，辅助 GC

⑥ `Itr` 迭代器的 `expectedModCount` 快速失败

java

private class Itr implements Iterator<E> {
    int cursor;       // 下一个返回元素的索引
    int lastRet = -1; // 上一个返回元素的索引（-1 表示无）
    int expectedModCount = modCount;
}

java

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

迭代器创建时记录 expectedModCount = modCount
每次 next() / remove() 调用 checkForComodification()
迭代过程中若外部通过 list.add() / list.remove() 修改结构，modCount 变化，触发快速失败

ArrayList 的 forEach() 和 spliterator() 同样有类似的并发修改检测。

⑦ `SubList` 的视图机制

java

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

SubList 是 ArrayList 的内部类，不是独立拷贝，而是原列表的视图：

java

private class SubList extends AbstractList<E> implements RandomAccess {
    private final ArrayList<E> root;
    private final int parentOffset;
    private final int size;
    // 操作直接委托给 root
    public E get(int index) {
        Objects.checkIndex(index, size);
        return root.elementData(offset + index);
    }
}

SubList 上的所有读写操作直接影响原 ArrayList
对 SubList 的 add / remove 也会修改原列表的 size 和 modCount

⑧ `Vector` vs `ArrayList` 的区别

对比维度	`ArrayList`	`Vector`
线程安全	非同步	`synchronized` 方法
扩容策略	1.5 倍	可指定 `capacityIncrement`，未指定则 2 倍
迭代器	`fail-fast`	`fail-fast` + `Enumeration`
性能	高	低（同步开销）
出现时间	JDK 1.2	JDK 1.0（遗留类）
继承结构	`AbstractList`	`AbstractList`

Vector 的扩容逻辑：

java

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    // capacityIncrement 可自定义，默认 0 → 2 倍扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

⑨ `Vector` 的 `Enumeration` 遗留迭代器

java

public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;
        public boolean hasMoreElements() {
            return count < elementCount;
        }
        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

Enumeration 是 JDK 1.0 遗留接口，已被 Iterator 取代
不支持 remove() 操作
无 fail-fast 机制

⑩ `ArrayList` 的 `toArray(T[])` 实现

java

@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;
}

若传入数组容量足够，直接 System.arraycopy() 复制
若不足，通过 Arrays.copyOf() 创建新数组
若传入数组更大，在 size 位置置 null 标识结束

总结

ArrayList 是日常开发中最常用的集合类之一。其核心设计围绕 Object[] 数组展开：

O(1) 随机访问：通过数组下标直接访问
O(n) 中间插入/删除：需要 System.arraycopy() 移动元素
自动扩容：懒加载 + 1.5 倍扩容
Fail-Fast 迭代器：通过 modCount 检测并发修改
视图机制：SubList 提供原列表的切片视图

Vector 作为遗留同步类，在并发场景下推荐使用 Collections.synchronizedList() 或 CopyOnWriteArrayList 替代。

ArrayList / Vector 动态数组源码 ​

概述 ​

核心源码解析 ​

① ArrayList 内部数组 elementData ​

② grow() 的 1.5 倍扩容 ​

③ add(E) 的 ensureCapacityInternal() ​

④ get(int) / set(int, E) 的 O(1) 直接索引 ​

⑤ remove(int) 的 System.arraycopy() 移动 ​

⑥ Itr 迭代器的 expectedModCount 快速失败 ​

⑦ SubList 的视图机制 ​

⑧ Vector vs ArrayList 的区别 ​

⑨ Vector 的 Enumeration 遗留迭代器 ​

⑩ ArrayList 的 toArray(T[]) 实现 ​

总结 ​

`ArrayList` / `Vector` 动态数组源码

概述

核心源码解析

① `ArrayList` 内部数组 `elementData`

② `grow()` 的 1.5 倍扩容

③ `add(E)` 的 `ensureCapacityInternal()`

④ `get(int)` / `set(int, E)` 的 O(1) 直接索引

⑤ `remove(int)` 的 `System.arraycopy()` 移动

⑥ `Itr` 迭代器的 `expectedModCount` 快速失败

⑦ `SubList` 的视图机制

⑧ `Vector` vs `ArrayList` 的区别

⑨ `Vector` 的 `Enumeration` 遗留迭代器

⑩ `ArrayList` 的 `toArray(T[])` 实现

总结