Java 迭代器的Fast-Fail机制

Java

报数的时候不能乱动

有这样一个需求，如果集合里存在符合某个条件的元素就删除它们

错误实现

这样可能会写出循环，在循环内调用集合的删除方法

Sample
1
2
3
4
5
6
7
8
9
10
Map<String, String> map = new HashMap<>();
map.put("foo", "foo");
map.put("bar", "bar");
map.put("baz", "baz");

for (String key : map.keySet()) {
    if (key.equals("bar")) {
        map.remove("bar");
    }
}

然而不幸的是，上述代码会报出java.util.ConcurrentModificationException

原因

究其原因，是因为Iterator才用了Fast-Fail的机制，防止并发修改。集合内部维护了一个名为modCount的计数变量，每当对集合进行结构性操作比如增删时，变量都会自增。

迭代器构造函数中，将建立时的modCount进行了保存，进行next操作会检查modCount是否保持不变。直接调用集合的remove方法时，迭代器并不知情，导致了modCount发生不一致。

HashMap.java
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
abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        //...
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        //...
        if (modCount != expectedModCount)  //检查modCount
            throw new ConcurrentModificationException();
        //...
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)  //检查modCount
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;  //修改modCount期望值
    }
}

正确实现

迭代器自身提供的remove方法在删除后维护了modCount，所以正确的方式是调用迭代器提供的方法进行删除

Sample
1
2
3
4
5
6
7
8
9
10
11
12
Map<String, String> map = new HashMap<>();
map.put("foo", "foo");
map.put("bar", "bar");
map.put("baz", "baz");

Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    String key = iterator.next();
    if (key.equals("bar")) {
        iterator.remove();
    }
}

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2017/11/10/java-iterator-modify/