两个迭代器的故事：Java 中的竞争性修改策略

该说明的作者是来自克拉科夫（波兰）的软件开发人员 Grzegorz Mirek。大约 6 年前，他还在读大学时就开始使用 Java 进行开发，从那时起，他就一直在不知疲倦地磨练自己在该领域的技能。他对 JVM 性能和优化特别感兴趣，这是他在博客上主要写的内容。 一些最流行的 Java 面试问题包括： 快速失败迭代器和故障安全迭代器之间有什么区别？ 对此最简单的答案是： 如果集合在迭代期间发生更改，快速失败迭代器将引发 ConcurrentModificationException，但故障安全迭代器不会。 虽然这听起来很有意义，但仍不清楚面试官所说的“故障安全”是什么意思？Java 语言规范没有定义与迭代器相关的术语。然而，有四种竞争性修改策略。

竞争性改装

首先，让我们定义什么是竞争（或并行）修改。假设我们有一个集合，当迭代器处于活动状态时，会发生一些并非来自该迭代器的更改。在这种情况下，我们得到了竞争性的修改。让我给你一个简单的例子：假设我们有几个线程。第一个线程进行迭代，第二个线程从同一集合中插入或删除元素。然而，在单线程环境中运行时， 我们可能会得到ConcurrentModificationException ：

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

快速失败

上面的代码片段是快速失败迭代器的示例。正如您所看到的，当尝试从迭代器检索第二个元素时，抛出了ConcurrentModificationException。迭代器如何知道集合自创建以来已被修改？例如，集合可能有一个日期/时间戳，例如lastModified。创建迭代器时，应该复制该字段并将其存储在迭代器对象中。然后，每次调用next()方法时，您只需将集合中的LastModified值与迭代器中的副本进行比较即可。例如，在ArrayList类的实现中使用了非常相似的方法。它有一个实例变量modCount存储列表被修改的次数：

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

需要注意的是，快速失败迭代器在最佳组合的基础上运行，这意味着不能保证在并发修改时会抛出ConcurrentModificationException 。因此您不应该依赖它们 - 相反，它们应该用于检测错误。大多数非并发集合提供快速失败迭代器。

弱一致性

java.util.concurrent包中的大多数并发集合（例如ConcurrentHashMap和大多数Queue）都提供弱一致迭代器。该术语的含义在文档中有很好的解释：

• 它们可以与其他操作同时处理
• 他们从不抛出ConcurrentModificationException
• 它们保证在迭代器创建时遍历现有元素一次，并且可以（但不要求）反映后续修改。

快照

通过这种策略，迭代器与集合创建时的状态相关联——这是集合的快照。对原始集合所做的任何更改都会导致创建基础数据结构的新版本。这使我们的快照保持不变，因此它不会反映创建迭代器后发生的集合更改。这是古老的写时复制 (COW) 技术。它完全解决了并发修改的问题，因此这种方法不会产生ConcurrentModificationException 。此外，迭代器不支持更改元素的操作。写时复制集合的使用成本往往太高，但如果更改发生的频率远低于迭代器遍历，则使用它们是有意义的。示例包括CopyOnWriteArrayList和CopyOnWriteArraySet类。

未定义的行为

您可能会在旧集合类型（例如Vector和Hashtable ）中遇到未定义的行为。两者都有标准的快速失败迭代器，但除此之外，它们还允许使用Enumeration接口的实现，并且它们不知道在并发修改的情况下如何表现。你可能会遇到一些元素被重复或缺失，甚至一些奇怪的异常。最好不要和他们一起玩！