迭代器源码解析
从运行以下(Java)代码说起:
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = iterator.next();
list.remove(integer);
}
以上代码运行时会抛出java.util.ConcurrentModificationException
运行时异常。
进入ArrayList的源码查看异常抛出时的条件:
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
/**
* modCount的数值表示list结构被修改的次数,包括会改变list的size大小的操作
*/
protected transient int modCount = 0;
同时expectedModCount是ArrayList实现的Iterator迭代器接口Itr中的属性,下面将剖析其迭代器实现类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,迭代器上次返回的元素位置标识
//期待的list重建次数,默认和上文中的modCount想等,当在迭代器迭代范围之外主动调用list.remove(), add()等方法后,
//改变了modCount的值,而itr.expectedModCount的值未随之改变,导致两值不相等时抛出java.util.ConcurrentModificationException异常
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//每次获取迭代器元素前,检查modCount和expectedModCount的值,避免同步更新list导致的问题
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;//游标位置增加1
return (E) elementData[lastRet = i];//为lastRet赋值
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//移除迭代器最近返回的元素,因为迭代器每次next()都更新了lastRet的值
ArrayList.this.remove(lastRet);
//将游标位置前移一格,因为在每次执行next()后游标位置自增了1,这里移除了迭代器的最后返回元素
//ArrayList.this.remove(lastRet)方法使list从lastRet+1 至 size-1位置的所有元素向前移动了一格,
//所以下次需要返回的游标位置为移除元素的位置,所以需要将游标位置置于lastRet的位置
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
下面分析一下ArrayList.this.remove(lastRet)
的具体实现:
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0){
//remove的具体操作,数组复制和移动
//将原数组从index+1到size-1的位置向前移动一个,并将size位置的值置为空
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
总结
遍历List过程中,对原List做删除操作
针对单线程的情况
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = iterator.next();
//因为迭代器的remove方法在方法内部每次重建list结构声明了modCount = expectedModCount
iterator.remove();
}
针对多线程情况
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
Thread thread1 = new Thread(){
public void run() {
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = iterator.next();
iterator.remove();
}
};
};
Thread thread2 = new Thread(){
public void run() {
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = iterator.next();
iterator.remove();
}
};
};
上面的代码虽然使用了迭代器的remove方法来改变list结构,但是通过上面的源码分析我们得知remove方法内部并非线程安全的,多线程同时remove时仍可能导致java.util.ConcurrentModificationException
。
所以应尽量避免多线程同步更新ArrayList,当然也可以通过加锁synchronized的方式来保证同步更新的正常运行。