ArrayList的 fast-fail（快速失败）机制

本文主要讲了 ArrayList的 fast-fail（快速失败）机制。

为什么集合可以使用 foreach 循环

我们发现，在java中，我们使用集合都可以通过foreach来遍历，就像下面的代码一样

List<Integer> list = new ArrayList<>();
list.add(1);
for (Integer integer : list) {
    // 循环体内代码
    System.out.println(integer);
}

上面那种迭代方法去除语法糖之后实际等价于以下写法

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    Integer integer = iterator.next();
    // 循环体内代码
    System.out.println(integer);
}

其原理其实很简单，这是一个java的语法糖，只要类实现了接口 Iterable 就可以。因为所有的集合都实现了一个父接口 Collection，而 Collection 继承了 Iterable。所有只要在 iterator() 方法中返回一个 Iterator，foreach 会自动调用这个 Iterator 的方法去遍历这个接口。因此所有的集合都能通过 foreach 来遍历。以下 Iterable 的源码。

public interface Iterable<T> {

    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

知道了原理，我们自己可以动手试一试，自己实现一个队列或者栈，通过实现这个接口来达到被 foreach 遍历的功能。

为什么在 foreach 的时候调用 remove 会抛出异常

既然我们知道了上面的原理，那要找到原因我们只需要看 ArrayList 的 iterator() 方法返回的迭代器实现的方法即可。翻阅源码我们看到以下代码。

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


private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    // 复制集合的修改次数并保存
    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();
    }
}

在此之前我们需要讲一讲这个 modcount 是什么，其实这个很简单，就是集合内部的一个修改记录的变量，只要执行集合的 add、remove、sort 等方法，都会执行 modCount++ 来记录一下集合的修改次数。

上一节我们知道，foreach 方法等价于执行 while 迭代器的操作。我们可以看到，Iterator 的 next() 方法中，调用了 checkForComodification() 方法，而此方法的唯一作用就是判断 modCount 是否等于创建迭代器时候保存的 expectedModCount，如果不等于则抛出并发修改异常。而在什么时候会不等于呢，那就是创建迭代器后，对集合进行了会递增 modcount 的操作。而 add、remove、sort 都会对集合进行操作记录（也就是 modcount++）因此只要在 foreach 中对原集合执行这些方法，都会导致异常的产生。

另一种 foreach 循环

之前 Iterable 接口的方法，我们看到了一个 default 的 forEach 方法。这是在 java8 中新增的方法，其本质也是利用了函数式编程简化了一下我们对 foreach 的调用，本质并无区别。但是 ArrayList 对这个方法进行了重写，改用成最基本的 for 循环实现，判断快速失败的机制与迭代器并无二样，都是通过记录 modcount 并判断是否一致来确保迭代过程是否修改过原集合。

@Override
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

对 Iterator 的一些补充

ArrayList 中，除了实现了继承而来的 iterator() 方法，也有一些其他的 iterator，例如 spliterator 和 listIterator。foreach 调用的只有继承而来的 iterator() 方法返回的迭代器的方法，其他的迭代器只是增加了一些迭代器的功能，因为和本文无关，有兴趣的可以自己去了解一下。

为什么集合可以使用 foreach 循环

为什么在 foreach 的时候 调用 remove 会抛出异常

另一种 foreach 循环

对 Iterator 的一些补充

为什么在 foreach 的时候调用 remove 会抛出异常