ForEach operation in Java collection

2022-07-13 730 words 4 minutes views

Contents

java.util.ConcurrentModificationException

当通过forEach循环遍历集合时，一般禁止 add or remove 操作集合元素。不然会报java.util.ConcurrentModificationException异常。

例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        for (Object o : list) {
            if ("3".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

输出结果如下：

源码分析

ConcurrentModificationException

在官方文档中有关于ConcurrentModificationException的javadoc，原文非常长，这边贴一部分关键的，有兴趣的可以自己去翻阅JDK源码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


/**
 * This exception may be thrown by methods that have detected concurrent
 * modification of an object when such modification is not permissible.
 
 * For example, it is not generally permissible for one thread to modify a Collection
 * while another thread is iterating over it.Some Iterator
 * implementations (including those of all the general purpose collection implementations
 * provided by the JRE) may choose to throw this exception if this behavior is
 * detected.  Iterators that do this are known as <i>fail-fast</i> iterators,
 * as they fail quickly and cleanly, rather that risking arbitrary,
 * non-deterministic behavior at an undetermined time in the future.
 
 * Note that this exception does not always indicate that an object has
 * been concurrently modified by a <i>different</i> thread.  If a single
 * thread issues a sequence of method invocations that violates the
 * contract of an object, the object may throw this exception.  For
 * example, if a thread modifies a collection directly while it is
 * iterating over the collection with a fail-fast iterator, the iterator
 * will throw this exception.
*/

这一大段话大概意思是说，这个异常可能会在检测到一个对象被做了不合法的并发修改，比如JDK自带的集合通常会内置一个fail-fast类型的迭代器，当集合检测到这类不合法的并发修改，就会抛出该异常。所谓的fail-fast（快速失败），顾名思义，就是当检测到有异常时，越快抛出异常结束越好，以免将来带来未知的隐患。另外这段话还说了，这个异常并不是像名字那样只会出现在多线程并发修改的情况下，在单线程下也会出现。

checkForComodification

控制台除了抛出这个异常，还提示了具体的异常抛出的位置，在java.util.ArrayList$Itr.next()内部的checkForComodification()方法。定位到ArrayList源码指定位置，如下图标识红框位置：

这个方法的逻辑非常简单。

这里出现了modCount和expectedModCount继续跳转到定义他们的地方。

modCount

modCount是定义在AbstractList（ArrayList的子类）里面的一个属性。这个属性的javadoc也是相当长，截取一部分如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.

* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list).  A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}.  If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;

大概意思是，这个字段的值是用来记录list被结构性操作的次数。何为结构性操作？就是对List的容量有影响的或者迭代过程中会导致错误结果的操作。而子类可以使用这个字段的值来实现fail-fast。如果要实现fail-fast，需要在所有结构性操作的方法内部做 modCount++ 操作，并且每个方法内部只能增加一次。如果不想实现fail-fast就不需要这个值的。比如ArrayList的add方法里面就有 modCount++ 操作，如下图所示：

expectedModCount

再来看看expectedModCount。expectedModCount是定义在java.util.ArrayList$Itr里面的属性，并且会将ArrayList的modCount的值作为其初始化值。

在正常情况下，ArrayList初始化后，内置的Itr也跟着初始化，并且expectedModCount和modCount是保持一致的。如果没有进行迭代操作，自然是不会出现不一致的问题，也就不会抛出ConcurrentModificationException。

那之前的程序为什么会导致这两个值不一致呢？

因为程序中使用了一个增强forEach循环，其实forEach可以看做是jdk一个语法糖，底层就是使用迭代器实现的。所以为了看清楚，我们在java.util.ArrayList$Itr的方法上都加上断点。如下图：

刚开始list添加了5个元素，size等于5。由前面得知，add操作属于结构性操作，会导致 modCount++ 。

Itr迭代器的游标cursor值会从0开始随着元素的遍历移动。hasNext()通过判断cursor != size来确定list是否还有下一个元素取出。如果返回true，则会进入 next()用来返回下一个元素。

显然我们有5个元素，可以进入next()。而在next方法中，第一行代码就是checkForComodification()用来校验expectedModCount和modCount的一致性。显然从List添加完元素到现在为止，我们没有再对list有过额外的结构性操作，自然前面3次迭代都不会抛出异常，正常返回元素。都如图所示:

并且每次执行完next()后，cursor会往后移动一位，为迭代下一个元素做准备。

这个时候轮到迭代第三个元素**“3”**了。自然if条件判断成立，会进入删除操作。

跟进remove()方法源码中，确实发现了 modCount++ 。也就是说，这个时候modCount值已经变成6了。而expectedModCount依然还是保存着初始值5。此时两者不一致了。

因为list在**“3”**之后还有**“4”**，**“5”**两个元素，因此当删除**“3”**元素之后，迭代器还会继续迭代，重复之前的流程，会先进入hasNext()，此时cursor等于3，size等于4，自然还是满足的，所以还是会继续进入next()取出下一个元素。

可以预料此时checkForComodification()校验expectedModCount和modCount已经不一致了，所以抛出了ConcurrentModificationException。

解决办法

解决方法1：

从API中可以看到List等Collection的实现并没有同步化，如果在多线程应用程序中出现同时访问，而且出现修改操作的时候都要求外部操作同步化；调用Iterator操作获得的Iterator对象在多线程修改Set的时候也自动失效，并抛出java.util.ConcurrentModificationException。这种实现机制是fail-fast，对外部的修改并不能提供任何保证。

