ArrayList 扩容机制：容量翻倍的秘密

扩容触发时机

ArrayList 不是一开始就把容量撑满的。它会按需扩容：

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

// 容量轨迹：
add("A")  → 容量从 0 → 10    （首次添加触发）
add("B")  → 容量 10，够用
add(...)  → 容量 10，够用
...
add("K")  → 容量 10 → 15    （第 11 个元素触发）
add("L")  → 容量 15，够用
...
add("P")  → 容量 15 → 22    （第 16 个元素触发）

触发条件：当前数组容量装不下下一个元素时（size + 1 > elementData.length）

---

扩容公式：1.5 倍增长

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 如果还不够，直接用所需容量
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }

    // 超过最大容量，用 Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }

    // 创建新数组，复制元素
    elementData = Arrays.copyOf(elementData, newCapacity);
}

容量增长轨迹：

0  → 10  → 15  → 22  → 33  → 49  → 73  → 109  → 163  ...
  (首次)  ×1.5   ×1.5   ×1.5   ×1.5   ×1.5   ×1.5   ×1.5

---

扩容做了什么：两步操作

扩容不只是「扩大数组」，而是要经历两个步骤：

步骤 1：分配新数组

// 假设旧容量是 10
// 创建容量为 15 的新数组
Object[] newArray = new Object[15];

步骤 2：复制所有元素

// 将旧数组的所有元素复制到新数组
System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);

这就是为什么扩容会慢——100 万个元素的 ArrayList 扩容一次，就要复制 100 万个引用。

---

扩容图解

初始状态：容量 10，size = 5
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
0   1   2   3   4   5   6   7   8   9

添加第 11 个元素（F），触发扩容：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │   │   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14
容量从 10 → 15（1.5 倍），size = 11

---

均摊复杂度：为什么说 add 是 O(1)

有人说 ArrayList 尾部添加是 O(1)，有人说扩容时是 O(n)，到底哪个对？

都对。用均摊复杂度（Amortized）来描述：均摊 O(1)。

计算过程：假设容量是 10，添加 10 个元素：

• 前 10 次添加：每次 O(1)
• 第 11 次添加：扩容 + 复制，O(n) ≈ O(10)

均摊到 11 次操作：(10 × O(1) + O(10)) / 11 = O(1)

简单说：扩容虽然慢，但触发频率低。平均下来，每次添加还是 O(1)。

---

预扩容：避免扩容的技巧

如果你提前知道大概要存多少元素，直接指定初始容量：

import java.util.*;

public class AvoidExpandDemo {

    public static void main(String[] args) {
        // 预估要存 10000 个元素

        // ❌ 默认容量，频繁扩容
        long start = System.nanoTime();
        ArrayList<String> bad = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            bad.add("item" + i);
        }
        System.out.println("未优化: " + (System.nanoTime() - start) / 1_000_000 + " ms");

        // ✅ 一步到位
        start = System.nanoTime();
        ArrayList<String> good = new ArrayList<>(10000);
        for (int i = 0; i < 10000; i++) {
            good.add("item" + i);
        }
        System.out.println("已优化: " + (System.nanoTime() - start) / 1_000_000 + " ms");
    }
}

典型性能差异：优化后快 2-5 倍。

---

ensureCapacity：批量添加优化

如果一次性添加大量元素，用 ensureCapacity 预扩容：

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

// 批量添加前预扩容
list.ensureCapacity(10000);

for (int i = 0; i < 10000; i++) {
    list.add("item" + i);
}

或者用 Collections.addAll：

List<String> list = new ArrayList<>();
Collections.addAll(list,
    "item0", "item1", "item2", "item3", "item4",
    "item5", "item6", "item7", "item8", "item9"
    // ... 一次添加多个
);

---

trimToSize：释放多余容量

如果你已经添加完所有元素，想释放多余的容量：

ArrayList<String> list = new ArrayList<>(1000);
// 实际只用了 50 个
list.add("a");
list.add("b");
// ...

// 释放多余容量
list.trimToSize();
// 现在容量 = size = 50

System.out.println(list.size()); // 50

什么时候用 trimToSize

通常不需要调用。trimToSize 本身也有 O(n) 的成本（复制数组）。只有在确实要节省内存，且后续不会继续添加大量元素时才考虑。

---

扩容边界：最大能到多大

参数	值	说明
默认初始容量	0 → 10	首次添加时才分配
扩容倍数	1.5 倍	oldCapacity + (oldCapacity >> 1)
最大容量	Integer.MAX_VALUE - 8	约 21 亿
MAX_ARRAY_SIZE	Integer.MAX_VALUE - 8	JVM 内部限制

当容量接近 Integer.MAX_VALUE 时，再次扩容可能触发 OutOfMemoryError: Required array size too large。

---

总结

问题	答案
扩容触发时机	size + 1 > capacity 时
扩容公式	新容量 = 旧容量 × 1.5
扩容成本	O(n)：分配新数组 + 复制元素
尾部添加复杂度	均摊 O(1)
如何避免扩容	预知大小时指定初始容量
最大容量	Integer.MAX_VALUE - 8

---

相关链接

• ArrayList 底层实现
• 容量优化