序

最新在学习迭代器模式的时候，遇到了一个之前一直知道，但是没有深入的问题：不能在集合遍历的时候，去删除集合中的数据，不然会报错。

首先这个问题无论是我们平时开发，还是说阿里的java开发规范中都有提及，而且我也会避免在集合遍历中去进行删除操作，如果真的要遍历的时候删除元素，我也会考虑使用迭代器的方式删除；而然我常常还是处于知其然而不知其所以然的阶段，没有深入源码去了解其背后的知识，导致每当有人提及时，自己却欲语还休，无法侃侃而谈。

所以本篇文章希望从学习过程遇到的问题（迭代器模式中如何删除元素）入手，逐步分析相关容器源码实现，争取能够将问题讲解清楚。

迭代器模式

概念

迭代器模式又叫游标模式，主要是针对集合对象的遍历进行解耦的，像复杂对象如集合、数组、链表、树以及图等等，这些对象如果在遍历过程要处理很复杂的逻辑，比如树的先序、中序和后序遍历，仅仅使用for循环是无法处理的，就需要使用迭代器这样的比较解耦的方式来实现。

迭代器模式我们不常直接使用，但是会使用自己语言中自带的具有迭代功能的方法，比如java的List集合中就通过iterator()方法生成一个具有迭代功能的接口，如果想要使用，直接调用即可，这里不展开讲述。

那么我们要说一说什么呢？我们来说一说一个好玩的，迭代器中如果想删除一个元素该怎么办？以及为什么要这么办？

示例

老规矩，先来段代码看看：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


package design;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author yinan
 * @date 2020/4/6
 */
public class Demo {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            if ("3".equals(iterator.next())) {
                //删除元素，该怎么删？
            }
        }
        System.out.println(list);
    }

}

上面代码片段中有一个删除逻辑需要补充，下面有两种方式来进行删除，你看看哪个可以？

list.remove("3");
iterator.remove();

明眼人当然可以看出来第一个不行，第二个可以，那么我问你第一个不行？会报什么错？还能猜出来吗？

我先放一下上面两个条件放到代码中运行结果吧。

第一个运行结果：

1
2
3
4


Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at design.Demo.main(Demo.java:20)

第二个运行结果：

1

[1, 2]

第一个运行抛出了一个异常，第二个正常输出了，那么我再改一下代码，试试此时会报什么错？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


package design;

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * @author yinan
 * @date 2020/4/6
 */
public class Demo {

    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            if ("3".equals(iterator.next())) {
                //删除元素
            }
        }
        System.out.println(list);
    }

}

也不知你是否看出来上面的代码片段和之前的片段有什么区别了没，我这里说一下，我把代码中的ArrayList改成了CopyOnWriteArrayList，此时运行结果也不卖关子了，答案是两次都能成功运行，没有报错。

分析

下面我们来分析分析，为何出现了这样的情况。

不知道你是否听过java集合中的两个机制，分别叫做：Fail-Fast机制和Fail-Safe机制。

这两个机制我第一次听说是在大学准备面试的时候见到的，当时在学习List源码的时候看到的，但是没有去仔细留意，也不知道干啥的，只是感觉挺高端，除此之外我记得当时还遇到了happens-before原则，也是感觉莫名其妙的东西。

我们还是先来看看这两个机制吧。

Fail-Fast

我们先来看看Fail-Fast定义：

A fail-fast system is nothing but immediately report any failure that is likely to lead to failure. When a problem occurs, a fail-fast system fails immediately. In Java, we can find this behavior with iterators. In case, you have called iterator on a collection object, and another thread tries to modify the collection object, then concurrent modification exception will be thrown. This is called fail-fast.

从定义中，我们大概知道，这东西啊，原来是针对java集合中出现的多个线程（单个线程）同时操作同一集合结构，导致集合结构发生改变（数据变多或变少）时可能会发生的错，而我们上面在集合遍历时对齐进行删除操作就是有可能导致Fail-Fast。

Fail-Safe

