Java基础 - 容器类快速报错（ Fail-fast）

Java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容。
如果在你迭代遍历某个容器的过程中，另一个进程介入其中，并且插入、删除或者修改此容器内的某个对象，那么就会出现问题：也许迭代过程已经处理过容器中的该元素了，也许还没处理，也许在调用 size()之后容器的尺寸收缩了——还有许多灾难情景。 Java容器类类库采用快速报错（ fail-fast）机制。它会探查容器上的任何除了你的进程所进行的操作以外的所有变化，一旦它发现其他进程修改了容器，就会立刻抛出 ConcurrentModificationException异常。这就是“快速报错 ”的意思——即，不是使用复杂的算法在事后再检查问题。

TestHashMapFastFail.java

Map hashMap = new HashMap();
hashMap.put(1,1);
hashMap.put(2,2);
hashMap.put(3,3);

Iterator it = hashMap.entrySet().iterator();
hashMap.put(4,4);

it.next();

System.out.println(hashMap);

运行结果：

Exception in thread "main" java.util.ConcurrentModificationException
       at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793)
       at java.util.HashMap$EntryIterator.next(HashMap.java:834)
       at java.util.HashMap$EntryIterator.next(HashMap.java:832)
       at study.java.collections.map.test.TestHashtableAndHashMap.main(TestHashtableAndHashMap.java:38)
       at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
       at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
       at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
       at java.lang.reflect.Method.invoke(Method.java:597)
                at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

这里我们看到抛出了 ConcurrentModificationException，因为在容器取得迭代器之后，又有东西被放入到了该容器中。 HashMap结构已经被改变，所以程序进行了快速报错。

我们来研究一下源代码中是怎样实现这个机制的， HashMap内部的迭代器是HashIterator，迭代真实的处理方法为 nextEntry()：

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;                // next entry to return
    int expectedModCount;    // For fast-fail
    int index;                               // current slot
    Entry<K,V> current;           // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
                        throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
                        throw new NoSuchElementException();

        if ((next = e.next) == null) {
                        Entry[] t = table;
                        while (index < t.length && (next = t[index++]) == null)
                                        ;
        }
        current = e;
        return e;
    }

    public void remove() {
        if (current == null)
                        throw new IllegalStateException();
        if (modCount != expectedModCount)
                        throw new ConcurrentModificationException();
        Object k = current.key;
        current = null;
        HashMap.this.removeEntryForKey(k);
        expectedModCount = modCount;
    }

}

我们注意一下这个判断逻辑：

if (modCount != expectedModCount)
    throw new ConcurrentModificationException();

当 modCount不等于expectedModCount 的时候就会抛出 ConcurrentModificationException异常，这就是机制的处理方式，那么 modCount和expectedModCount 是什么呢？

modCount ：

The number of times this HashMap has been structurally modifiedStructural modifications are those that change the number of mappings inthe HashMap or otherwise modify its internal structure (e.g.,rehash). This field is used to make iterators on Collection-views ofthe HashMap fail-fast. (See ConcurrentModificationException).

modCount表示HashMap 结构改变的次数，结构改变包括改变 mappings数或者是像rehash 一样改变内部结构。下面是源代码中会改变这个属性的取值的方法列表：

* public V put(K key, V value)  ->  private V putForNullKey(V value)
* public V remove(Object key)  ->  final Entry<K,V> removeEntryForKey(Object key)
* final Entry<K,V> removeMapping(Object o)
* public void clear()
* HashIterator. Remove() -> final Entry<K,V> removeEntryForKey(Object key)

expectedModeCount ：

如其名字一样，表示预期的修改数，它是在 HashIterator的构造函数中进行初始化的，初始值为 modCount。当我们迭代元素的时候，调用 HashIterator构造器创建对象

Iterator it = hashMap.entrySet().iterator();

这时就初始化 expectedModeCount，将其值设置为modCount。

这个异常的产生有两个重要的前提：

1. 在迭代过程中，另外一个线程改变 HashMap结构。
   在我们上面的例子中我们获取了一个迭代器，然后再修改 HashMap结构，再迭代，虽然是单线程，但是也模拟了这种效果。
2. 注意 HashMap中modCount 属性的修饰词。

transient volatile int modCount;

我们知道每个线程是有自己的线程变量的，拿我们的例子来说，我们这个线程首先获取了 modCount，放到了自己的线程变量中，那么我们这个线程使用的时候就使用这个原先获取的 modCount，它不是静态变量，其他线程了对我们当前线程应该是没影响的嘛，在 HashMap中有影响，因为这个属性是 volatile的。

Volatile 修饰的成员变量在每次被线程访问时，都强迫从共享内存中重读该成员变量的值。而且，当成员变量发生变化时，强迫线程将变化值回写到共享内存。这样在任何时刻，两个不同的线程总是看到某个成员变量的同一个值。

假设有 A、B 两个线程访问 HashMap，
初始：

modCount =  5 ；

A开始迭代Map ：

expectedModCount = modCount = 5;

迭代过程中 B修改了HashMap 的结构，此时 modCount = 6；
A继续迭代，通过HashIterator的 next方法获取下一个元素，进入到nextEntry方法中，此时：

expectedModCount(5)  !=  modCount(6)

于是就抛出了 ConcurrentModificationException。

API中对快速报错进行了这样的附加描述

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