Fail-fast And fail-safe

我们可以通过迭代器遍历集合对象，迭代器分为fail-fast和fail-safe两种类型，fail-fast是指当我们通过迭代器遍历集合时，如果集合元素发生了修改，会抛出ConcurrentModificationException异常。fail-safe类迭代器则不会抛出这类异常。

Fail-fast case

public static void main(String[] args) {
    ArrayList<Integer>data = new ArrayList<>();
    data.add(1);
    data.add(2);
    data.add(3);
    Iterator<Integer> ptr = data.iterator();
    while (ptr.hasNext()){
        Integer a = ptr.next();
        System.out.println(a);
        data.remove(a);
    }
}

执行如上代码，在通过迭代器遍历集合时，对集合进行修改，删除了一个元素，迭代器在遍历时会抛出如下ConcurrentModificationException异常：

Fail-Fast Iterators internal working

以ArrayList为例，分析fail-fast的原理。ArrayList有一个迭代器内部类 ListItr, 我们在通过iterator()方法返回ArrayList对象的迭代器时就是返回这个类的一个实例。

1
2
3

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

内部类 ListItr 有一个属性expectedModCount，在创建 ListItr 实例时会赋值为modCount，而modCount则是在构建迭代器之前当前ArrayList实例的修改次数，当对ArrayList对象进行修改时，modCount的值都会加1。内部类 ListItr 有一个内部方法：

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

在通过迭代器调用next, add, remove, set等方法时，首先会执行如上checkForComodification方法，如果在这之前集合对象发生了修改，那modCount的值增加以后，将会执行if语句中泡出异常的操作。

但是如果我们使用内部类ListItr自身提供的修改方法，则不会抛出ConcurrentModificationException异常，因为这些方法实现会更新expectedModCount的值。

Fail-safe case

和fail-fast的迭代器不同，fail-safe类迭代器遍历集合时，如果对集合进行修改，会拷贝一份集合元素的副本，在副本上进行修改，所以不会抛出异常。以CopyOnWriteArrayList为例：

public static void main(String[] args) {
    List<Integer> data = new CopyOnWriteArrayList<>();
    data.add(1);
    data.add(2);
    data.add(3);
    Iterator<Integer>iterator = data.iterator();
    while (iterator.hasNext()){
        Integer a = iterator.next();
        if (a==2){
            data.add(4); //modify while traverse over the collection.
        }
        System.out.print(String.valueOf(a)+' ');
    }
}

运行结果：

即时我们在遍历过程中对集合进行了添加元素，也不会体现在遍历结果中，因为是在另一个副本中进行添加的。

Fail-safe internal working

看一下是如何对副本进行操作的，以add方法为例：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray(); //return array, which store the element.
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); //array length incremented to original length + 1, and copy the original elements to newElement array.
        newElements[len] = e; //the last solt is e, which we want to add.
        setArray(newElements); //set the original array reference to newElements.
        return true;
    } finally {
        lock.unlock();
    }
}

可见添加元素是重新开辟了一份数组空间，添加了元素之后再修改数组引用。CopyOnWriteArrayList的迭代器遍历的却是原来的数组：

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0); //getArray() return the original array reference.
}
private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    //traverse the array by snapshot, the snapshot is the original array. elements may receive new array 
    //value, so we need use snapshot to store its reference.
    snapshot = elements; 
}

显然，使用CopyOnWriteArrayList的缺点也是明显的，首先，由于在副本上进行修改操作，遍历其上的迭代器不能反映出其最新的状态，其次，需要一份额外的内存空间，还需要对元素进行拷贝迁移，这也是很耗费性能的，所以应该尽量在读多写上的场景进行使用。

参考文献

Fail-fast and Fail-safe iterations in Java Collections