浅析ConcurrentModificationException出现的原因。
写在开篇
ConcurrentModificationException，也就是并发修改异常，当我们使用一些Java集合类时，有时需要遍历集合并根据条件remove其中的元素，此时就有可能出现该异常。
接下来我们通过下面这个例子来分析一下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class Solution {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
for (Integer i : list) {
System.out.println(i);
if (i == 2)
list.remove(i);
}
}
}
上图中我们可以看到，在程序输出“3”之前出现了ConcurrentModificationException，也就是说，异常是在遍历下一个元素时抛出的。也就是，删除和遍历产生了冲突。
从ArrayList内部看异常出现的原因
ArrayList的遍历
在例子中使用了foreach遍历元素，实际上，foreach遍历的原理就是使用Iterator进行迭代，可以通过javap进行反编译即可查看到相关的字节码指令（看64行的注释）：1
2
3
4
5
6
7
8
9
10
11
12......
54: invokestatic #19 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
57: invokeinterface #25, 2 // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
62: pop
63: aload_1
64: invokeinterface #31, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
69: astore_3
70: goto 106
73: aload_3
74: invokeinterface #35, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
79: checkcast #20 // class java/lang/Integer
......
这是因为集合类所实现的Collection接口继承了Iterable这个接口，因此都能够使用foreach的方式遍历。在ArrayList所实现的iterator方法中，返回的是ArrayList的内部类Itr。在Itr实现的next方法中，会先判断modCount和expectedModCount两个值是否相等，改变记录下标cursor和lastRet的值，从0下标开始返回ArrayList内部数组的值。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
44public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
protected int limit = ArrayList.this.size;
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; // modCount是AbstractList的成员变量，表示对List的修改次数
public boolean hasNext() {
return cursor < limit;
}
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
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() {
if (lastRet < 0)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
ArrayList的删除
在next方法中，首先会判断两个表示修改次数的值是否相等，一次来自List的修改，一次来自Iterator的修改，如果不同就抛出ConcurrentModificationException。
接着看下ArrayList的remove()：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public 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++;
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方法删除元素最终是调用的fastRemove()，改变modCount的值，然后通过调用arraycopy把index后的所有元素都往前移动，然后size-1。
真相大白
回到例子中，代码list.remove(bean)对List进行了一次修改，那么modCount+1，但没有同步到Itr中的expectedModCount。因此，在list.remove(bean)后，iterator调用next()访问下一个元素时，就会导致modCount != expectedModCount，抛出异常。但是，在Itr的remove方法的实现中，每次操作都会把modCount同步到expectedModCount，这样，就不会抛出异常了。因此，正确的遍历删除如下：1
2
3
4
5
6
7Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer i = iterator.next();
System.out.println(i);
if (i == 2)
iterator.remove();
}
另一种情况
如果改变删除的元素为倒数第二个，就是 i = 3 时：1
2
3
4
5for (Integer i : list) {
System.out.println(i);
if (i == 3)
list.remove(i);
}
运行结果：
程序没有抛出ConcurrentModificationException，但是在打印“4”之前程序就结束了，这是为什么呢？
因为List在删除元素后会减小记录自身元素个数的值，也就是size从5变为了4，而此时，遍历访问的下标由3来到了4，也就是访问i = 3的下标向后移了。Itr的hasNext()此时判断，List已经没有元素可以访问了，于是返回了false。
多线程下的解决方案
上面我们已经给出了单线程环境下的解决方案，不过它在多线程下适用吗，我们一起来看看下面这个例子：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
38public class Solution {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
Thread thread1 = new Thread(){
public void run() {
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
System.out.println(integer);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
};
Thread thread2 = new Thread(){
public void run() {
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
if(integer==2)
iterator.remove();
}
};
};
thread1.start();
thread2.start();
}
}
运行结果：
可能有人说ArrayList是非线程安全的容器，换成Vector就没问题了，实际上换成Vector还是会出现这种错误。
原因在于，虽然Vector的方法采用了synchronized进行了同步，但是实际上通过Iterator访问的情况下，每个线程里面返回的是不同的iterator，也即是说expectedModCount是每个线程私有。假若此时有2个线程，线程1在进行遍历，线程2在进行修改，那么很有可能导致线程2修改后导致Vector中的modCount自增了，线程2的expectedModCount也自增了，但是线程1的expectedModCount没有自增，此时线程1遍历时就会出现expectedModCount不等于modCount的情况了。
因此一般有2种解决办法：
- 在使用iterator迭代的时候使用synchronized或者Lock进行同步
- 使用并发容器CopyOnWriteArrayList代替ArrayList和Vector
