JAVA高级面试进阶训练营视频教程

admin

环境：JDK 1.8.0_111

在Java开发过程中，使用iterator遍历集合的同时对集合进行修改就会出现java.util.ConcurrentModificationException异常，本文就以ArrayList为例去理解和解决这种异常。

一、单线程情况下问题分析及解决方案

1.1 问题复现

先上一段抛异常的代码。

 1     public void test1()  {
 2         ArrayList<Integer> arrayList = new ArrayList<>();
 3         for (int i = 0; i < 20; i++) {
 4             arrayList.add(Integer.valueOf(i));
 5         }
 6 
 7         // 复现方法一
 8         Iterator<Integer> iterator = arrayList.iterator();
 9         while (iterator.hasNext()) {
10             Integer integer = iterator.next();
11             if (integer.intValue() == 5) {
12                 arrayList.remove(integer);
13             }
14         }
15 
16         // 复现方法二
17         iterator = arrayList.iterator();
18         for (Integer value : arrayList) {
19             Integer integer = iterator.next();
20             if (integer.intValue() == 5) {
21                 arrayList.remove(integer);
22             }
23         }
24     }

在这个代码中展示了两种能抛异常的实现方式。

1.2、问题原因分析

先来看实现方法一，方法一中使用Iterator遍历ArrayList， 抛出异常的是iterator.next()。看下Iterator next方法实现源码

 1         public E next() {
 2             checkForComodification();
 3             int i = cursor;
 4             if (i >= size)
 5                 throw new NoSuchElementException();
 6             Object[] elementData = ArrayList.this.elementData;
 7             if (i >= elementData.length)
 8                 throw new ConcurrentModificationException();
 9             cursor = i + 1;
10             return (E) elementData[lastRet = i];
11         }
12 
13         final void checkForComodification() {
14             if (modCount != expectedModCount)
15                 throw new ConcurrentModificationException();
16         }

在next方法中首先调用了checkForComodification方法，该方法会判断modCount是否等于expectedModCount，不等于就会抛出java.util.ConcurrentModificationExcepiton异常。

我们接下来跟踪看一下modCount和expectedModCount的赋值和修改。

modCount是ArrayList的一个属性，继承自抽象类AbstractList，用于表示ArrayList对象被修改次数。

1 protected transient int modCount = 0;

整个ArrayList中修改modCount的方法比较多，有add、remove、clear、ensureCapacityInternal等，凡是设计到ArrayList对象修改的都会自增modCount属性。

在创建Iterator的时候会将modCount赋值给expectedModCount，在遍历ArrayList过程中，没有其他地方可以设置expectedModCount了，因此遍历过程中expectedModCount会一直保持初始值20（调用add方法添加了20个元素，修改了20次）。

1 int expectedModCount = modCount; // 创建对象时初始化

遍历的时候是不会触发modCount自增的，但是遍历到integer.intValue() == 5的时候，执行了一次arrayList.remove(integer)，这行代码执行后modCount++变为了21，但此时的expectedModCount仍然为20。

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

在执行next方法时，遇到modCount != expectedModCount方法，导致抛出异常java.util.ConcurrentModificationException。

明白了抛出异常的过程，但是为什么要这么做呢？很明显这么做是为了阻止程序员在不允许修改的时候修改对象，起到保护作用，避免出现未知异常。引用网上的一段解释，点击查看解释来源

Iterator 是工作在一个独立的线程中，并且拥有一个 mutex 锁。 
Iterator 被创建之后会建立一个指向原来对象的单链索引表，当原来的对象数量发生变化时，这个索引表的内容不会同步改变。
当索引指针往后移动的时候就找不到要迭代的对象，所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。
所以 Iterator 在工作的时候是不允许被迭代的对象被改变的。但你可以使用 Iterator 本身的方法 remove() 来删除对象， Iterator.remove() 方法会在删除当前迭代对象的同时维护索引的一致性。

