跳到主要内容
约 11 分钟5 张卡

集合迭代器

迭代器(Iterator)是记住遍历位置、一次取出一个元素的对象,所有集合都通过它提供统一的遍历方式。遍历时最容易出错的是「一边遍历一边修改」:直接改集合会让迭代器记住的位置失效,于是 ArrayList 这类集合用 fail-fast 机制尽早抛出异常。和它相关的另一组问题是「不让别人改」:只读视图、不可变副本和固定大小列表分别挡住了哪些修改,又有哪些挡不住。下文以 Java 21 为准。

1. 面试核心​

先记住这几条,再读正文
  • ArrayList 等集合用 modCount 记录结构修改,迭代器发现它和自己保存的预期计数不一致时,抛出 ConcurrentModificationException。卡 · 结构修改与 fail-fast
  • fail-fast 只是尽力检测遍历与修改的冲突,单线程也会触发;它不提供线程安全,共享访问仍要靠同步。卡 · 结构修改与 fail-fast
  • 对支持删除的迭代器,每次 next 之后最多调用一次 remove,删除的是刚返回的那个元素。卡 · 迭代器的删除状态
  • Collections.unmodifiableList 返回跟随原列表变化的只读视图,List.copyOf 返回固定了元素引用和顺序的不可修改副本。卡 · 不可修改视图与不可变副本
  • 不可修改列表仍然共享元素对象,元素的字段能不能改,要由元素类型自己控制。

2. Iterable 与 Iterator​

Iterable 表示「这个对象能提供迭代器」,Iterator 负责执行一次具体的遍历。对集合使用增强 for 时,编译器会调用 Iterable.iterator() 拿到迭代器。下面两种写法做的是同一件事(二选一,放在一起只是为了对照):

// 增强 for
for (User user : users) {
consume(user);
}

// 对应的迭代器写法
Iterator<User> iterator = users.iterator();
while (iterator.hasNext()) {
User user = iterator.next();
consume(user);
}

两段代码都依次取出元素交给 consume。遍历位置保存在迭代器里,而不是靠下标,所以没有索引的集合也能这样遍历:数组列表、链表、哈希表和树,用的都是同一套 hasNext、next。

3. 结构修改与 fail-fast​

迭代器要根据集合当前的结构找到下一个元素。如果绕过迭代器直接增删元素,它记住的位置就不再可靠。下面的代码在遍历中直接调用了列表的 remove:

for (User user : users) {
if (user.disabled()) {
users.remove(user);
}
}

ArrayList 防范这种错误的办法是计数。它用 modCount 记录结构修改的次数,创建迭代器时把当时的值存为 expectedModCount。之后每次 next、remove 都比较这两个数,不一致就抛出 ConcurrentModificationException,简称 CME。这种一发现冲突就立即失败的行为叫 fail-fast。上面的循环删除一个元素后,modCount 加一,下一次 next 就会抛出 CME。

结构修改是指改变元素数量,或者会影响遍历结构的操作。对 ArrayList 来说,增删元素和显式调整数组容量都算;set 只是替换某个位置的元素,不改变 modCount。其他集合哪些操作算结构修改,要看各自的文档。

3.1 fail-fast 的检测范围​

fail-fast 是用来暴露错误的,看到 CME 应该去改代码,而不是捕获它继续跑。它只是尽力检查,不保证每次冲突都能发现。比如上面的循环如果删掉的恰好是倒数第二个元素,删除后 hasNext 判断已经到头,循环直接结束,既不抛异常,也漏掉了最后一个元素。

在没有同步的多线程访问中,它更不可靠。modCount 的比较只是比一个数,不会让其他线程的修改自动对当前线程可见,也不会把多步操作变成原子操作,所以没有抛异常并不能证明访问是安全的。普通集合要么只在一个线程里使用,要么用锁或并发容器来保护共享访问。

4. 遍历期间的元素删除​

遍历中要删除当前元素,应该让迭代器来删。迭代器删除后会同时调整自己的遍历位置和预期计数,下一次 next 就不会出错。下面是迭代器删除与条件删除两种做法(二选一):

// 由迭代器删除当前元素
Iterator<User> iterator = users.iterator();

while (iterator.hasNext()) {
User user = iterator.next();
if (user.disabled()) {
iterator.remove();
}
}

// 直接按条件删除
users.removeIf(User::disabled);
  • iterator.remove() 删除刚取出的禁用用户,迭代器接着访问后面的元素。
  • removeIf 一次删掉所有满足条件的元素,只是按条件删除时写起来最简单。

如果还需要双向遍历、替换刚返回的元素,或者在当前位置插入,可以用 ListIterator,它是 List 专用的迭代器,适合做局部编辑。

4.1 迭代器的删除状态​

remove 不带参数,它删的是最近一次 next 返回的元素,所以能不能调用取决于前面有没有调用过 next。对支持删除的迭代器,删除状态有三种情况:

  • 第一次调用 next 之前,没有可删的元素,调用 remove 抛出 IllegalStateException。
  • 调用 next 之后,可以调用一次 remove 删除刚返回的元素。
  • 同一次 next 之后连续调用两次 remove,第二次抛出 IllegalStateException。
var values = new ArrayList<>(List.of("A", "B"));
var it = values.iterator();
it.next();
it.remove();
System.out.println(values); // [B]

it.next() 返回 A,it.remove() 把它删掉,最后列表是 [B]。删除后,it 会更新自己的预期计数,可以继续遍历;但同一个列表上的其他迭代器还拿着旧计数,再用就会抛 CME,需要重新创建。只读集合的迭代器则直接拒绝 remove,抛出 UnsupportedOperationException。

