当前位置：首页 > news >正文

深入理解 Java ArrayList 扩缩容机制（含源码分析）

news 来源：原创 2025/9/19 8:18:28

标签： Java, ArrayList, 集合框架, 源码分析, 扩容机制, 性能优化, CSDN

摘要： java.util.ArrayList 作为 Java 集合框架中最常用的类之一，其动态数组的特性深受开发者喜爱。然而，“动态”背后的扩容与缩容机制是怎样的？它如何影响程序性能？本文将带你深入 ArrayList 的内部，结合 JDK 源码，彻底搞懂其容量自动调整的秘密，并提供实用的性能优化建议。

文章目录

- - 1. 引言：为什么 ArrayList 需要扩缩容？
  - 2. 核心概念：`size` 与 `capacity`
  - 3. 自动扩容（Expansion）：当空间不足时
  - - 触发时机
    - 核心源码解析：`grow()` 方法
    - 扩容因子：为什么是 1.5 倍？
    - 扩容的成本
  - 4. 手动缩容（Contraction）：`trimToSize()`
  - - ArrayList 会自动缩容吗？
    - 源码解析：`trimToSize()` 方法
    - 使用场景与注意事项
  - 5. 性能考量与最佳实践
  - - 预设初始容量的重要性
    - 理解均摊时间复杂度
    - 谨慎使用 `trimToSize()`
  - 6. 总结

1. 引言：为什么 ArrayList 需要扩缩容？

ArrayList 底层是基于数组 (Object[]) 实现的。数组一旦创建，其长度是固定的。但我们使用 ArrayList 时，却可以动态地添加或删除元素，似乎没有长度限制。这正是 ArrayList 扩容机制在发挥作用。

灵活性需求： 业务场景中，我们往往无法预知一个列表最终会存储多少元素。ArrayList 的动态性使得我们无需在创建时就精确指定大小。
数组的局限： 固定长度的数组无法满足动态添加的需求。当数组满时，必须有某种机制来“扩大”存储空间。
空间与时间的权衡： 扩容机制需要在“预留过多空间造成浪费”和“频繁扩容导致性能下降”之间找到平衡。

理解 ArrayList 的扩缩容机制，有助于我们编写更高效、内存使用更合理的 Java 代码。

2. 核心概念：`size` 与 `capacity`

在深入源码之前，必须明确 ArrayList 的两个核心属性：

size: 表示 ArrayList 中实际存储的元素数量。通过 list.size() 方法获取。
capacity: 表示 ArrayList 底层数组 (elementData) 的长度（容量）。它通常大于或等于 size。ArrayList 没有直接提供 getCapacity() 方法，但可以通过反射或调试查看内部 elementData.length。

// 内部存储元素的数组
transient Object[] elementData; // non-private to simplify nested class access// 实际存储的元素数量
private int size;

size 是我们直接关心的元素个数，而 capacity 则是 ArrayList 为了容纳更多元素而预留的内部空间大小。扩缩容操作主要就是围绕调整 capacity（即 elementData 数组的长度）进行的。

3. 自动扩容（Expansion）：当空间不足时

触发时机

ArrayList 的自动扩容主要在以下几种情况发生：

调用 add(E e) 或 add(int index, E element) 时： 当添加元素前，发现 size 等于 elementData.length（即数组已满），就会触发扩容。
调用 addAll(...) 时： 计算需要添加的元素数量，如果添加后所需的总容量 (size + numNew) 超过当前 capacity，则触发扩容。
调用 ensureCapacity(int minCapacity) 时： 显式要求确保 ArrayList 至少具有 minCapacity 的容量，如果当前 capacity 小于 minCapacity，则触发扩容。