网上查找的关于Iterator的工作机制。Iterator是工作在一个独立的线程中，并且拥有一个 mutex锁，就是说Iterator在工作的时候，是不允许被迭代的对象被改变的。Iterator被创建的时候，建立了一个内存索引表（单链表），这个索引表指向原来的对象，当原来的对象数量改变的时候，这个索引表的内容没有同步改变，所以当索引指针往下移动的时候，便找不到要迭代的对象，于是产生错误。List、Set等是动态的，可变对象数量的数据结构，但是Iterator则是单向不可变，只能顺序读取，不能逆序操作的数据结构，当 Iterator 指向的原始数据发生变化时，Iterator自己就迷失了方向。如何才能满足需求呢，需要再定义一个List，用来保存需要删除的对象：
1

List delList = new ArrayList()
最后只需要调用集合的removeAll(Collection con)方法就可以了。
解决方法2：

在找到原因后，则进一步进行解决，经过查阅源码可以发现，iterator也有一个remove方法如下，其中有一个重要的操作为expectedModCount = modCount;

这样就保证了两者的相等。

初步总结

也就是说，在forEach或者迭代器中调用对集合的结构性操作会导致modCount值发生修改，而expectedModCount的值仍然是初始化值，所以在next()中校验不通过抛出异常。所以不要在迭代器迭代过程中使用集合自带的remove、add等操作，而要使用迭代器自带的remove方法，原因就在于此。

那为什么使用迭代器自带的remove方法就不会报错呢？如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");
        for (Iterator it = list.iterator(); it.hasNext(); ) {
            if ("3".equals(it.next()))
                it.remove();
        }
        System.out.println(list);
    }
}

结果如图所示：

深入探究

要搞清楚这中间的区别，再去看看List迭代器remove方法的源码了。下面代码中主要关注红框的2行，第一行作用是删除被迭代的元素，ArrayList.this.remove这个是调用外部类ArrayList的remove方法，上面已经说过了，集合的remove方法是结构性操作，会导致 modCount++ 的，这样等迭代下一个元素时，调用next()时校验expectedModCount和modCount一致性必然会报错，为了防止这个问题，所以下一行expectedModCount = modCount将expectedModCount更新至modCount最新值，使得一致性不被破坏。

这也是为什么使用迭代器自带的remove方法并不会抛出异常的原因。

额外思考

考虑这种情况，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        for (Object o : list) {
            // 删除元素由"3"变为"4"
            if ("4".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

输出结果如下：

为什么这里在forEach遍历中用集合自身的remove方法不会报错？

debug一下，List中前面的元素的遍历过程和上面是一样的，不再赘述。直接看关键处，如下图，这个时候已经遍历到**“4”**这个元素了，即将开始remove操作，remove操作也和上面一样，会调用fastRemove()删除元素，fastRemove()也确实会执行*modCount++*，确实导致了expectedModCount != modCount。但是……

当将要迭代下一个元素的时候，还是会进入hashNext()做判断，很遗憾，这个时候cursor和size都是4，也就是hashNext()条件不成立返回false，也就不会再进入next()方法，自然也就不会再去调用checkForComodification()做校验，也就不会再有机会抛异常了。其实这个时候，list中最后一个元素**“5”**根本也就没遍历到。为了验证这一点，可以在for循环中添加输出代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        for (Object o : list) {
            System.out.println(o);  //输出正在迭代的元素
            if ("4".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

输出结果如下：

会发现只会输出1、2、3、4，不会输出5。

额外思考考

最后再来一种情况，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        for (Object o : list) {
            // 删除元素由变为"5"
            if ("5".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

猜猜结果是啥？有人会认为，不是和刚刚情况一模一样的吗？那就是成功删除了啊，输出1到4啊。呵呵🙄，让您失望了。

为什么会报错？

原因还是在这里，前面 “1”-“4” 四个元素遍历完毕肯定是没问题的，当开始遍历**“5”**时候，通过next()返回元素**“5”**，cursor此时会增加到5，而size由于后面会调用remove减为4了，这个时候hasNext()里的条件返回true又成立啦！所以Itr迭代器又会傻傻的去调用next()，然后checkForComodification()又被调用了，抛出**ConcurrentModificationException**异常。

通过上述的整个分析过程，可以总结出一点结论：

其实整个过程的问题关键所在就是java.util.ArrayList$Itr的hasNext()方法的逻辑。不难看出，每当迭代器返回一个元素时，元素在列表中的索引等于Itr的cursor值，而每次删除一个元素会导致 size– ，不难推断出，如果你要删除的元素恰好位于List倒数第二个位置，则并不会抛出异常，并且会显示正确的删除操作，就像思考的第一个例子，其余情况都会抛出异常。但是就算是不抛异常的情况，其实此时List迭代器内部的expectedModCount 和modCount一致性已经遭到了破坏，只是被掩盖了，所以这样的操作后续可能会有非常大的隐患，个人不建议这样使用，需要在迭代过程操作集合的还是应该用迭代器的方法。

另外，其实除了ArrayList以外，会发现HashMap中也会有modCount属性，而在其相应的结构性操作方法内部，如put()、clear()等都会有对 modCount++ 操作，而在HashMap内部也有一个内部迭代器HashIterator，内部会维护一个expectedModCount属性，其余的套路就都和ArrayList类似了。