ArrayList的遍历方式与fail-fast

标签：Iterator iterator ArrayList fast modCount remove fail listIterator arrayList

遍历方式

普通for循环遍历

for (int i = 0; i < arrayList.size(); i++) {
    System.out.println(arrayList.get(i));
}

推荐使用普通for循环，效率最高。

Iterator迭代

Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

增强foreach循环遍历

for (Integer item : arrayList) {
    System.out.println(item);
}

增强foreach循环遍历，只是一个语法糖，在编译的时候foreach的语法会转换成Iterator迭代方法，可以通过观察两种方法的字节码或者反编译class文件（语法糖会消失）来验证这一点。

for (Integer item : arrayList) {
    System.out.println(item);
}

Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

对应的字节码如下：

31 aload_1
 // 增强foreach开始
32 invokevirtual #8 <java/util/ArrayList.iterator>
35 astore_2
36 aload_2
37 invokeinterface #9 <java/util/Iterator.hasNext> count 1
42 ifeq 65 (+23)
45 aload_2
46 invokeinterface #10 <java/util/Iterator.next> count 1
51 checkcast #11 <java/lang/Integer>
54 astore_3
55 getstatic #12 <java/lang/System.out>
58 aload_3
59 invokevirtual #13 <java/io/PrintStream.println>
62 goto 36 (-26)
 // 增强foreach结束
65 aload_1
 // Iterator开始
66 invokevirtual #8 <java/util/ArrayList.iterator>
69 astore_2
70 aload_2
71 invokeinterface #9 <java/util/Iterator.hasNext> count 1
76 ifeq 94 (+18)
79 getstatic #12 <java/lang/System.out>
82 aload_2
83 invokeinterface #10 <java/util/Iterator.next> count 1
88 invokevirtual #13 <java/io/PrintStream.println>
91 goto 70 (-21)
 // Iterator开始

使用反编译工具javap命令，反编译后得到的java代码如下：

Iterator iterator = arrayList.iterator();

while(iterator.hasNext()) {
    Integer item = (Integer)iterator.next();
    System.out.println(item);
}

iterator = arrayList.iterator();

while(iterator.hasNext()) {
    System.out.println(iterator.next());
}

从上面的代码可以得出以下两个结论：

增加for循环是一个语法糖，底层使用Iterator实现。
泛型也是一个语法糖，底层会使用强制类型转换。

ListIterator迭代

ListIterator<Integer> listIterator = arrayList.listIterator();
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
}

Iterator与ListIterator的比较

首先看一下Iterator接口的方法：

boolean hasNext();
E next();
void remove();

再看一下ListIterator迭代器的方法，ListIterator继承了Iterator：

boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
void set(E e);
void add(E e);

两者的区别：

使用范围不同，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。
ListIterator有add方法，可以向List中添加对象，而Iterator不能。
ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。
ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。

四种遍历方法的比较

普通for循环效率最高。
其他三种遍历方式都是采用Iterator迭代，增强for循环底层采用的Iterator迭代（语法糖），而ListItr(ListIterator接口底层具体实现类的名称)只是继承了Itr(Iterator接口底层具体实现类的名称)，并未重写父类的方法。

ListIterator的使用

向后遍历

向后遍历的操作与Iterator的操作类似。

ListIterator<Integer> listIterator = arrayList.listIterator();
while (listIterator.hasNext()) {
    System.out.println(listIterator.nextIndex() + ":" + listIterator.next());
}

向前遍历

向前遍历需要先将游标移至最后，否则无法遍历出数据。

ListIterator<Integer> listIterator = arrayList.listIterator(arrayList.size()); // 先将游标移至最后
while (listIterator.hasPrevious()) {
    System.out.println(listIterator.previousIndex() + ":" + listIterator.previous());
}

添加元素

添加元素是添加到游标前面，下面的元素66会添加到数组索引为0的位置。

ListIterator<Integer> listIterator = arrayList.listIterator();
listIterator.add(66);
System.out.println(Arrays.toString(arrayList.toArray()));

删除元素

删除迭代器最后一次操作的元素，也就是更新最后一次调用next()或者previous()返回的元素。注意，当没有迭代，也就是没有调用next()或者previous()直接调用remove()时会报java.lang.IllegalStateException错。

ListIterator<Integer> listIterator = arrayList.listIterator();
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
    listIterator.remove();
}
System.out.println(arrayList.size());

修改元素

修改迭代器最后一次操作的元素，与删除元素一样，必须先迭代元素后再进行修改。

ListIterator<Integer> listIterator = arrayList.listIterator();
while (listIterator.hasNext()) {
    listIterator.set(listIterator.next() * 10);
}
System.out.println(Arrays.toString(arrayList.toArray()));

fail-fast快速失败

fail-fast错误重现

Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
    arrayList.remove(1);
}

运行结果如下：

java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    at com.morris.javase.list.FailFastDemo.failFast(FailFastDemo.java:27)
...

fail-fast发生在通过Iterator去遍历集合的过程中该集合的内容被修改了，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

fail-fast出现的原因

产生fail-fast事件，是通过抛出ConcurrentModificationException异常来触发的。那么，ArrayList是如何抛出ConcurrentModificationException异常的呢?

// 此值从ArrayList父类AbstractList继承而来
protected transient int modCount = 0; // 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1

// Itr为ArrayList的内部类
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; 
...
public E next() {
    checkForComodification();
    ...
}

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();
    }
}

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

从Itr的源码中可以发现，在调用next()和remove()时，都会执行checkForComodification()方法。若modCount != expectedModCount，则抛出ConcurrentModificationException异常，产生fail-fast事件。那么什么时候modCount != expectedModCount呢？

从Itr类中，我们知道expectedModCount在创建Itr对象时，被赋值为modCount，所以expectedModCount不可能被修改为不等于modCount。所以，需要考证的就是modCount何时会被修改。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 添加元素时modCount被修改

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

public E remove(int index) {
    rangeCheck(index);

    modCount++; // 删除元素时modCount被修改
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

public void clear() {
    modCount++; // 清空元素时modCount被修改

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

从ArrayList的源码中可以发现：无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值。

总结：当一个集合进行Iterator遍历的的时候，该集合的内容被所改变(即调用add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

fail-fast解决办法一

在单线程的遍历过程中，如果要进行remove操作，可以调用迭代器的remove方法而不是集合类的remove方法。看看ArrayList中迭代器的remove方法的源码：

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

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount; // 会将expectedModCount重新赋值
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

可以看到，该remove()方法最后会将modCount重新赋值给expectedModCount，这样两个值就不会不相等，也就不会抛出ConcurrentModificationException异常，但是该方法有一定的局限性，只能remove当前遍历过的那个元素。

通过Iterator的remove()删除代码如下：

Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
    iterator.remove();
}

fail-fast解决办法二

只有用Iterator遍历的时候才会去检查modCount与expectedModCount是否相等，用普通for循环遍历不会导致fail-fast。

for (int i = 0; i < arrayList.size(); i++) {
    arrayList.remove(0);
}

fail-fast解决办法三

前面两种方法都只能在单线程下解决fail-fast，在多线程下可以使用CopyOnWriteArrayList替换ArrayList。

Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到。

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

看看CopyOnWriteArrayList的源码:

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

public E get(int index) {
    return get(getArray(), index);
}

读的时候不需要加锁，如果读的时候有多个线程正在向ArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的ArrayList。

标签：Iterator,iterator,ArrayList,fast,modCount,remove,fail,listIterator,arrayList
From： https://blog.51cto.com/u_6784072/6216475