从Java的容器说起

ConcurrentModificationException

在 HashMap的源码中，有这样一段注释：

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own <tt>remove</tt> method, the iterator will throw a {@link ConcurrentModificationException}. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

意思就是，当在在一个迭代器使用的途中，容器的结构遭到了改变，就会触发fail-fast机制：抛出ConcurrentModificationException异常。

modCount

在谈fail-fast之前，先看一个在ArrayList、LinkedList、HashMap等容器中，都有出现的变量modCount:

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

modCount用来记录集合结构修改的次数，在容器的源码中，只有对容器进行增加和删除操作时，才会对modCount进行修改。

可以简单的把modCount类比于一个容器结构的版本号，如果在某个操作中，对容器结构进行了修改，就对modCount++。

Fail Fast

通过HashMap中一个内部类迭代器的源码，对Fail Fast机制做个介绍。

迭代器的属性、构造方法

   abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot

        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        ……
}

这里的重点是：expectedModCount这个变量。
在迭代器初始化的时候，注意expectedModCount = modCount;这一行，记录了当前该容器的modCount。用于在后面的操作中进行比较。

迭代器中使用到了`expectedModCount`的地方

        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                // 检测到容器结构的修改次数与预期不一致，抛出异常
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

       public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                // 检测到容器结构的修改次数与预期不一致，抛出异常
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
                // 自己的删除操作，会更新 expectedModCount 
            expectedModCount = modCount;
        }

可以看到，在迭代器的迭代和删除操作中，都会将modCount与预期值expectedModCount进行比较，不一致时，即说明在本次使用迭代器操作的过程中，容器结构被修改了，并抛出ConcurrentModificationException。

Fail Fast 具体机制

显然，Fail Fast的机制就是每次操作时，都会对modCount进行比较。
以保证在本次操作的过程中，容器结构没有被修改，一定程度上保证了安全性。

导致 Fail Fast 的原因

并发修改

在操作执行过程中，数据被修改，最可能的原因就是，多线程的并发环境：
本线程在操作的时候，其他线程对本容器进行了增加或者删除操作，导致modCount与操作开始时保存的expectedModCount不一致，导致并发修改异常ConcurrentModificationException。

单线程环境

除了并发的环境，单线程也会出现ConcurrentModificationException：

从迭代器的源码可以看到，在迭代器被创建的时候会记录expectedModCount，并且在迭代器自己的删除操作中会更新ConcurrentModificationException。
但是如果在使用迭代器操作的过程中，使用容器自带的remove()方法来操作容器，还是会导致modCount与迭代器记录expectedModCount相异，从而抛出异常。

操作代码：

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }
        System.out.println("定义迭代器");
        Iterator<Integer> iterator = list.iterator();
        System.out.println("修改容器结构");
        list.remove(2);
        System.out.println("使用迭代器遍历");
        while (iterator.hasNext()) {
            // 使用迭代器迭代   此时会抛出异常
            System.out.println(iterator.next());
        }
    }

结果：

定义迭代器
修改容器结构
使用迭代器遍历
Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:939)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:893)
    at Main.main(Main.java:27)

Fail Safe

要解决Fail Fast问题，最简单的办法就是对并发进行控制。

思路一：使用锁对并发进行控制。
例如在每次对容器进行操作的时候，要求先获取到锁，操作完再释放。但是这样会阻塞并发的操作，效率较低。

思路二：每次对容器进行写操作时，先复制一个副本出来，操作完再修改之前对象的引用。
这样修改就不会作用到原容器上，不会影响原容器的modCount，从而不会导致异常。但是这样每次都要复制一个副本，对内存的消耗还是比较大的。

具体操作：可以使用java.util.concurrent包中支持并发的容器，如CopyOnWriteArrayList、ConcurrentHashMap等。

For example:

    public static void main(String[] args) {
        // 使用 CopyOnWriteArrayList
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }
        System.out.println("定义迭代器");
        Iterator<Integer> iterator = list.iterator();
        System.out.println("修改容器结构");
        list.remove(2);
        System.out.println("使用迭代器遍历");
        while (iterator.hasNext()) {
            // 使用迭代器迭代   不会抛出异常
            System.out.println(iterator.next());
        }
    }

定义迭代器
修改容器结构
使用迭代器遍历
0
1
2
3
4

Fail Fast和Fail Safe