为什么 it.next() 会抛出 java.util.ConcurrentModificationException 异常？

Question

final Multimap<Term, BooleanClause> terms = getTerms(bq);
        for (Term t : terms.keySet()) {
            Collection<BooleanClause> C = new HashSet(terms.get(t));
            if (!C.isEmpty()) {
                for (Iterator<BooleanClause> it = C.iterator(); it.hasNext();) {
                    BooleanClause c = it.next();
                    if(c.isSomething()) C.remove(c);
                }
            }
        }

虽然不是最小自给可运行示例(SSCCE)，但你能否理解这个问题的本质？

- simpatico

---

听起来你已经知道了问题所在。 - bmargulies

可能是一个愚蠢的问题 - 什么是SSCE或SSCCE？这些缩写似乎都不相关。 - CoolBeans

@CoolBeans：请查看SSCCE。 - Hovercraft Full Of Eels

@Hovercraft Full Of Eels - 难怪你白天是医生，晚上是程序员 :) - CoolBeans

如果你要接受任何答案，Swagatika 更加技术正确。 - John Vint

Answer 1

HashSet 类的 Iterator 是一种快速失败的迭代器。从 HashSet 类的文档中可以看到：

该类的 iterator 方法返回的迭代器是快速失败的：如果在创建迭代器后集合被以任何方式（除了通过迭代器自身的 remove 方法）修改，则迭代器会抛出 ConcurrentModificationException 异常。因此，在并发修改的情况下，迭代器会迅速而干净地失败，而不是冒着在未来某个不确定的时间面临任意、不确定行为的风险。

请注意，由于存在非同步的并发修改，迭代器的快速失败行为不能得到保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException 异常。因此，编写依赖于此异常的程序来确保其正确性是错误的：迭代器的快速失败行为应仅用于检测错误。

请注意最后一句话——捕获 ConcurrentModificationException 表示另一个线程正在修改集合。同一 Javadoc API 页面还指出：

If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set:

Set s = Collections.synchronizedSet(new HashSet(...));

我认为Javadoc中的参考说明了下一步应该做什么。

此外，在您的情况下，我不明白为什么您没有使用ImmutableSet，而是创建了一个HashSet对象（这可能会在中间被修改；我看不到getTerms方法的实现，但我猜测底层的keyset正在被修改）。创建一个不可变集合将允许当前线程拥有原始键集的自己的防御性副本。

请注意，尽管使用同步的Set（如Java API文档中所述）可以防止ConcurrentModificationException异常，但前提是所有线程都访问同步集合而不是直接访问支持集合（在您的情况下可能是不真实的，因为HashSet可能在一个线程中创建，而MultiMap的基础集合则由其他线程修改）。同步集合类实际上维护了一个内部互斥体供线程获取访问权限；由于您无法直接从其他线程访问互斥体（在这里这样做非常荒谬），因此您应该考虑使用键集或MultiMap本身的防御性副本使用MultiMaps类的unmodifiableMultimap方法（您需要从getTerms方法返回一个不可修改的MultiMap）。您还可以调查返回同步MultiMap的必要性，但再次强调，您需要确保任何线程都必须获取互斥体以保护基础集合免受并发修改。

请注意，我故意省略了提及使用线程安全的HashSet的原因是我不确定实际集合的并发访问是否得到保证；很可能不是这种情况。

---

编辑：ConcurrentModificationException在单线程场景下在Iterator.next上抛出

这是针对编辑后的问题中引入的语句：if(c.isSomething()) C.remove(c);

调用Collection.remove会改变问题的性质，因为即使在单线程场景下，也有可能抛出ConcurrentModificationException。

这种可能性源于方法本身的使用，以及与Collection的迭代器一起使用，在此情况下使用了变量it初始化的语句：Iterator<BooleanClause> it = C.iterator();。

迭代CollectionC的Iteratorit存储与Collection当前状态相关的状态。在这种特殊情况下（假设使用Sun/Oracle JRE），使用KeyIterator（HashMap类的内部内部类，由HashSet使用）迭代Collection。该Iterator的一个特定特征是，它通过其Iterator.remove方法跟踪对Collection（在这种情况下为HashMap）执行的结构修改次数。

当您直接在集合上调用remove，然后紧接着调用Iterator.next时，迭代器会抛出ConcurrentModificationException异常，因为Iterator.next会验证是否有任何结构修改的Collection是迭代器不知道的。在这种情况下，Collection.remove会导致一次结构性修改，由Collection跟踪，但不是由Iterator跟踪。

