Collection下如List、Set等是我们常用的数据结构,良好的使用这些结构和提供的工具类,能帮助我们极大的提高开发效率。比如其中基于迭代器模式所实现的Iterator和封装的foreach是比较常用的遍历神器。
但是在实际使用iterator和foreach的开发过程中,有时候会遇到一些ConcurrentModificationException的错误,可能会造成不熟悉这些数据结构的同学觉得比较迷惑。而有时候,虽然清楚会存在这种潜在的问题,但是总是忘记哪种方式才是安全的。因此这里做一个小结,避免出现遗忘的时候又要重新看源码的情况。
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at com.company.Main.singleThreadDeleteFail(Main.java:69)
at com.company.Main.main(Main.java:40)
总的来说,fast-fail的发生只会发生在迭代期间做出了数据修改的情况下(因为Collection下的数据结构情况都差不多,就没有每个都去细细分析了,这里仅以ArrayList为例,如果其它Set之类的结构有差异化的地方,需要自己多注意下):
分类 | 方法 | fast-fail问题 | 线程安全 |
---|---|---|---|
foreach | ArrayList.remove | yes | no |
Iterator | ArrayList.remove | yes | no |
Iterator | Iterator.remove | no | no |
CopyOnWriteArrayList | ArrayList.remove | no | depends |
CopyOnWriteArrayList | Iterator.remove | not support | not support |
synchronizedList | ArrayList.remove | yes | yes |
synchronizedList | Iterator.remove | no | no |
下面我们根据每种情况的源码,来具体分析以下:
foreach
foreach的功能在实际使用种应该是最常见的,因为确实十分方便而且代码会变得十分简洁和清晰。因为foreach本身内部不会有再次使用iterator的情况,因此我们仅考虑ArrayList自身的remove情况。
我们重点关注以下代码,从中可以发现在foreach的循环过程中,一旦检测到modCount和expectedModCount不一致就会导致遍历中断,且抛出ConcurrentModificationException。而之所以modCount和expectedModCount会不一致就是因为数据结构自身的Remove等方法会改变起ModCount值:
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
// 犯人就是你!
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
public E remove(int index) {
rangeCheck(index);
// 凶器和犯罪动机在这里!
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
iterator
iterator在这种需要一边遍历一边修改的场景下,应该就是最推荐的实现方式了,因为其Iterator.Remove方法不仅不会造成Fast-fail问题,而且实现起来也简单。但是值得注意的是,在使用Iterator的场景下,直接使用ArrayList的remove方法也是不行的(会抛出ConcurrentModificationException),原因如下,在Iterator的Remove方法中,会设置expectedModCount = modCount从而造成了不会抛出异常:
// ArrayList自身的remove方法
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
// Iterator提供的remove方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 犯人就是你!
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
CopyOnWriteArrayList
网上很多的资料里面都推荐使用CopyOnWriteArrayList的方式来解决Fast-fail问题,诚然这是没有问题的,透过CopyOnWriteArrayList的原理我们发现,其实质是通过不断的拷贝数组来最终实现了所有的Remove和Add等方法,自然前后两个ArrayList已经不是同一个对象了(而是互相独立的两个对象),自然修改也不会带来Fast-fail问题,而且在这种修改过程中通过ReentrantLock来保证了复制和修改的原子性。这种实现且不论空间和时间的多余消耗,会给人一种是多线程安全的错觉,因为确实他是线程安全的,但是问题是两个线程操作的完全可能是不同的两个对象(也因此线程安全一项里面我觉得应该给出depands的结果)。也大概可以看一下其代码实现,copy是关键所在:
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();
}
}
还有个值得注意的问题是,因为CopyOnWriteArrayList是不支持Iterator的Remove方法的,所以这个乱用是要抛出异常的(具体代码就不贴了)
synchronizedList
最后想说一下synchronizedList这个这个数据结构。它和ArrayList本身的实现其实完全是一致的,只是在实现中加入了sychronised关键字保证其线程安全性。
但是需要特别注意的是,如果使用Iterator需要自己来保证线程安全。这一点比较容易忽略掉。
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}
结语
其实仔细品味一下fast-fail设计,可以感受到作者在考虑到尽量保护数据一致性和避免一些不可预期的错误的初衷,也对我们的具体使用会有很大的帮助来避免一些比较难以察觉到的问题。
越过这种机制本身会给我们具体的编码中带来一些问题,就更需要我们充分的明白其中的原理和缺陷,做到更好的掌控代码的质量,不要掉到深坑里面。
Anyway,enjoy~ : )