问题

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

标准答案

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

答案解析

1. 扩容机制

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

1. 计算新容量：扩容 1.5 倍，即 newCapacity = oldCapacity + (oldCapacity >> 1)。
2. 分配新数组：创建一个新的 Object[] 数组，大小为 newCapacity。
3. 数据迁移：使用 System.arraycopy() 将旧数组的元素复制到新数组。
4. 丢弃旧数组：新数组成为 ArrayList 的 elementData，由 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;
}

其中 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);
}

当 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);
}

源码解析 在 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 容量

• 适用于 大量元素提前已知 的场景，避免反复扩容和数据搬移。

（2）使用 ensureCapacity()

list.ensureCapacity(5000); // 提前扩容，减少扩容次数

• 适用于 后续数据量增长较快 的情况，提前扩容提高性能。

（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();
     

   • 但 trimToSize() 可能导致 下一次扩容重新分配数组，需权衡使用场景。

相关面试题

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