为了克服这个问题，您必须调用Iterator.remove而不是Collection.remove，因为这可以确保Iterator现在知道了对Collection的修改。在这种情况下，Iterator将通过remove方法跟踪发生的结构性修改。因此，您的代码应该如下所示：

final Multimap<Term, BooleanClause> terms = getTerms(bq);
        for (Term t : terms.keySet()) {
            Collection<BooleanClause> C = new HashSet(terms.get(t));
            if (!C.isEmpty()) {
                for (Iterator<BooleanClause> it = C.iterator(); it.hasNext();) {
                    BooleanClause c = it.next();
                    if(c.isSomething()) it.remove(); // <-- invoke remove on the Iterator. Removes the element returned by it.next.
                }
            }
        }

- Vineet Reynolds

---

@Hover，嘿谢谢。在我发表那个声明之前，我经历了很多战斗。 - Vineet Reynolds

@J-16 SDiZ，是的，我同意在这种特殊情况下，Collections.synchronizedSet调用是没有意义的。 - Vineet Reynolds

代码位于一个静态方法中，从@Test方法调用，我没有看到任何并发。有什么方法可以验证问题确实是并发问题吗？如果我使用Collections.UnmodifiableSet，它可以工作，直到删除语句（已添加）。 - simpatico

@simpatico，另外，我怀疑原始的“ConcurrentModificationException”与“Collection.remove”调用有很大关系这使迭代器无效。您应该在集合的迭代器上调用remove方法。编辑：我注意到您之前的评论，如果您的代码确实调用了Collection.remove，那么即使在单线程场景下，CME异常的原因也是可以理解的。 - Vineet Reynolds

@Vineet，我评论的原因是因为你的答案在技术上仍然不正确，尽管你的评论可能会验证你所说的大部分内容，但我想知道有多少人会看到你有6个赞，读了你的答案并继续前进。实际答案中根本没有提到迭代器本身，而我们知道迭代器是实际异常的驱动力，而不是多个线程。我认为你的答案会让新手感到困惑。 - John Vint

Answer 2

原因是您试图在迭代器之外修改集合。

工作原理：

当您创建迭代器时，集合会分别为集合和迭代器维护modificationNum变量。 1. 修改集合或迭代器时，集合变量将递增。 2. 修改迭代器时，迭代器变量将递增。

因此，当您通过迭代器调用it.remove()时，它会将modification-number变量的值增加1。

但是，当您直接在集合上调用collection.remove()时，它只会增加集合的modification-numbervariable的值，而不会增加迭代器的变量。

规则是：当迭代器的modification-number值与原始集合的modification-number值不匹配时，它会引发ConcurrentModificationException。

- Swagatika

---

你的规则很有道理（因为它没有涉及到线程）。你能否重写代码让它能够工作？ - simpatico

这不是我的规则，这是集合内部迭代器的工作方式。您可以使用it.remove()而不是直接从集合中删除。 - Swagatika

Answer 3

Vineet Reynolds已经详细解释了为什么集合会抛出ConcurrentModificationException（线程安全、并发性）。Swagatika已经详细解释了这种机制的实现细节（集合和迭代器如何计算修改数量）。

他们的答案很有趣，我投了赞成票。但是，在您的情况下，问题不是来自并发性（只有一个线程），而且实现细节虽然有趣，但在这里不应该考虑。

您只需要考虑HashSet javadoc的这部分内容：

此类的iterator方法返回的迭代器是快速失败的：如果在创建迭代器后任何时候以任何方式修改集合，除了通过迭代器自己的remove方法之外，迭代器都会抛出ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速而清晰地失败，而不是在未来某个不确定的时间冒任意、不确定的风险。

在你的代码中，你使用其迭代器遍历HashSet，但你使用HashSet自己的remove方法来删除元素（C.remove(c)），这导致了ConcurrentModificationException异常。相反，如javadoc中所述，你应该使用Iterator自己的remove()方法，该方法从基础集合中删除当前正在迭代的元素。

                if(c.isSomething()) C.remove(c);

使用

                if(c.isSomething()) it.remove();

如果您想使用更多功能的方法，可以创建一个谓词并在HashSet上使用Guava的Iterables.removeIf()方法：

Predicate<BooleanClause> ignoredBooleanClausePredicate = ...;
Multimap<Term, BooleanClause> terms = getTerms(bq);
for (Term term : terms.keySet()) {
    Collection<BooleanClause> booleanClauses = Sets.newHashSet(terms.get(term));
    Iterables.removeIf(booleanClauses, ignoredBooleanClausePredicate);
}

PS：请注意，在这两种情况下，这只会从临时 HashSet 中删除元素。 Multimap 不会被修改。

- Etienne Neveu