再来分析下第二种for循环抛异常的原因：

 1     public void forEach(Consumer<? super E> action) {
 2         Objects.requireNonNull(action);
 3         final int expectedModCount = modCount;
 4         @SuppressWarnings("unchecked")
 5         final E[] elementData = (E[]) this.elementData;
 6         final int size = this.size;
 7         for (int i=0; modCount == expectedModCount && i < size; i++) {
 8             action.accept(elementData);
 9         }
10         if (modCount != expectedModCount) {
11             throw new ConcurrentModificationException();
12         }
13     }

在for循环中一开始也是对expectedModCount采用modCount进行赋值。在进行for循环时每次都会有判定条件modCount == expectedModCount，当执行完arrayList.remove(integer)之后，该判定条件返回false退出循环，然后执行if语句，结果同样抛出java.util.ConcurrentModificationException异常。

这两种复现方法实际上都是同一个原因导致的。

1.3 问题解决方案

上述的两种复现方法都是在单线程运行的，先来说明单线程中的解决方案：

 1     public void test2() {
 2         ArrayList<Integer> arrayList = new ArrayList<>();
 3         for (int i = 0; i < 20; i++) {
 4             arrayList.add(Integer.valueOf(i));
 5         }
 6 
 7         Iterator<Integer> iterator = arrayList.iterator();
 8         while (iterator.hasNext()) {
 9             Integer integer = iterator.next();
10             if (integer.intValue() == 5) {
11                 iterator.remove();
12             }
13         }
14     }

这种解决方案最核心的就是调用iterator.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;
10                 expectedModCount = modCount;
11             } catch (IndexOutOfBoundsException ex) {
12                 throw new ConcurrentModificationException();
13             }
14         }

在iterator.remove()方法中，同样调用了ArrayList自身的remove方法，但是调用完之后并非就return了，而是expectedModCount = modCount重置了expectedModCount值，使二者的值继续保持相等。

针对forEach循环并没有修复方案，因此在遍历过程中同时需要修改ArrayList对象，则需要采用iterator遍历。

上面提出的解决方案调用的是iterator.remove()方法，如果不仅仅是想调用remove方法移除元素，还想增加元素，或者替换元素，是否可以呢？浏览Iterator源码可以发现这是不行的，Iterator只提供了remove方法。

但是ArrayList实现了ListIterator接口，ListIterator类继承了Iter，这些操作都是可以实现的，使用示例如下：

 1     public void test3() {
 2         ArrayList<Integer> arrayList = new ArrayList<>();
 3         for (int i = 0; i < 20; i++) {
 4             arrayList.add(Integer.valueOf(i));
 5         }
 6 
 7         ListIterator<Integer> iterator = arrayList.listIterator();
 8         while (iterator.hasNext()) {
 9             Integer integer = iterator.next();
10             if (integer.intValue() == 5) {
11                 iterator.set(Integer.valueOf(6));
12                 iterator.remove();
13                 iterator.add(integer);
14             }
15         }
16     }

二、 多线程情况下的问题分析及解决方案

单线程问题解决了，再来看看多线程情况。

2.1 问题复现

 1     public void test4() {
 2         ArrayList<Integer> arrayList = new ArrayList<>();
 3         for (int i = 0; i < 20; i++) {
 4             arrayList.add(Integer.valueOf(i));
 5         }
 6 
 7         Thread thread1 = new Thread(new Runnable() {
 8             @Override
 9             public void run() {
10                 ListIterator<Integer> iterator = arrayList.listIterator();
11                 while (iterator.hasNext()) {
12                     System.out.println("thread1 " + iterator.next().intValue());
13                     try {
14                         Thread.sleep(1000);
15                     } catch (InterruptedException e) {
16                         e.printStackTrace();
17                     }
18                 }
19             }
20         });
21 
22         Thread thread2 = new Thread(new Runnable() {
23             @Override
24             public void run() {
25                 ListIterator<Integer> iterator = arrayList.listIterator();
26                 while (iterator.hasNext()) {
27                     System.out.println("thread2 " + iterator.next().intValue());
28                     iterator.remove();
29                 }
30             }
31         });
32         thread1.start();
33         thread2.start();
34     }

在个测试代码中，开启两个线程，一个线程遍历，另外一个线程遍历加修改。程序输出结果如下

