ConcurrentModificationException及

ConcurrentModificationException（下文简称CME），即并发修改异常，是Java集合操作中常见的一种异常。本文通过示例及JDK源码分析CME的内部机制，并提出解决方法。

CME的产生

java.util包下很多集合的操作都可能会抛出CME，这里就以ArrayList为例。下面的程序产生包含10个元素的ArrayList，遍历它，并在遍历过程中随机删掉其中一个元素。

public class CMEExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            list.add(String.valueOf(i));
        }
        String random = String.valueOf(new Random().nextInt(10) + 1);
        System.out.println(random);
        for (String s : list) {
            if (s.equals(random)) {
                list.remove(s);
            }
        }
    }
}

多次运行以上程序，发现大多数情况均会抛出CME，如以下输出：

6
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    at me.lmagics.CMEExample.main(CMEExample.java:19)

但是当要删除元素"9"时，就不会抛出异常，执行成功。为什么会有两种不同的情况？下面就通过JDK源码来分析。

CME原因分析（fail-fast机制）

CMEExample类中使用foreach循环来遍历List，也就相当于采用了迭代器。ArrayList的迭代器实现位于私有内部类Itr中，其源码如下。

    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

查看报错信息，CME是在调用Itr.next()方法时，从checkForComodification()方法抛出的，原因是modCount与expectedModCount的值不相等。由上面的代码可知，expectedModCount在Itr初始化时就赋值，其值等于modCount，所以modCount的值一定发生了变化。

modCount字段定义在ArrayList的父类AbstractList中。

protected transient int modCount = 0;

根据JavaDoc的解释，modCount记录了一个列表发生结构化修改（structurally modified，如改变大小或打乱顺序）的次数，类似于版本号。

下图展示了modCount字段会被ArrayList类中的哪些方法修改。注意添加元素的add()与addAll()方法并没有出现，但它们最终调用了ensureExplicitCapacity()方法，故也会修改modCount。

示例代码中调用remove(Object)方法后，嵌套的fastRemove()方法会增加modCount的值，变成11，而expectedModCount的值仍为10，就抛出了CME。
换句话说，ArrayList.remove()方法破坏了迭代器内维护的集合修改状态。如果在迭代过程中进行了任何使modCount改变的操作（不管是单线程还是多线程的环境下），为了防止继续迭代下去发生不可预见的状况，就会立即失败并抛出CME，这就是所谓的快速失败（fail-fast）机制。

那么为什么删除元素"9"就没问题？这与迭代器的hasNext()方法有关。迭代器内维护了指示当前元素的游标cursor，当cursor与列表的大小size相同时，表示没有下一个元素，迭代过程结束。删除掉元素“9”之后，cursor与size的值都是9，所以会退出迭代，next()方法根本不会执行，只是一种巧合而已。

CME的解决方法

就示例中的删除操作而言，正确的方式是不调用容器的remove()方法，而是调用迭代器本身的remove()方法，即：

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals(random)) {
                iterator.remove();
            }
        }

我们可以参考一下Itr.remove()方法的源码，它除了调用ArrayList.remove()方法之外，还做了两件额外的事：

• 将游标cursor重置回上一个读取的元素下标。
• 将expectedModCount重新赋值成当前的modCount。

这样在删除元素的同时，也维护了游标位置和修改状态，因此能够安全地继续迭代。如果需要迭代时添加元素，那么可以利用ArrayList提供的另一种迭代器ListIterator，它的功能更加丰富一点，并且机制几乎相同，不再赘述。

多线程环境

文章开头的例子是在单线程环境演示的，但从CME的命名“并发修改异常”来看，它似乎更偏向于多线程的情况。由于ArrayList本身就是线程不安全的，因此我们采用线程安全的列表Vector再做一次实验，以排除干扰。

public class CMEExample {
    public static void main(String[] args) {
        Vector<String> vector = new Vector<>();
        for (int i = 1; i <= 20; i++) {
            vector.add(String.valueOf(i));
        }
        String random = String.valueOf(new Random().nextInt(20) + 1);
        System.out.println("Random: " + random);

        Thread threadA = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            while (iterator.hasNext()) {
                String s = iterator.next();
                System.out.println("Thread-A: " + s);
                if (s.equals(random)) {
                    iterator.add(s);
                }
            }
        }, "Thread-A");

        Thread threadB = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            while (iterator.hasNext()) {
                System.out.println("Thread-B: " + iterator.next());
            }
        }, "Thread-B");

        threadA.start();
        threadB.start();
    }
}

这个示例创建了有20个元素的Vector与两个线程。线程A遍历该Vector，并从中随机选择一个元素，使用安全的ListIterator.add()方法再插入一个相同的元素；线程B则只做遍历。其输出如下：

Random: 16
Thread-A: 1
Thread-A: 2
Thread-A: 3
Thread-B: 1
Thread-B: 2
Thread-B: 3
Thread-B: 4
Thread-B: 5
Thread-A: 4
Thread-A: 5
Thread-A: 6
Thread-A: 7
Thread-B: 6
Thread-A: 8
Thread-A: 9
Thread-A: 10
Thread-A: 11
Thread-A: 12
Thread-A: 13
Thread-A: 14
Thread-A: 15
Thread-A: 16
Thread-B: 7
Thread-A: 17
Thread-A: 18
Thread-A: 19
Thread-A: 20
Exception in thread "Thread-B" java.util.ConcurrentModificationException
    at java.util.Vector$Itr.checkForComodification(Vector.java:1210)
    at java.util.Vector$Itr.next(Vector.java:1163)
    at me.lmagics.CMEExample.lambda$main$1(CMEExample.java:37)
    at java.lang.Thread.run(Thread.java:748)

可见，CME与容器本身线程安全与否并没有关系。在这种情况下，当线程A添加元素之后，线程A中迭代器的expectedModCount会随着modCount更新，但线程B中迭代器的expectedModCount并不会更新，进而抛出CME。

要解决多线程CME问题，可以考虑对迭代过程加锁，确保多个线程不会同时遍历列表，即：

        Thread threadB = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            synchronized (vector) {
                while (iterator.hasNext()) {
                    System.out.println("Thread-B: " + iterator.next());
                }
            }
        }, "Thread-B");

我们还可以使用并发容器CopyOnWriteArrayList来替代普通的ArrayList与Vector。
CopyOnWriteArrayList（以及其他j.u.c包中的集合）是安全失败（fail-safe）机制的典型应用。它会在写操作时将集合复制一份副本，在副本上写数据，即copy on write，写完成之后再将正本的引用指向副本，而读操作直接在正本上进行。这种读写分离的方法使得它不会抛出CME，之后也会详细地阅读它的源码。

fail-safe的容器比起fail-fast固然安全了很多，但是由于每次写都要复制，时间和空间的开销都更高，因此只适合读多写少的情景。并且它的正本和副本有可能不同步，因此无法保证读取的是最新数据，这也是CAP理论中一致性（consistency）与可用性（availability）矛盾的体现。