今天在做算法题的时候，碰到的如下问题，记录下来加深记忆。很多时候我们都有这样一个需求，在迭代的时候（满足某个给定的条件）添加或者删除元素。结果却是等来了java.util.ConcurrentModificationException这个异常，追踪其原因，就是有些容器是Fail-Safe，Fail-First的。出现异常的代码如下：
public class CollectionTest {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
for (int a : arrayList) {
if (a == 1)
arrayList.remove(a);
}
System.out.println(arrayList);
}
}
1. Fail-Safe,Fail-First概念。
在ArrayList的里面有个内部类Itr。当我们获取到迭代器的时候，就会对这个类进行初始化，来看下这个类的源码，分析初始化做了些什么。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
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();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在初始化的时候，它会让expectedModCount = modCount，modCount在AbstractList，每次对ArrayList的结构性改变（remove,add）都会使得modCount相应的减1或者加1。来分析下我们刚开始出现问题的代码。当我们获取到迭代器的时候，此时expectedModCount = modCount。当remove的时候，modCount会加1，但是expectedModCount却不变，当执行Itr的next()操作时候，会执行上述源码中的checkForComodification()来检查expectedModCount = modCount，若不相等，则会throw ConcurrentModificationException。
所以就不难分析出上述问题。
FailFirst:当我们在迭代获取集合元素的时候，在迭代器创建之后，对集合做一些结构性的改变（remove,add操作)，那么FailFirst容器首先会抛出 ConcurrentModificationException。
2. 如何解决上述问题。
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
ArrayList sub=new ArrayList();
for(int a:arrayList){
if(a==1)
sub.add(a);
}
arrayList.removeAll(sub);
System.out.println(arrayList);
}
上述这个办法好，但是却占额外空间。
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
int a = iterator.next();
if (a == 1)
iterator.remove();
}
System.out.println(arrayList);
}
这样就不占额外的空间，是更好的办法。 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();
}
}
expectedModCount = modCount;这句起作用，它删除元素后它会强制满足条件。所以不会抛异常。
3. Fail-First的出场 。
将刚开始的代码换成如下的形式,问题迎刃而解。
public static void main(String[] args) {
CopyOnWriteArrayList<Integer> arrayList = new CopyOnWriteArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
int a = iterator.next();
if (a == 1)
arrayList.remove(a);
}
System.out.println(arrayList);
}
像CopyOnWriteArrayList这类容器就属于Fail-Safe容器。当集合结构改变的时候不会抛出异常，这是因为他们只是原始集合的复制，它用snapshot这个数组来保存集合。所以你原始集合的修改只会让原来的引用指向新的数组，而旧的引用还是被迭代器的snapshot所引用。因而他们属于Fail-Safe容器。看看其源码
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
private boolean remove(Object o, Object[] snapshot, int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) findIndex: {
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
if (current[i] != snapshot[i] && eq(o, current[i])) {
index = i;
break findIndex;
}
}
if (index >= len)
return false;
if (current[index] == o)
break findIndex;
index = indexOf(o, current, index, len);
if (index < 0)
return false;
}
Object[] newElements = new Object[len - 1];
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index + 1,
newElements, index,
len - index - 1);
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
从上面可以看出每次添加元素都是线程安全的，因为加了锁。另外，每添加一个元素，都会把原来的引用指向一个新的数组。所以对他进行操作没问题。所以使用Fail-Safe容器也是一种很好的解决办法。
网友评论