Fork me on GitHub

Java的艺术-Java容器(2)之并发修改异常

此处输入图片的描述
ConcurrentModificationException(并发修改异常)为什么会出现?怎么解决呢?

什么时候出现“并发修改异常”?

看下面这两段代码

(1)增强for

1
2
3
4
5
6
7
8
ArrayList<String> res = new ArrayList<>();
res.add("a");
res.add("b");
for (String s:res){
if(s=="a"){
res.add("c");
}
}

(2)迭代器

1
2
3
4
5
6
7
8
9
10
ArrayList<String> res = new ArrayList<>();
res.add("a");
res.add("b");
Iterator it = res.iterator();
while(it.hasNext()){
String s =(String) it.next();
if(s == "a"){
res.add("c");
}
}

上面的代码都会出现下面的异常:

1
2
3
4
5
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 offer.Solution38.Permutation(Solution38.java:25)
at offer.Solution38.main(Solution38.java:35)

为什么会出现“并发修改异常”?

源码分析

首先我们看ArrayList类的源码,其iterator()方法为:

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

返回一个新建的Itr对象,源码如下:

1
Itr() {}

是个没有内容内部类,我们只能看看ArrayList的父类AbstractList有没有对应的内容:

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
private class Itr implements Iterator<E> {
/**
* Index of element to be returned by subsequent call to next.
*/
int cursor = 0;

/**
* Index of element returned by most recent call to next or
* previous. Reset to -1 if this element is deleted by a call
* to remove.
*/
int lastRet = -1;

/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;

public boolean hasNext() {
return cursor != size();
}

public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}

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

是一个实现了Iterator接口的私有内部类。

分析它的hasNext()方法,会发现一个成员变量cursor。分析发现,这个变量表示下一个要访问元素的索引,当索引大于集合的size()后,则hasNext()=false。并且,next()方法返回的元素调用了get(cursor),而get()方法在ArrayList中为:

1
2
3
4
public E get(int index) {
rangeCheck(index);
return elementData(index);
}

elementData就是用来存储ArrayList的Object数组。

什么时候会出现ConcurrentModificationException呢?

我们发现了Itr类的两个方法remove()和checkForComodification()会抛出这个异常:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}

以及

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

我们观察上面抛出异常的代码:

1
2
3
4
5
6
7
8
9
10
ArrayList<String> res = new ArrayList<>();
res.add("a");
res.add("b");
Iterator it = res.iterator();
while(it.hasNext()){
String s =(String) it.next();
if(s == "a"){
res.add("c");
}
}

首先在next()方法中会调用checkForComodification()方法,然后根据cursor的值获取到元素,接着将cursor的值赋给lastRet,并对cursor的值进行加1操作。初始时,cursor为0,lastRet为-1,那么调用一次之后,cursor的值为1,lastRet的值为0。注意此时,modCount为0,expectedModCount也为0

随后,代码调用了res.add(“c”)。

查看源码,ArrayList的add()方法如下:

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

再查看ensureCapacityInternal()的源码:

1
2
3
4
5
6
7
8
9
10
11
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

我们发现了关键一行:

1
modCount++;

此时,modCount为1,expectedModCount为0

在调用next()方法时,执行checkForComodification()显然就会抛出ConcurrentModificationException()

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

终于解决了这个疑惑!

结论

分析源码,在多线程程序中,如果有多个线程都在使用一个集合对象X,线程继续迭代,当A线程调用迭代器的next()方法时,发现modCount不等于expectedModCount,因此就抛出了ConcurrentModificationException异常。这可能就是它为什么叫并发修改异常的原因。从这一点也能说明ArrayList不是线程安全的。

简单来说,调用list.remove(),list.add()方法导致modCount和expectedModCount的值不一致。使用for-each进行迭代实际上也会出现这种问题。

解决办法

一般有2种解决办法:

(1)不使用迭代器遍历集合,就可以在遍历的时候使用集合的方法进行增加或删除

1
2
3
4
5
6
7
8
9
ArrayList<String> res = new ArrayList<>();
res.add("a");
res.add("b");
for (int i = 0; i < res.size(); i++) {
if(res.get(i) == "a")
res.add("c");
}
System.out.println(res);
return res;

(2)依然使用迭代器遍历,那么就需要使用Iterator的子接口ListIterator来实现向集合中添加

1
2
3
4
5
6
7
ListIterator lit = res.listIterator();
while(lit.hasNext()) {
String s = (String)lit.next();
if(s.equals("a")) {
lit.add("c");
}
}

其他解决同步问题的办法:

(3)在使用iterator迭代的时候使用synchronized或者Lock进行同步;

(4)使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

-------------本文结束感谢阅读-------------