thread1 0
thread2 0
thread2 1
thread2 2
thread2 3
thread2 4
thread2 5
thread2 6
thread2 7
thread2 8
thread2 9
thread2 10
thread2 11
thread2 12
thread2 13
thread2 14
thread2 15
thread2 16
thread2 17
thread2 18
thread2 19
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at com.snow.ExceptionTest$1.run(ExceptionTest.java:74)
	at java.lang.Thread.run(Thread.java:745)

Process finished with exit code 0

2.2 问题分析

从上面代码执行结果可以看出thread2 遍历结束后，thread1 sleep完1000ms准备遍历第二个元素，next的时候抛出异常了。我们从时间点分析一下抛异常的原因

时间点	arrayList.modCount	thread1 iterator.expectedModCount	thread2 iterator.expectedModCount
thread start，初始化iterator	20	20	20
thread2.remove()调用之后	21	20	21

 

 

 

两个thread都是使用的同一个arrayList，thread2修改完后modCount = 21，此时thread2的expectedModCount = 21 可以一直遍历到结束；thread1的expectedModCount仍然为20，因为thread1的expectedModCount只是在初始化的时候赋值，其后并未被修改过。因此当arrayList的modCount被thread2修改为21之后，thread1想继续遍历必定会抛出异常了。

在这个示例代码里面，两个thread，每个thread都有自己的iterator，当thread2通过iterator方法修改expectedModCount必定不会被thread1感知到。这个跟ArrayList非线程安全是无关的，即使这里面的ArrayList换成Vector也是一样的结果，不信上测试代码：

 1     public void test5() {
 2         Vector<Integer> vector = new Vector<>();
 3         for (int i = 0; i < 20; i++) {
 4             vector.add(Integer.valueOf(i));
 5         }
 6 
 7         Thread thread1 = new Thread(new Runnable() {
 8             @Override
 9             public void run() {
10                 ListIterator<Integer> iterator = vector.listIterator();
11                 while (iterator.hasNext()) {
12                     System.out.println("thread1 " + iterator.next().intValue());
13                     try {
14                         Thread.sleep(1000);
15                     } catch (InterruptedException e) {
16                         e.printStackTrace();
17                     }
18                 }
19             }
20         });
21 
22         Thread thread2 = new Thread(new Runnable() {
23             @Override
24             public void run() {
25                 ListIterator<Integer> iterator = vector.listIterator();
26                 while (iterator.hasNext()) {
27                     Integer integer = iterator.next();
28                     System.out.println("thread2 " + integer.intValue());
29                     if (integer.intValue() == 5) {
30                         iterator.remove();
31                     }
32                 }
33             }
34         });
35         thread1.start();
36         thread2.start();
37     }

执行后输出结果为：

thread1 0
thread2 0
thread2 1
thread2 2
thread2 3
thread2 4
thread2 5
thread2 6
thread2 7
thread2 8
thread2 9
thread2 10
thread2 11
thread2 12
thread2 13
thread2 14
thread2 15
thread2 16
thread2 17
thread2 18
thread2 19
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.Vector$Itr.checkForComodification(Vector.java:1184)
	at java.util.Vector$Itr.next(Vector.java:1137)
	at com.snow.ExceptionTest$3.run(ExceptionTest.java:112)
	at java.lang.Thread.run(Thread.java:745)

Process finished with exit code 0

test5()方法执行结果和test4()是相同的，那如何解决这个问题呢？

2.3 多线程下的解决方案

