java ArrayList 迭代器快速失败源码分析

2018-07-25 13:05:57来源：博客园阅读 ()

先来看一个例子：

 1     @Test
 2     void test2() {
 3         ArrayList<String> list = new ArrayList<String>();
 4         list.add("a");
 5         list.add("b");
 6         list.add("c");
 7         list.add("d");
 8         list.add("e");
 9 //        list.add("f");
10         Iterator<String> iterator = list.iterator();
11         while(iterator.hasNext()){
12             String str = (String) iterator.next();
13             if(str.equals("d")){
14                 list.remove(str);
15 //                iterator.remove();
16             }else{
17                 System.out.println(str);
18             }
19         }
20     }

Console:

1 a
2 b
3 c

这段代码运行不会报错，但输出不符合我们的预期。我们预期应该是输出：a,b,c,e

如果我们换成删除c，则会报 java.util.ConcurrentModificationException 异常

为什么会出现这个问题呢？

我们跟踪到源码可以发现，ArrayList 类有一个成员变量 modCount 继承自 AbstractList 类

AbstractList 类：

1 protected transient int modCount = 0;

transient 关键字修饰，表明变量不必参与序列化。
这个变量的作用是记录list 结构被修改的次数
在add 和 remove 方法里面都能看到它的身影
add方法：

1     //add方法会调用此方法
2     private void ensureExplicitCapacity(int minCapacity) {
3         modCount++;
4 
5         // overflow-conscious code
6         if (minCapacity - elementData.length > 0)
7             grow(minCapacity);
8     }

remove(int)方法：

 1     public E remove(int index) {
 2         rangeCheck(index);
 3 
 4         modCount++;
 5         E oldValue = elementData(index);
 6 
 7         int numMoved = size - index - 1;
 8         if (numMoved > 0)
 9             System.arraycopy(elementData, index+1, elementData, index,
10                              numMoved);
11         elementData[--size] = null; // clear to let GC do its work
12 
13         return oldValue;
14     }

remove(Object) 方法:

 1     public boolean remove(Object o) {
 2         if (o == null) {
 3             for (int index = 0; index < size; index++)
 4                 if (elementData[index] == null) {
 5                     fastRemove(index);
 6                     return true;
 7                 }
 8         } else {
 9             for (int index = 0; index < size; index++)
10                 if (o.equals(elementData[index])) {
11                     fastRemove(index);
12                     return true;
13                 }
14         }
15         return false;
16     }

而ArrayList的迭代器是ArrayList的一个内部类：

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

Itr 源码：

 1     private class Itr implements Iterator<E> {
 2         int cursor;       // index of next element to return
 3         int lastRet = -1; // index of last element returned; -1 if no such
 4         int expectedModCount = modCount;
 5 
 6         Itr() {}
 7 
 8         public boolean hasNext() {
 9             return cursor != size;
10         }
11 
12         @SuppressWarnings("unchecked")
13         public E next() {
14             checkForComodification();
15             int i = cursor;
16             if (i >= size)
17                 throw new NoSuchElementException();
18             Object[] elementData = ArrayList.this.elementData;
19             if (i >= elementData.length)
20                 throw new ConcurrentModificationException();
21             cursor = i + 1;
22             return (E) elementData[lastRet = i];
23         }
24 
25         public void remove() {
26             if (lastRet < 0)
27                 throw new IllegalStateException();
28             checkForComodification();
29 
30             try {
31                 ArrayList.this.remove(lastRet);
32                 cursor = lastRet;
33                 lastRet = -1;
34                 expectedModCount = modCount;
35             } catch (IndexOutOfBoundsException ex) {
36                 throw new ConcurrentModificationException();
37             }
38         }
39 
40         @Override
41         @SuppressWarnings("unchecked")
42         public void forEachRemaining(Consumer<? super E> consumer) {
43             Objects.requireNonNull(consumer);
44             final int size = ArrayList.this.size;
45             int i = cursor;
46             if (i >= size) {
47                 return;
48             }
49             final Object[] elementData = ArrayList.this.elementData;
50             if (i >= elementData.length) {
51                 throw new ConcurrentModificationException();
52             }
53             while (i != size && modCount == expectedModCount) {
54                 consumer.accept((E) elementData[i++]);
55             }
56             // update once at end of iteration to reduce heap write traffic
57             cursor = i;
58             lastRet = i - 1;
59             checkForComodification();
60         }
61 
62         final void checkForComodification() {
63             if (modCount != expectedModCount)
64                 throw new ConcurrentModificationException();
65         }
66     }

可以看到迭代器有一个内部变量 expectedModCount 是拷贝的 modCount

next() 会检查modCount 是否改变，若改变则抛出 ConcurrentModificationException 异常

所以文章开头的第一种情况就可以解释了，之所以删除d’没有报错是因为，d是倒数第二个元素，删除之后，游标 cursor == size

在hasNext方法执行的时候就已经返回了false，没有执行next()方法

而改成c以后，next()会被执行，从而检查出modCount 被修改，抛出异常。

而调用迭代器的remove 方法就不会出现这种情况，因为它更新了expectedModCount，使之与 modCount 保持一致

迭代器的remove方法：

 1 public void remove() {
 2             if (lastRet < 0)
 3                 throw new IllegalStateException();
 4             checkForComodification();
 5 
 6             try {
 7                 ArrayList.this.remove(lastRet);
 8                 cursor = lastRet;
 9                 lastRet = -1;
　　　　　　　　　　　　//更新expectedModCount
10                 expectedModCount = modCount;
11             } catch (IndexOutOfBoundsException ex) {
12                 throw new ConcurrentModificationException();
13             }
14         }