HashMap 等集合中的快速失败机制（fast-fail）

缘起

我们知道遍历HashMap的时候，或者使用迭代器遍历ArrayList等集合的时候，是不能直接调用集合的API对集合元素进行删除或者新增元素（而不是覆盖，覆盖不会导致异常）操作的. 否则的话，会抛出ConcurrentModificationException. 这是为什么呢? 其实这个和所谓的 快速失败机制（Fast-Fail）有关.

分析

先上一段熟悉的代码

1
2
3
4
5
6
7
8
9
10
11
public Map<Double, Double> processMap(Map<Double, Double> list) {
	Map<Double, Double> map = list;
	Iterator<Double> iter = map.keyset().iterator;
	while(iter.hasNext()) {
        double key = iter.next();
        if (key > 5)
            map.remove(key);
        } 
	}
        return map;
}

调用此接口的话，将会抛出 java.util.ConcurrentModificationException异常. 而并没有删除元素.

书上一般告诉我们要像下面这样使用迭代器来删除元素

1
2
3
4
5
6
7
8
9
10
11
public Map<Double, Double> processMap(Map<Double, Double> list) {
    Map<Double, Double> map = list;
    Iterator<Double> iter = map.keyset().iterator;
    while(iter.hasNext()) {
        double key = iter.next();
        if (key > 5) {
            iter.remove(key); // OK
    	} 
    } 
    return map;
}

原因是HashMap使用迭代器遍历元素, HashMap的keyset的iterator跟一下源码不难知道是HashIterator的子类KeyIterator. 而HashIterator的nextNode方法

1
2
3
4
5
6
7
8
9
10
11
12
final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

看到了 ConcurrentModificationException 了么? 就是 modCount != expectedModCount的时候就会抛出此异常. 而HashIterator的构造器是

1
2
3
4
5
6
7
8
9
HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

可以看见，expectedModCount伊始是等于modCount（注意，modCount是HashMap的属性）的. 但是为什么遍历的途中不等了呢? 嗯，显然就是对HashMap 进行增删的时候（注意，不包括改，具体原因可以参见【1】）变化了HashMap的结构，会导致modCount变化（就是+1，分析见【1】）. 从而导致迭代的时候抛出异常. 这种抛出异常的机制叫做快速失败（fast-fail）. 目的是JDK的设计者希望遍历HashMap的时候不要修改HashMap. 如果实在是想修改的话（毕竟也有这种需求），则应该使用迭代器的接口方法进行删除等操作. 因为HashIterator的remove的源码如下

1
2
3
4
5
6
7
8
9
10
11
public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }

注意最后一行——发现了没有? 使用迭代器移除元素会同步更新expectedModCount，所以下一次nextNode方法的时候不会快速失败.

上面仅就HashMap的fast-fail机制做了分析. 对于ArrayList 也是一样的.

参考

【1】https://yfsyfs.github.io/2019/06/07/java-util-HashMap-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/