核心逻辑通常在添加元素前调用一个检查容量并可能增长的方法，例如 ensureCapacityInternal(size + 1) (对于 add(E e)）。

核心源码解析：`grow()` 方法

扩容的核心逻辑位于私有方法 grow(int minCapacity) 中（以 JDK 8/11 为例，不同版本细节可能略有差异）：

// java.util.ArrayList
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// 核心扩容逻辑：新容量 = 旧容量 + 旧容量 / 2 （即 1.5 倍）int newCapacity = oldCapacity + (oldCapacity >> 1); // >> 1 是右移一位，等效于除以2取整// 如果计算出的新容量仍然小于所需的最小容量 (例如 addAll 时)，则直接使用最小容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 防止容量过大，超过数组允许的最大值 (Integer.MAX_VALUE - 8)// MAX_ARRAY_SIZE 通常是 Integer.MAX_VALUE - 8，因为一些VM在数组头会保留字if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity); // 处理非常大的容量请求// 最关键的一步：创建新数组并复制旧数组内容// elementData = Arrays.copyOf(elementData, newCapacity); // 这个方法内部会 new 一个新数组，然后 System.arraycopy
}// (辅助方法) 处理非常大的容量请求
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 如果minCapacity已经大于MAX_ARRAY_SIZE，就取Integer.MAX_VALUE，否则取MAX_ARRAY_SIZEreturn (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

关键步骤解读：

计算新容量： newCapacity = oldCapacity + (oldCapacity >> 1)。这是 ArrayList 扩容的核心策略——将容量增加到原来的 1.5 倍。使用位运算 >> 1 比 / 2 效率略高。
最小容量检查： 如果期望的最小容量 minCapacity (例如 addAll 时需要一次性放入多个元素) 比 1.5 倍计算出的 newCapacity 还大，则直接采用 minCapacity 作为新容量。
最大容量检查： 防止整数溢出和超出 VM 对数组大小的限制 (MAX_ARRAY_SIZE)。
数据迁移： 调用 Arrays.copyOf(elementData, newCapacity)。这是扩容操作中最耗时的部分。它会：
- 创建一个新的、长度为 newCapacity 的 Object 数组。
- 使用 System.arraycopy() 将旧数组 (elementData) 中的所有元素（size 个）复制到新数组的开头。
- 将 elementData 引用指向这个新创建的数组。旧数组如果没有其他引用，将在后续被垃圾回收器回收。

扩容因子：为什么是 1.5 倍？

选择 1.5 倍（而不是 2 倍或其他因子）是一个工程上的权衡：

增长太慢（如 1.2 倍）： 会导致扩容操作更频繁，虽然单次复制的元素相对较少，但总体 System.arraycopy 的调用次数增多，时间开销增大。
增长太快（如 2 倍）： 可以减少扩容次数，但可能导致容量长期远大于实际 size，造成更大的内存空间浪费。

1.5 倍被认为是在扩容频率（时间成本）和空间利用率之间的一个比较好的折中点。

扩容的成本

时间成本： 主要来自于 Arrays.copyOf 中的 System.arraycopy() 操作，其时间复杂度为 O(n)，其中 n 是当前 ArrayList 中的元素数量 (size)。这意味着每次扩容都需要复制所有现有元素。
空间成本： 需要额外分配一个更大的新数组，旧数组在被 GC 回收前会暂时占用内存。

4. 手动缩容（Contraction）：`trimToSize()`

ArrayList 会自动缩容吗？

答案是：不会。 当你调用 remove() 或 clear() 方法从 ArrayList 中删除元素时，size 会减小，并且被删除位置的引用会被置为 null（帮助 GC），但底层 elementData 数组的 capacity 保持不变。

原因： 自动缩容同样需要创建新数组和复制元素（System.arraycopy），如果频繁在添加和删除之间切换，可能会导致代价高昂的“抖动”（连续的扩容和缩容）。因此，Java 设计者决定不提供自动缩容功能。

源码解析：`trimToSize()` 方法

如果你确实希望释放 ArrayList 中未使用的容量（即让 capacity 等于 size），可以手动调用 trimToSize() 方法：

// java.util.ArrayList
public void trimToSize() {modCount++; // 修改计数器增加// 只有当实际元素数量小于数组容量时才需要缩容if (size < elementData.length) {// 如果size为0，则直接用空数组常量；否则，创建刚好够大的新数组并复制元素elementData = (size == 0)? EMPTY_ELEMENTDATA // 通常是一个 static final Object[0]: Arrays.copyOf(elementData, size);}
}

逻辑很简单：

检查 size 是否小于当前的 capacity (elementData.length)。
如果是，则使用 Arrays.copyOf(elementData, size) 创建一个长度刚好等于 size 的新数组，并将旧数组中的 size 个元素复制过去。
将 elementData 指向这个紧凑的新数组。

使用场景与注意事项

使用场景：
- 当 ArrayList 经历了大量的删除操作后，size 远小于 capacity。
- 你预期该 ArrayList 在未来很长一段时间内不会再有显著增长。
- 应用程序对内存占用非常敏感，需要及时回收不再使用的内存空间。
注意事项：
- trimToSize() 本身也是一个 O(n) 的操作（因为 Arrays.copyOf），它需要时间和计算资源。
- 不要频繁调用！ 如果在缩容后马上又开始大量添加元素，会导致立刻再次触发扩容，得不偿失。仅在确实需要且后续增长可能性小时使用。

5. 性能考量与最佳实践

预设初始容量的重要性

ArrayList 提供了带初始容量的构造函数：ArrayList(int initialCapacity)。

ArrayList<String> list = new ArrayList<>(100); // 创建一个初始容量为100的列表

好处： 如果你在创建 ArrayList 时能预估到它大致会存储多少元素，强烈建议使用此构造函数指定一个合适的初始容量。

避免或减少扩容： 如果初始容量足够大（或接近最终大小），可以显著减少甚至完全避免代价高昂的扩容操作（数组复制）。
提升添加性能： 特别是在需要一次性添加大量元素（如从数据库查询结果、文件读取）的场景下，性能提升非常明显。

经验法则： 如果不确定，可以稍微设置大一点，但也不要过大导致浪费。如果完全无法预估，则使用无参构造函数（默认初始容量在 JDK 8 中是 10，早期版本可能是 0 但第一次 add 时会变为 10）。

理解均摊时间复杂度

虽然单次扩容的时间复杂度是 O(n)，但 ArrayList 的 add(E e) 操作的均摊时间复杂度（Amortized Time Complexity） 仍然是 O(1)。

简单理解： 考虑连续添加 n 个元素。假设从空列表开始，每次扩容容量翻倍（简化模型）。扩容发生在第 1, 2, 4, 8, …, 2^k 次添加时。总的复制成本大约是 1 + 2 + 4 + … + 2^k ≈ 2^(k+1) ≈ 2n。将这个总成本分摊到 n 次添加操作上，平均每次添加的成本是 O(2n / n) = O(2) = O(1)。

这意味着，尽管偶尔会有一次“昂贵”的扩容，但长期来看，ArrayList 的添加操作效率非常高。预设初始容量可以让你避免那些“昂贵的”操作。

谨慎使用 `trimToSize()`

再次强调，trimToSize() 是一个有成本的操作，且可能与后续的添加操作冲突。仅在明确需要回收内存且列表大小趋于稳定时使用。

6. 总结

ArrayList 使用动态数组实现，通过扩容机制来支持动态添加元素。
扩容通常在 add()、addAll() 等操作导致容量不足时触发。
核心扩容逻辑在 grow() 方法中，策略是增长为原容量的 1.5 倍 (oldCapacity + (oldCapacity >> 1))。
扩容的主要成本在于 Arrays.copyOf()，需要创建新数组并复制所有现有元素 (O(n) 时间复杂度)。
ArrayList 不会自动缩容。删除元素只减少 size，不改变 capacity。
可以通过手动调用 trimToSize() 来让 capacity 等于 size，以回收内存，但此操作也有 O(n) 成本，需谨慎使用。
最佳实践： 尽可能使用 ArrayList(int initialCapacity) 构造函数预设初始容量，以减少或避免扩容，提高性能。
add 操作的均摊时间复杂度为 O(1)。

理解 ArrayList 的扩缩容机制，特别是扩容的触发条件、增长策略和成本，以及如何通过预设容量来优化，对于编写高性能、内存友好的 Java 应用至关重要。希望本文能帮助你更深入地掌握 ArrayList 的使用！