ArrayList 扩容原理：容量翻倍的代价

ArrayList 的底层

ArrayList 的底层是一个数组：

public class ArrayList<E> {
    transient Object[] elementData; // 存储元素的数组
    private int size;              // 元素数量
}

当元素数量超过数组容量时，需要扩容。

---

扩容时机

创建 ArrayList：elementData = []
添加第一个元素：elementData = new Object[10]（默认容量 10）
元素超过 10 个：扩容

---

扩容公式

新容量 = 旧容量 + 旧容量 / 2
新容量 = 旧容量 * 1.5

容量变化：0 → 10 → 15 → 22 → 33 → 50 → 75 → 113 → ...

扩容演示

ArrayList<Integer> list = new ArrayList<>();

// 通过反射查看容量变化
for (int i = 0; i < 25; i++) {
    list.add(i);
    System.out.println("第 " + (i+1) + " 个元素后，容量 = " + getCapacity(list));
}

// 典型输出：
// 第 1 个元素后，容量 = 10
// 第 11 个元素后，容量 = 15（第一次扩容）
// 第 16 个元素后，容量 = 22（第二次扩容）
// 第 23 个元素后，容量 = 33（第三次扩容）

---

扩容的成本

扩容时需要：

1. 创建新数组（容量更大）
2. 复制所有元素到新数组

// 扩容的核心代码
void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍

    Object[] newArray = new Object[newCapacity];
    System.arraycopy(elementData, 0, newArray, 0, size);
    elementData = newArray;
}

这就是为什么预分配容量很重要。

---

性能对比

// 添加 100 万元素
// 方式 1：默认容量
ArrayList<Integer> list1 = new ArrayList<>();
// ~17 次扩容，每次都复制元素
long t1 = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) list1.add(i);
System.out.printf("默认容量: %.0f ms%n", (System.nanoTime() - t1) / 1_000_000.0);

// 方式 2：预估容量
ArrayList<Integer> list2 = new ArrayList<>(1_000_000);
long t2 = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) list2.add(i);
System.out.printf("预估容量: %.0f ms%n", (System.nanoTime() - t2) / 1_000_000.0);

// 典型结果：预估容量快 3-5 倍

---

ensureCapacity：提前扩容

如果知道大概要添加多少元素，可以用 ensureCapacity 提前扩容：

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(100000); // 一次性扩容到 100000
// 后续 add 操作不会触发扩容

---

trimToSize：收缩容量

ArrayList 不会自动缩小。如果想释放多余容量：

// ❌ ArrayList 没有 trimToSize
// list.trimToSize(); // 编译错误！

// ✅ 正确做法：创建新实例
ArrayList<Integer> trimmed = new ArrayList<>(list);

---

总结

要点	说明
默认容量	首次添加时分配 10
扩容倍数	1.5 倍
扩容成本	创建新数组 + 复制所有元素
优化方式	预分配容量 new ArrayList<>(size)

---

相关链接

• ArrayList 底层实现
• HashMap 扩容机制