5. 同步包装的遍历​

Collections.synchronizedList 只给列表的每一次方法调用单独加锁。而一次遍历由很多次 hasNext、next 组成,其他线程可以在这些调用之间插进来修改列表。所以要在包装返回的那个 List 对象上,把整个遍历同步起来:

List<String> values = Collections.synchronizedList(new ArrayList<>());
synchronized (values) {
for (String value : values) {
consume(value);
}
}

遍历期间一直持有 values 的锁,其他线程通过包装方法执行的更新要等遍历结束才能进行。这要求所有对底层列表的访问都经过包装对象;「先检查、再插入」这类复合操作也要放在同一把锁里。如果有代码锁的是原始的 ArrayList,两边用的不是同一把锁,就起不到互斥的作用。

6. 并发集合的迭代语义​

并发集合允许遍历和更新同时进行,不会抛 CME,但不同实现能看到的内容不同。ConcurrentHashMap 的迭代器是弱一致的,遍历过程中可能看到一部分更新;CopyOnWriteArrayList 的迭代器则固定在创建时的数组快照上,之后的修改都看不到。

这两种保证范围不同,Java API 里也没有一个统一的「fail-safe」接口来概括它们。具体差别见迭代一致性。

7. 不可修改视图与不可变副本​

给调用方返回一个只读列表之前,先想清楚:这个结果要不要跟着原列表变化。Collections.unmodifiableList 返回的是共享原列表的只读视图,List.copyOf 返回的是内容固定的副本:

// 只读视图
List<String> source = new ArrayList<>(List.of("A", "B"));
List<String> view = Collections.unmodifiableList(source);

source.add("C");
System.out.println(view); // [A, B, C]

// 固定列表内容的副本
List<String> snapshot = List.copyOf(source);
source.add("D");

System.out.println(snapshot); // [A, B, C]
  • view 和 source 共享数据,调用方不能通过 view 修改,但 source 加入 C 后,view 也能看到。
  • snapshot 在创建时复制了当时的元素引用,source 后来加入 D,snapshot 还是 [A, B, C]。

如果传给 List.copyOf 的本来就是一个合适的不可修改列表,它可能直接返回这个实例,不再复制。所以调用方可以依赖「内容不会变」,但不要假设每次都得到一个新对象。

Java 9 起,List.of、Set.of、Map.of 可以直接创建不可修改集合。使用这些集合工厂方法时要注意:

  • 三者都拒绝 null 元素、null 键或 null 值。
  • Set.of 遇到重复元素会抛异常。
  • Map.of 遇到重复键会抛异常。

List.copyOf 从 Java 10 开始提供,适合根据已有集合生成一个稳定的列表结果。

8. 浅层不可变​

只读列表限制的是列表本身:不能增删元素,也不能把某个位置换成别的对象。但列表里的对象仍然是共享的,这些对象的字段能不能改,由元素类型自己决定。这种只管到容器这一层的不可变叫浅层不可变:

List<User> snapshot = List.copyOf(users);
snapshot.get(0).rename("changed");

如果 User 的 rename 会修改自己的字段,这段代码仍然能改掉用户的名字,而且 users 里的同一个 User 也跟着变了。不可修改列表能防止调用方意外增删列表,也让跨线程共享更容易管理,但元素的状态需要另外保护。

要让整个结果都不变,可以让元素本身不可变,或者在返回时把需要隔离的可变对象也复制一份。这种防止外部修改影响内部状态的做法叫防御性复制,实现见不可变对象。

9. Arrays.asList 的固定大小列表​

Arrays.asList 返回的是一个直接建在原数组上的固定大小列表:长度不能变,但元素可以替换,而且替换会写回原数组。

String[] array = {"A", "B"};
List<String> fixed = Arrays.asList(array);

fixed.set(0, "X"); // 可以
// fixed.add("C"); // UnsupportedOperationException
System.out.println(array[0]); // X

fixed.set(0, "X") 改的就是原数组的第一个槽位,所以 array[0] 也变成了 X。增删会改变长度,因此抛出 UnsupportedOperationException。作为对照,List.of 连 set 都不允许,而且它不依赖原数组,之后替换数组里的元素也不会影响它。

9.1 基本类型数组的列表转换​

把基本类型数组传给 Arrays.asList,结果和直觉不一样。这个方法的参数是泛型可变参数 T...,而泛型类型参数只能是引用类型,T 不可能是 int。int[] 本身是一个引用类型的对象,于是 T 被推断为 int[],整个数组成了列表里的唯一一个元素:

int[] numbers = {1, 2};
List<int[]> one = Arrays.asList(numbers);
List<Integer> boxed = Arrays.stream(numbers).boxed().toList();
System.out.println(one.size()); // 1
System.out.println(boxed.size()); // 2

one 的大小是 1,里面保存的是整个 int[]。boxed() 把每个 int 转成 Integer,也就是逐项装箱,所以 boxed 的大小是 2。Java 16 起,Stream.toList() 返回的是不可修改列表;需要可修改的结果时,再传给 ArrayList 的构造器。

10. 常见问题​

10.1 单线程的修改冲突​

单线程也会抛 CME。只要绕过迭代器修改了集合,计数就对不上,和有几个线程无关。CME 检测的是遍历和修改在时间上交错,异常名里的 concurrent 并不表示一定有多个线程。

10.2 索引循环的删除边界​

10.3 只读视图与 API 返回值​

10.4 List.copyOf 的空值约束​

11. 面试题卡片​

12. 参考资料​

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