和Fail-Fast机制相对的当然是Fail-Safe机制了，它的说明如下：

In this case the iterator will make a copy of the internal data structure and iterates over the copied data structure. Thus any modifications done to the internal data structure will not effect the iterator.

从中大概能看到，这是通过copy一个副本，使得当集合结构被破坏时依然不会抛出异常。

上面的第一个机制决定了我们针对集合进行遍历的时候不能进行结构更改操作，否则可能会发生问题，而第二个机制介绍了一种可以同时进行遍历和结构更改的方案，那就是通过copy一个副本的方式进行。但是，我们明明记得上面的代码片段中使用迭代器方式时是可以同时遍历和删除元素的，难道是使用copy一个副本的方式来实现的？说不定呢！

我们继续往下看……

源码

首先，这里声明一下，我们这里仅仅从迭代器部分源码出发，如果讨论过程中涉及到其他操作容器的功能，那么再深入讨论，所以可能不会对容器中每一个方法的源码都进行详细分析，请做好心理准备。

ArrayList

先来看看ArrayList中的iterator()方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


public Iterator<E> iterator() {
  	//实例化一个迭代器对象
    return new Itr();
}

//实现自Iterator接口的类
private class Itr implements Iterator<E> {
    //游标，对应着下一次调用next()方法返回值的索引
    int cursor;  
    //上一次调用next()方法返回值的索引位置，如果没有调用（初始值）为-1
    int lastRet = -1;
    //expectedModCount：迭代器修改次数
    //modCount：外部类，也就是ArrayList的属性值（继承自AbstractList），默认为0，
    //表示外部类中的方法对集合修改的次数，ArrayList()的remove相关方法以及sort()方法都会导致该数值增加
    //这里保持两个值相等
    int expectedModCount = modCount;

    Itr() {}
		
    //cursor值小于等于size，如果等于size说明集合里面的值已经完全迭代掉了
    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
      	//检查expectedModCount是否等于modCount，如果不等直接抛出异常
        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() {
      	//lastRet小于0表示还没有调用过next()方法，或者前一次调用过remove()方法，直接抛出异常
        if (lastRet < 0)
            throw new IllegalStateException();
      	//检查expectedModCount是否等于modCount，如果不等直接抛出异常
        checkForComodification();

        try {
            //调用ArrayList中的remove方法进行删除
            ArrayList.this.remove(lastRet);
            //删除结束需要维护迭代器类中的属性
            //游标指向上一次调用next()位置，因为删除了当前元素，所以从当前位置往后的所有元素向前移动了一位
            cursor = lastRet;
            lastRet = -1;
            //重新维护两个值相等
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

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

从iterator()方法我们可以看到，其内部还是实例化了一个实现了迭代器接口的类，然后后续所有操作都是在这个类上做的（其实就是迭代器模式的应用），这里面一个比较特殊的地方是，这里面维护了一个变量expectedModCount，当每次调用next()方法的时候都会去校验expectedModCount的值和modCount是否相等，如果相等，那么继续执行，否则会直接抛出异常。而这个异常就是我上面的示例代码运行结果对应的异常。

说明这个异常引起的原因很大一部分是因为这两个值不一致导致的（除此之外，从源码来看，调用迭代器类的remove()方法而引发数组越界，在这里也会抛出ConcurrentModificationException；以及调用next()方法，游标值超出当前集合size也会抛出异常）。

那么针对为什么调用集合内部的remove()方法会抛出异常，而使用迭代器的remove()方法却没事，这个问题，各位到此应该能够解决了，下面我来解答一下这个问题。

先来看看ArrayList类对应的remove()方法，其实不论是remove(Object o)还是remove(int index)内部原理都是相似的，这里直接看remove(Object o)方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
  	//注意这里，删除时会导致modCount值自增
    modCount++;
    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
}

从源码可以看到，因为remove()方法内部会使modCount自增，而Itr类的expectedModCount属性却还是原来的值，所以在执行checkForComodification()方法时，直接抛出异常。

而使用Itr类自带的remove()方法在最后会维护expectedModCount = modCount，这样就不会因为expectedModCount != modCount而抛出异常。

到此ArrayList在遍历时执行自身remove()方法导致异常原因是说清楚了，而CopyOnWriteArrayList为何没有抛出异常呢？接着往下看。

CopyOnWriteArrayList

先来说说CopyOnWriteArrayList和ArrayList的区别吧，但从字面上来看，这个类多了前缀CopyOnWrite，说明这个类在write的时候会copy，那么问题来了：

copy什么呢?

复制一份当前数据

为何要复制数据呢？

是为了写数据的时候不直接对数据进行操作，而是复制一份数据出来，对复制数据进行操作，操作完成之后，再将指针指向修改后的数据。

为什么要这么做呢？

因为CopyOnWriteArrayList类是一个线程安全的类，所谓线程安全，其实就是这个类中的方法在多个线程同时运行的结果和单个线程逐步运行结果是相同的，那么就是线程安全的，或者说一个类或程序所提供的接口对于线程来说是原子操作或多个线程之间的切换不会导致该接口的执行结果存在二义性，也就是说我们不用考虑同步的问题。而CopyOnWriteArrayList为了实现线程安全，针对写数据的操作做了加锁操作。这样写数据的时候是安全的了，但是每一次读数据时候却需要等待写完成，导致执行效率较低，为此采用了复制数据再修改最后将指针指向修改之后数据的方式。

这样做的好处有很多，例如使用迭代器遍历中的集合，在原集合增加或者删除元素的时候是不会导致遍历中的集合抛出异常的，具体实现我们来看看代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    //用来保存集合中的元素
    private transient volatile Object[] array;

    final Object[] getArray() {
        return array;
    }

    final void setArray(Object[] a) {
        array = a;
    }

    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //获取集合元素
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
            //用来存储集合的副本，将原来集合中元素都放到这个副本
            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                //最后一个位置添加元素
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                //指定位置添加元素
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                    numMoved);
            }
            //新元素添加到副本
            newElements[index] = element;
            //将指针指向副本
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }


    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

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

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

