ArrayList的遍历方式与fail-fast

た入场券 2022-11-07 05:46 19阅读 0赞

# 遍历方式 #

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

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

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

## 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);

两者的区别：

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