2.3.1 方案一：iterator遍历过程加同步锁，锁住整个arrayList

 1     public static void test5() {
 2         ArrayList<Integer> arrayList = new ArrayList<>();
 3         for (int i = 0; i < 20; i++) {
 4             arrayList.add(Integer.valueOf(i));
 5         }
 6 
 7         Thread thread1 = new Thread(new Runnable() {
 8             @Override
 9             public void run() {
10                 synchronized (arrayList) {
11                     ListIterator<Integer> iterator = arrayList.listIterator();
12                     while (iterator.hasNext()) {
13                         System.out.println("thread1 " + iterator.next().intValue());
14                         try {
15                             Thread.sleep(100);
16                         } catch (InterruptedException e) {
17                             e.printStackTrace();
18                         }
19                     }
20                 }
21             }
22         });
23 
24         Thread thread2 = new Thread(new Runnable() {
25             @Override
26             public void run() {
27                 synchronized (arrayList) {
28                     ListIterator<Integer> iterator = arrayList.listIterator();
29                     while (iterator.hasNext()) {
30                         Integer integer = iterator.next();
31                         System.out.println("thread2 " + integer.intValue());
32                         if (integer.intValue() == 5) {
33                             iterator.remove();
34                         }
35                     }
36                 }
37             }
38         });
39         thread1.start();
40         thread2.start();
41     }

这种方案本质上是将多线程通过加锁来转变为单线程操作，确保同一时间内只有一个线程去使用iterator遍历arrayList，其它线程等待，效率显然是只有单线程的效率。

2.3.2 方案二：使用CopyOnWriteArrayList，有坑！要明白原理再用，否则你就呆坑里吧。

我们先来看代码，很有意思咯

 1     public void test6() {
 2         List<Integer> list = new CopyOnWriteArrayList<>();
 3         for (int i = 0; i < 20; i++) {
 4             list.add(Integer.valueOf(i));
 5         }
 6 
 7         Thread thread1 = new Thread(new Runnable() {
 8             @Override
 9             public void run() {
10                 ListIterator<Integer> iterator = list.listIterator();
11                 while (iterator.hasNext()) {
12                     System.out.println("thread1 " + iterator.next().intValue());
13                     try {
14                         Thread.sleep(1000);
15                     } catch (InterruptedException e) {
16                         e.printStackTrace();
17                     }
18                 }
19             }
20         });
21 
22         Thread thread2 = new Thread(new Runnable() {
23             @Override
24             public void run() {
25                 for (Integer integer : list) {
26                     System.out.println("thread2 " + integer.intValue());
27                     if (integer.intValue() == 5) {
28                         list.remove(integer);
29                     }
30                 }
31                 for (Integer integer : list) {
32                     System.out.println("thread2 again " + integer.intValue());
33                 }
34 //                ListIterator<Integer> iterator = list.listIterator();
35 //                while (iterator.hasNext()) {
36 //                    Integer integer = iterator.next();
37 //                    System.out.println("thread2 " + integer.intValue());
38 //                    if (integer.intValue() == 5) {
39 //                        iterator.remove();
40 //                    }
41 //                }
42             }
43         });
44         thread1.start();
45         thread2.start();
46     }

先不分析，看执行结果，这个执行结果重点关注字体加粗部分。

thread1 0
thread2 0
thread2 1
thread2 2
thread2 3
thread2 4
thread2 5
thread2 6
thread2 7
thread2 8
thread2 9
thread2 10
thread2 11
thread2 12
thread2 13
thread2 14
thread2 15
thread2 16
thread2 17
thread2 18
thread2 19
thread2 again 0
thread2 again 1
thread2 again 2
thread2 again 3
thread2 again 4
thread2 again 6
thread2 again 7
thread2 again 8
thread2 again 9
thread2 again 10
thread2 again 11
thread2 again 12
thread2 again 13
thread2 again 14
thread2 again 15
thread2 again 16
thread2 again 17
thread2 again 18
thread2 again 19
thread1 1
thread1 2
thread1 3
thread1 4
thread1 5
thread1 6
thread1 7
thread1 8
thread1 9
thread1 10
thread1 11
thread1 12
thread1 13
thread1 14
thread1 15
thread1 16
thread1 17
thread1 18
thread1 19

Process finished with exit code 0

我们先分析thread2的输出结果，第一次遍历将4 5 6都输出，情理之中；第一次遍历后删除掉了一个元素，第二次遍历输出4 6，符合我们的预期。

再来看下thread1的输出结果，有意思的事情来了，thread1 仍然输出了4 5 6，什么鬼？thread1和thread2都是遍历list，list在thread1遍历第二个元素的时候就已经删除了一个元素了，为啥还能输出5？

