# 问题
1. ArrayList 的底层数据结构是什么?默认容量是多少?
# 标准答案
ArrayList
底层基于 动态数组(dynamic array) 实现,使用 Object[]
数组存储元素。默认情况下,JDK 1.8 及以后版本的 ArrayList
初始容量为 0,只有在第一次 add()
操作时才会扩容到 10(即 DEFAULT_CAPACITY = 10
)。
# 答案解析
# 1. 底层数据结构
ArrayList
的底层数据结构是 动态数组,它与 LinkedList
的链表结构不同,依赖 连续的内存空间 存储数据。
首次创建
ArrayList
List<Integer> list = new ArrayList<>();
1ArrayList
初始时elementData
数组为 空数组,不会立即分配内存。第一次
add()
时触发初始化list.add(1);
1ArrayList
扩容到DEFAULT_CAPACITY = 10
,实际存储数组elementData
长度变为 10。
# 2. 默认容量(JDK 1.8+)
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
2
- JDK 1.7 及以前:默认初始容量
10
,直接分配Object[10]
。 - JDK 1.8 及以后:初始时
elementData
为空数组,只有在第一次add()
时才扩容至10
,减少不必要的内存占用。
# 3. 扩容机制
当 ArrayList
需要存储的元素超出当前数组容量时,会触发 扩容,扩容规则如下:
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍扩容
1
例如:
- 容量
10
扩容到15
- 容量
15
扩容到22
- 容量
22
扩容到33
扩容过程:
- 创建一个 更大的数组
- 复制原数组的数据到新数组
- 丢弃旧数组,使用新数组
扩容涉及 数组拷贝(System.arraycopy()
),可能影响性能,因此建议在大量插入数据时 预分配足够的容量 以减少扩容次数:
List<Integer> list = new ArrayList<>(1000); // 预分配 1000 容量,避免频繁扩容
1
# 4. ArrayList 与 LinkedList 的对比
特性 | ArrayList | LinkedList |
---|---|---|
底层结构 | 动态数组 (Object[] ) | 双向链表 (Node ) |
访问速度 | O(1) 随机访问快 | O(n) 随机访问慢 |
插入删除 | O(n) 移动数据,性能低 | O(1) 修改指针,性能高 |
内存占用 | 较低,仅存储数据 | 较高,额外存储指针 |
适用场景 | 读多写少(如缓存) | 写多读少(如队列) |
# 深入追问
为什么 JDK 1.8 之后
ArrayList
初始容量变为 0,而不是直接 10?- 这样可以减少内存占用,只有在
add()
时才分配数组,适用于未必需要添加数据的情况。
- 这样可以减少内存占用,只有在
扩容 1.5 倍的依据是什么?为什么不是 2 倍?
- 1.5 倍是时间复杂度与空间利用率的折中。
- 2 倍扩容会增加内存占用,而 1.5 倍减少了碎片化的浪费,避免 GC 压力。
如何减少
ArrayList
的扩容影响?- 预分配容量
new ArrayList<>(expectedSize)
。 - 使用
ensureCapacity(int minCapacity)
主动扩容。
- 预分配容量
# 相关面试题
ArrayList
和LinkedList
的区别是什么?- 为什么
ArrayList
的扩容不是按固定大小增加? - 如何优化
ArrayList
的性能,减少扩容开销?