CopyOnWriteArrayList源码还是比较容易理解的，相信大家应该都可以看明白。

接下来继续看看CopyOnWriteArrayList生成的迭代器是什么样的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

static final class COWIterator<E> implements ListIterator<E> {
    //集合中的元素快照
    private final Object[] snapshot;

    //游标，下一次需要访问的位置
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }


    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    public boolean hasPrevious() {
        return cursor > 0;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }

    ...

}

可以看到，CopyOnWriteArrayList中的iterator()方法实例化的COWIterator类实现的是ListIterator接口，该接口继承自Iterator接口，同时添加了一些额外的增强方法，例如hasPrevious()、previous()等，而其构造方法是将外部集合当前拥有的元素直接传了进来，此时当前处于迭代阶段的集合肯定不会收到影响。

总结

到此为止，我们本篇文章也要告一段落了，下面我们来总结一下。

首先，在迭代器里面调用集合自身的删除方法是不明智的，因为它很有可能会触发Fail-Fast机制，导致程序在运行中抛出异常。

其次，如果想在迭代器中删除元素，最好还是使用迭代器自身的删除方法，因为迭代器中维护着一个变量，该变量会时刻保持和外部集合中的另外一个变量一致，如果不一致会抛出ConcurrentModificationException，外部集合在删除时没有维护该变量和迭代器内部变量一致性，但迭代器自身的删除方法有维护这两个值相等。

最后，还可以考虑使用CopyOnWriteArrayList，这样在其迭代的时候是可以使用外部集合的删除方法的，毕竟其迭代器的不支持删除方法。

最后还有一个问题，我想在这里和大家分享一下：

分析了CopyOnWriteArrayList之后，有没有感觉这样的实现方式在哪见过呢？我之前遇到过一个相似的，MySql的多版本并发控制，也就是著名的mvcc，它的实现原理你知道吗？它们有哪些异同呢？