为了了解这个问题，需要了解CopyOnWriteArrayList是如何做到一边遍历的同时还能一边修改并且还不抛异常的。

在这里不想再深入分析CopyOnWriteArrayList代码，后续会专门出一篇博客来解释这个类的源码的。

这里说一下CopyOnWriteArrayList的解决思路，其实很简单：

1 private transient volatile Object[] array;

CopyOnWriteArrayList本质上是对array数组的一个封装，一旦CopyOnWriteArrayList对象发生任何的修改都会new一个新的Object[]数组newElement，在newElement数组上执行修改操作，修改完成后将newElement赋值给array数组（array=newElement）。

因为array是volatile的，因此它的修改对所有线程都可见。

了解了CopyOnWriteArrayList的实现思路之后，我们再来分析上面代码test6为什么会出现那样的输出结果。先来看下thread1和thread2中用到的两种遍历方式的源码：

 1     public void forEach(Consumer<? super E> action) {
 2         if (action == null) throw new NullPointerException();
 3         // 在遍历开始前获取当前数组
 4         Object[] elements = getArray();
 5         int len = elements.length;
 6         for (int i = 0; i < len; ++i) {
 7             @SuppressWarnings("unchecked") E e = (E) elements;
 8             action.accept(e);
 9         }
10     }

 

 1 public ListIterator<E> listIterator() {
 2         return new COWIterator<E>(getArray(), 0);
 3     }
 4     static final class COWIterator<E> implements ListIterator<E> {
 5         /** Snapshot of the array */
 6         private final Object[] snapshot;
 7         /** Index of element to be returned by subsequent call to next.  */
 8         private int cursor;
 9 
10         private COWIterator(Object[] elements, int initialCursor) {
11             cursor = initialCursor;
12             // 初始化为当前数组
13             snapshot = elements;
14         }
15 
16         public void remove() {
17             // 已经不支持Iterator remove操作了！！
18             throw new UnsupportedOperationException();
19         }
20 
21         public boolean hasNext() {
22             return cursor < snapshot.length;
23         }
24 
25         @SuppressWarnings("unchecked")
26         public E next() {
27             if (! hasNext())
28                 throw new NoSuchElementException();
29             return (E) snapshot[cursor++];
30         }
31 
32         // 此处省略其他无关代码
33     }

这两种遍历方式有个共同的特点：都在初始化的时候将当前数组保存下来了，之后的遍历都将会遍历这个数组，而不管array如何变化。

时间点	CopyOnWriteArrayList的array	thread1 iterator 初始化的Object数组	thread2 第一次遍历forEach初始化的Object数组	thread2 第二次遍历forEach初始化的Object数组
thread start	假设为A	A	A	/
thread2 调用remove方法之后	假设为B	A	A	B

 

 

 

有了这个时间节点表就很清楚了，thread1和thread2 start的时候都会将A数组初始化给自己的临时变量，之后遍历的也都是这个A数组，而不管CopyOnWriteArrayList中的array发生了什么变化。因此也就解释了thread1在thread2 remove掉一个元素之后为什么还会输出5了。在thread2中，第二次遍历初始化数组变成了当前的array，也就是修改后的B，因此不会有Integer.valueOf(5)这个元素了。

从test6执行结果来看，CopyOnWriteArrayList确实能解决一边遍历一边修改并且还不会抛异常，但是这也是有代价的：

(1) thread2对array数组的修改thread1并不能被动感知到，只能通过hashCode()方法去主动感知，否则就会一直使用修改前的数据

(2) 每次修改都需要重新new一个数组，并且将array数组数据拷贝到new出来的数组中，效率会大幅下降

此外CopyOnWriteArrayList中的ListIterator实现是不支持remove、add和set操作的，一旦调用就会抛出UnsupportedOperationException异常，因此test6注释代码34-41行中如果运行是会抛异常的。

参考文献： 

http://lz12366.iteye.com/blog/675016 

http://www.cnblogs.com/dolphin0520/p/3933551.html

http://blog.csdn.net/androiddevelop/article/details/21509345