Iterator迭代器

ConcurrentModificationException异常

List<String> strings = new ArrayList<String>();
Iterator<String> iterator = strings.iterator();

// 添加元素
// strings.add("...")
// ...

while(iterator.hasNext()){
    System.out.println(iterator.next());
}

错误信息：

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)

分析异常

  问题出现在两个方法上:checkForComodification()和next()，后者是我在程序中调用的方法，前者之前没见过，我决定从头开始查找源码问题。

创造迭代器

  例子中通过strings.iterator()返回一个迭代器，其中strings是一个ArrayList的实例。
  查找ArrayList的源码，并没有iterator()方法，于是找到其父类AbstractList中:

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

也就是说创造一个迭代器返回的是一个Itr类型对象的引用。
  来看Itr:

private class Itr implements Iterator<E> {
    
    int cursor = 0;
  
    int lastRet = -1;

    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();
    }
}

其中的成员变量：
cursor: 游标，表示下一个要访问的元素的索引，在next方法中会自增
lastRet: 上一个元素的索引
expectedModCount: 表示对ArrayList修改次数的期望值，初始值为modCount
modCount: AbstractList类中的一个成员变量，表示对List的修改次数(structurally modified)，每次add()和remove()就会加1

解决错误

在Itr的源码中可以看到，迭代器中的操作都要先执行checkForComodificatioin()方法来确定modCount!=expectedModCount,这是保护ArrayList的机制，防止返回错误结果。

错误的原因可能在于创建迭代器之后添加元素也算是产生了结构性的变化。

Q. What is the difference between fail-fast and fail-safe iterator?

fail-fast Iterator

Iterators in java are used to iterate over the Collection objects.Fail-Fast iterators immediately throw ConcurrentModificationException if there is structural modification of the collection. Structural modification means adding, removing or updating any element from collection while a thread is iterating over that collection. Iterator on ArrayList, HashMap classes are some examples of fail-fast Iterator.

import java.util.ArrayList;
import java.util.Iterator;
 
public class FailFastIteratorExample 
{       
    public static void main(String[] args) {

        //Creating an ArrayList of integers
        ArrayList<Integer> list = new ArrayList<Integer>();
         
        //Adding elements to list
        list.add(1452);
        list.add(6854);
        list.add(8741);
                 
        //Getting an Iterator from list
        Iterator<Integer> it = list.iterator();
         
        while (it.hasNext()) {
            Integer integer = (Integer) it.next();
            list.add(8457);      //This will throw ConcurrentModificationException
        }
    }   
}

Output

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
    at java.util.ArrayList$Itr.next(Unknown Source)
    at pack1.MainClass.main(MainClass.java:32)

fail-safe Iterator

Fail-Safe iterators don’t throw any exceptions if a collection is structurally modified while iterating over it. This is because, they operate on the clone of the collection, not on the original collection and that’s why they are called fail-safe iterators. Iterator on CopyOnWriteArrayList, ConcurrentHashMap classes are examples of fail-safe Iterator.

import java.util.Iterator;
import java.util.concurrent.ConcurrentHashMap;
 
public class FailSafeIteratorExample 
{       
    public static void main(String[] args) {

        //Creating a ConcurrentHashMap
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<String, Integer>();
         
        //Adding elements to map
        map.put("ONE", 1);
        map.put("TWO", 2);
        map.put("THREE", 3);
         
        //Getting an Iterator from map
        Iterator<String> it = map.keySet().iterator();
         
        while (it.hasNext()) {
            String key = (String) it.next();
            System.out.println(key+" : "+map.get(key));
            map.put("FOUR", 4); //This will not be reflected in the Iterator
        }
    }   
}

Output

TWO : 2
FOUR : 4
ONE : 1
THREE : 3

↥ back to top