# 问题
ArrayList 是如何扩容的?扩容时有哪些性能影响?
# 标准答案
ArrayList
采用 动态数组 作为底层存储结构,其扩容机制遵循 1.5 倍扩容策略。当 add()
方法插入元素超过当前容量时,会触发扩容,即创建一个 更大的数组,并将旧数组的数据拷贝到新数组中。扩容的主要性能影响包括 内存分配开销、数据拷贝成本和 GC 压力。因此,在大量数据插入场景下,推荐 提前指定容量 或使用 ensureCapacity()
避免频繁扩容。
# 答案解析
# 1. 扩容机制
当 ArrayList
的元素数量超过当前数组 elementData
的容量时,会触发扩容:
- 计算新容量:扩容 1.5 倍,即
newCapacity = oldCapacity + (oldCapacity >> 1)
。 - 分配新数组:创建一个新的
Object[]
数组,大小为newCapacity
。 - 数据迁移:使用
System.arraycopy()
将旧数组的元素复制到新数组。 - 丢弃旧数组:新数组成为
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;
}
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);
}
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);
}
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 容量
- 适用于 大量元素提前已知 的场景,避免反复扩容和数据搬移。
(2)使用 ensureCapacity()
list.ensureCapacity(5000); // 提前扩容,减少扩容次数
- 适用于 后续数据量增长较快 的情况,提前扩容提高性能。
(3)使用 LinkedList
替代 ArrayList
(适用于频繁插入/删除场景)
LinkedList
采用 双向链表 结构,插入/删除 O(1),但查询性能低(O(n))。- 适用于 数据量大且随机插入/删除频繁 的场景,如 队列、LRU 缓存等。
# 深入追问
为什么
ArrayList
采用 1.5 倍扩容,而不是 2 倍?- 1.5 倍是 时间复杂度与空间利用率的折中。
- 2 倍扩容会导致 更高的内存浪费,增加 GC 压力。
- 1.5 倍减少了 扩容触发的频率,同时不至于造成大块内存占用过多。
System.arraycopy()
是如何优化数组拷贝的?System.arraycopy()
是 JVM 内部的本地方法,采用 CPU 内存指令优化(如memcpy
),比手写for
循环更快。- 在 堆内存连续的情况下,
System.arraycopy()
利用 SIMD 指令并行拷贝,减少 CPU 指令数量,提高吞吐量。
如何减少
ArrayList
的内存占用?- 在数据不再增长时调用
trimToSize()
收缩容量,减少浪费:list.trimToSize();
1 - 但
trimToSize()
可能导致 下一次扩容重新分配数组,需权衡使用场景。
- 在数据不再增长时调用
# 相关面试题
- 为什么
ArrayList
采用 1.5 倍扩容,而不是 2 倍? ArrayList
和LinkedList
在扩容与插入删除方面的性能对比?- 如何优化
ArrayList
的扩容影响,提高插入性能? ArrayList
扩容的时间复杂度是多少?如何降低扩容带来的 GC 影响?