ArrayList
ArrayList 是用一个可以自动变大的数组实现的 List:内部数组里连续存放元素的引用,按下标读取很快,空间不够时换一个更大的数组。它是 Java 里最常用的列表,选型、性能和内存问题几乎都绕不开它。
分清元素个数和数组长度,再从「数组」这个底层结构出发,就能推导各种操作的成本:哪些是 O(1),什么时候要复制,为什么尾部追加平均下来仍是 O(1)。本文的实现细节以 OpenJDK 21 为准。
1. 面试核心
先记住这几条,再读正文get、set直接按下标定位数组槽位,成本是 O(1)。- OpenJDK 21 扩容时首选在旧容量基础上增加一半,同时满足本次操作需要的最小容量。卡 · size 与 capacity
- 尾部追加的摊销成本是 O(1),但触发扩容的那一次要复制全部引用,成本是 O(n)。卡 · size 与 capacity
- 在中间插入或删除,要搬移后面所有的引用,最坏成本是 O(n)。卡 · 随机访问
subList返回的是和原列表共享数据的视图,复制一份才能和原列表的后续变化隔离开。卡 · 子列表的内存保留
2. size 与 capacity
ArrayList 里有两个容易混淆的数。元素数量 size 是已经放进列表的元素个数;容量(capacity)是内部数组的长度,也就是不扩容时最多能放多少个。容量总是大于等于元素数量,多出来的是还没用的空槽。下面的代码只预留了空间,没有放入元素:
List<String> values = new ArrayList<>(100);
System.out.println(values.size()); // 0
构造参数 100 预留了 100 个引用槽,但 size 仍是 0,这时调用 get(0) 会抛出 IndexOutOfBoundsException。能访问的下标由 size 决定,和容量无关。
还要注意,数组里连续排列的是对象的引用,不是对象本身。各个元素对象分散在堆上各自的位置,引用连续不代表对象也连续。
3. 随机访问
读取第 i 个元素时,ArrayList 先检查 0 <= i < size,再直接读内部数组的第 i 个槽位:
User user = users.get(i);
数组可以用下标直接算出槽位的位置,不用从头找,所以 get 和 set 都是 O(1)。顺序遍历时,程序连续读取相邻的引用,这对 CPU 很友好:CPU 缓存会保存最近访问过的数据,预取机制还会提前把接下来要用的数据加载进来。链表则要顺着节点一个个跳,节点分散在堆上,缓存很难帮上忙。
复杂度只描述成本随数据量增长的趋势。同样是 O(n),连续复制一个数组和逐个访问链表节点,实际耗时可以差很多。所以比较性能时,要在相同的数据规模和访问方式下测量。
4. 尾部追加与扩容
内部数组还有空位时,尾部 add 只是把引用写进 elementData[size],再把 size 加一(elementData 是内部数组的字段名):
users.add(user);
数组的长度创建后就不能改。容量不够时,ArrayList 只能分配一个更大的新数组,再把引用复制过去。OpenJDK 21 的步骤是:
- 算出这次操作至少需要多大容量(最小所需容量)。
- 新容量首选旧容量加上它的一半,也就是大约 1.5 倍;如果还不够最小所需容量,就直接用最小所需容量。比如
addAll一次加入很多元素时,就可能出现后一种情况。 - 申请新的引用数组。
- 把现有的元素引用复制过去。
- 让
elementData指向新数组,旧数组等待 GC 回收。
1.5 倍这个比例是 OpenJDK 的实现细节,API 文档只保证尾部追加的摊销成本是常数时间。
4.1 摊销复杂度
扩容要复制 O(n) 个引用,为什么还说尾部追加是 O(1)?这要用摊销复杂度来解释:把一连串操作的总成本平均分到每次操作上。
连续追加时,绝大多数 add 只写一个槽位,只有少数几次触发扩容。关键在于容量按比例增长:假设每次扩容都翻倍(1.5 倍的道理一样),追加到 n 个元素时,历次扩容复制的数量是 …、n/4、n/2、n,加起来不超过 2n。总复制量和追加次数成正比,平均到每次追加就是常数。
但平均不等于每次。触发扩容的那一次仍然要复制全部引用,如果一个很大的列表恰好在处理请求时扩容,这次请求就会明显变慢。延迟敏感的代码可以提前预留容量。
5. 初始容量
知道大概会放多少元素时,可以在创建时预留容量:
List<OrderLine> lines = new ArrayList<>(expectedLineCount);
预留容量能减少扩容的三类开销:分配新数组的次数,复制已有引用的次数,以及新旧数组同时存在时的内存峰值(扩容时旧数组要等垃圾回收器 GC 回收后才释放)。
预留多少要参考实际的元素数量。预留过大同样有代价:如果系统里有大量小列表,每个都预留一个大数组,空槽会长期占着内存,浪费可能超过省下的扩容开销。
对已经存在的列表,要一次追加大量元素前可以先调用 ensureCapacity。反过来,元素大量减少后,trimToSize 能把数组缩到和当前元素数量一样大。缩容同样要分配新数组并复制,所以只适合长期保留、大小已经稳定的列表,频繁调用反而增加开销。
6. 中间插入与删除
数组里的元素必须连续存放,不能留空。所以在某个下标插入元素时,这个位置之后的引用都要整体右移一格:
users.add(0, user);
add(0, user) 要把全部 n 个引用右移,是最坏情况。删除正好相反,后面的引用左移一格,原来最后一个位置置为 null。置为 null 是为了不让数组继续引用这个对象;等对象的其他引用也都消失后,GC 才能回收它。
把几种操作放在一起比较:
- 尾部追加直接用空槽,摊销成本 O(1)。
- 中间插入和删除要搬移后面的引用,最坏 O(n),越靠前越慢。
- 按值删除(
remove(Object))要先从头线性查找目标,再搬移,也是 O(n)。
批量删除时,按下标从后往前删可以避免下标错位,但每删一个都要搬移一次,总成本可能到 O(n²)。OpenJDK 21 的 removeIf 会一次把要保留的元素压缩到数组前部,避免反复搬移。也可以先筛选出要保留的元素,再组成一个新列表。
后续阅读:subList 视图
7. subList 视图
subList 返回原列表一段范围的视图:它不复制元素,读写都直接作用在原列表的数据上。下面的 page 对应原列表下标从 from(含)到 to(不含)的元素:
List<User> page = users.subList(from, to);
通过 page 替换、增加或删除元素,原列表会跟着变。反过来就有问题:如果绕过视图直接对原列表增删元素(结构修改),视图并不知道,之后再使用视图的行为是未定义的。OpenJDK 会用修改计数尽力检测这种情况,抛出 ConcurrentModificationException,但不保证一定能检测到。
需要一个独立的列表时,显式复制一份:
List<User> page = new ArrayList<>(users.subList(from, to));
视图还会让整个原列表无法被回收,内存上的影响见 子列表的内存保留。
8. 线程安全
ArrayList 不是线程安全的,多个线程同时修改它,结果没有保证。即使每个方法单独看起来没问题,组合起来的操作也不是原子的,比如「不存在就添加」:
if (!users.contains(user)) {
users.add(user);
}
两个线程可能都先通过了 contains 检查,再各自 add,同一个元素就被加了两次。怎么避免,要看列表是怎样被共享的:
- 列表只由一个线程访问时,使用线程封闭,让其他线程通过任务或消息提交修改。
- 多个线程共享可变列表时,用同一把锁保护完整的检查与追加。
- 读者只需要固定结果时,发布安全构造的不可变快照。
- 需要特定并发操作时,选择提供相应原子方法的并发容器。
Collections.synchronizedList 只保证单个方法调用是同步的。遍历和上面这种复合操作,仍然要手动在包装后的列表对象上加锁。具体规则见 集合迭代器。
检查能否解释
解释随机访问、追加、扩容和中间插入的成本,区分单次操作与摊销复杂度。
ArrayList 怎样扩容,指定初始容量有什么作用? 查看题目与参考回答 →9. 子列表的内存保留
只保留一个很小的 subList,也会让整个原列表继续占用内存。原因在于视图的实现:OpenJDK 21 的 SubList 对象里保存了根列表 root、父视图 parent 和偏移量。只要视图还被引用,根列表就能通过它访问到,GC 不会回收根列表,它的底层数组和数组引用的所有元素也都会继续存活。比如从一百万条记录里取前 10 条的视图长期缓存起来,那一百万条记录都释放不掉。
需要长期保存一页结果时,复制这一页:
List<String> page = new ArrayList<>(all.subList(0, 10));
新列表只保存这 10 个元素的引用,和原列表没有关系,原列表的其他元素可以被回收。但这是浅复制:两个列表引用的是同一批元素对象,元素如果可变,通过一个列表改了元素的字段,另一个也能看到。
10. 常见问题
10.1 ArrayList 的默认容量是 10 吗?
不完全是。OpenJDK 21 的无参构造器一开始用的是一个共享的空数组,不占额外空间,等到第一次 add 一个元素时才分配容量 10 的数组。显式写 new ArrayList<>(0) 时,第一次 add 分配的容量是 1。这些数值都是实现策略,业务代码判断有没有元素要看 size,不要依赖容量。
10.2 Arrays.asList 返回的是 ArrayList 吗?
不是 java.util.ArrayList。Arrays.asList 返回的是一个由原数组支撑的固定大小列表:set 替换元素会写回原数组,add、remove 这类改变长度的操作会抛出 UnsupportedOperationException。示例见 集合迭代器。
10.3 List<Integer> 调用 remove(1),删的是哪个?
删的是下标 1 的元素。remove 有 remove(int index) 和 remove(Object o) 两个重载,编译器选择重载时优先匹配不需要装箱的版本,所以 remove(1) 选中了按下标删除。要删除值为 1 的元素,写成 remove(Integer.valueOf(1))。
10.4 ArrayList 比数组慢多少?
要看具体代码。ArrayList 多了容量管理,存基本类型时还要装箱(把数值包装成 Integer 这样的对象);但数组访问本身也有边界检查,即时编译器(JIT)也能优化掉一部分开销,实际差距需要测量。一般来说,长度固定、基本类型的密集计算适合用数组,需要动态增删的业务数据适合用 List。
11. 面试题卡片
12. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明