跳到主要内容
约 10 分钟3 张卡

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. 算出这次操作至少需要多大容量(最小所需容量)。
  2. 新容量首选旧容量加上它的一半,也就是大约 1.5 倍;如果还不够最小所需容量,就直接用最小所需容量。比如 addAll 一次加入很多元素时,就可能出现后一种情况。
  3. 申请新的引用数组。
  4. 把现有的元素引用复制过去。
  5. 让 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 吗?​

10.3 List<Integer> 调用 remove(1),删的是哪个?​

10.4 ArrayList 比数组慢多少?​

11. 面试题卡片​

12. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明