# 问题

ArrayList 是如何扩容的?扩容时有哪些性能影响?

# 标准答案

ArrayList 采用 动态数组 作为底层存储结构,其扩容机制遵循 1.5 倍扩容策略。当 add() 方法插入元素超过当前容量时,会触发扩容,即创建一个 更大的数组,并将旧数组的数据拷贝到新数组中。扩容的主要性能影响包括 内存分配开销、数据拷贝成本和 GC 压力。因此,在大量数据插入场景下,推荐 提前指定容量 或使用 ensureCapacity() 避免频繁扩容。

# 答案解析

# 1. 扩容机制

ArrayList 的元素数量超过当前数组 elementData 的容量时,会触发扩容:

  1. 计算新容量:扩容 1.5 倍,即 newCapacity = oldCapacity + (oldCapacity >> 1)
  2. 分配新数组:创建一个新的 Object[] 数组,大小为 newCapacity
  3. 数据迁移:使用 System.arraycopy() 将旧数组的元素复制到新数组。
  4. 丢弃旧数组:新数组成为 ArrayListelementData,由 GC 回收旧数组。

# 2. ArrayList 的底层结构

ArrayList 底层使用 动态数组 Object[] elementData 存储元素,其默认初始容量为 10(JDK 1.7+),当元素数量超过当前容量时,就会触发 扩容

# 3. 扩容触发条件

扩容通常发生在 add(E e) 方法插入元素时,如果数组已满,就会调用 grow(int minCapacity) 进行扩容:

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保容量足够
    elementData[size++] = e;
    return true;
}
1
2
3
4
5

其中 ensureCapacityInternal() 负责检查是否需要扩容:

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
1
2
3
4
5
6
7
8
9
10
11

minCapacity > elementData.length 时,触发 grow() 方法进行扩容。

# 4. 扩容源码剖析(JDK 1.8)

(1)扩容策略:1.5 倍增长

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍扩容
    if (newCapacity - minCapacity < 0) 
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) 
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
1
2
3
4
5
6
7
8
9

源码解析ArrayList.add(E e) 方法中,当数组满时会调用 grow() 进行扩容:

  • oldCapacity >> 1 计算 原容量的 1/2,相当于 newCapacity = oldCapacity * 1.5
  • Arrays.copyOf(elementData, newCapacity) 使用 System.arraycopy() 拷贝旧数组数据到新数组
  • 如果 newCapacity 超过 Integer.MAX_VALUE - 8,调用 hugeCapacity() 处理特殊情况,防止 OOM(OutOfMemoryError)

# 5. 扩容性能影响

(1)内存分配开销

  • ArrayList 依赖 连续的内存块,扩容时需要在堆上重新分配更大的数组,可能触发 内存碎片整理,影响 GC。
  • 若扩容后的数组找不到足够大的连续空间,可能导致 Full GC 或 OOM(OutOfMemoryError)

(2)数据拷贝成本

  • System.arraycopy() 需要将旧数组数据逐个复制到新数组,时间复杂度为 O(n)
  • 如果 ArrayList 扩容过于频繁,会造成大量的 数据搬移,影响性能。

(3)GC 压力

  • 旧数组会变成垃圾,等待 GC 回收,导致 GC 频率上升
  • 在大数据量场景下,频繁扩容可能引发 Young GC 甚至 Full GC,影响应用吞吐量。

# 6. 如何优化扩容影响?

(1)指定初始容量,减少扩容次数

List<Integer> list = new ArrayList<>(1000); // 预分配 1000 容量
1
  • 适用于 大量元素提前已知 的场景,避免反复扩容和数据搬移。

(2)使用 ensureCapacity()

list.ensureCapacity(5000); // 提前扩容,减少扩容次数
1
  • 适用于 后续数据量增长较快 的情况,提前扩容提高性能。

(3)使用 LinkedList 替代 ArrayList(适用于频繁插入/删除场景)

  • LinkedList 采用 双向链表 结构,插入/删除 O(1),但查询性能低(O(n))。
  • 适用于 数据量大且随机插入/删除频繁 的场景,如 队列、LRU 缓存等

# 深入追问

  1. 为什么 ArrayList 采用 1.5 倍扩容,而不是 2 倍?

    • 1.5 倍是 时间复杂度与空间利用率的折中
    • 2 倍扩容会导致 更高的内存浪费,增加 GC 压力。
    • 1.5 倍减少了 扩容触发的频率,同时不至于造成大块内存占用过多。
  2. System.arraycopy() 是如何优化数组拷贝的?

    • System.arraycopy()JVM 内部的本地方法,采用 CPU 内存指令优化(如 memcpy),比手写 for 循环更快。
    • 堆内存连续的情况下System.arraycopy() 利用 SIMD 指令并行拷贝,减少 CPU 指令数量,提高吞吐量。
  3. 如何减少 ArrayList 的内存占用?

    • 在数据不再增长时调用 trimToSize() 收缩容量,减少浪费:
      list.trimToSize();
      
      1
    • trimToSize() 可能导致 下一次扩容重新分配数组,需权衡使用场景。

# 相关面试题

  • 为什么 ArrayList 采用 1.5 倍扩容,而不是 2 倍?
  • ArrayListLinkedList 在扩容与插入删除方面的性能对比?
  • 如何优化 ArrayList 的扩容影响,提高插入性能?
  • ArrayList 扩容的时间复杂度是多少?如何降低扩容带来的 GC 影响?