劳伦的奇妙冒险


客亦知夫水与月乎?

哀吾生之须臾,
羡长江之无穷。

Java迭代器:fail-fast与fail-safe

原文地址:Fail fast and fail safe iterators in Java
作者:mridul09



译者总结

一个数据集(Collection),我们可以对其进行静态的访问 get 或动态的操作 add, remove;但是当这两种操作同时发生时,则可能发生意外。例如线程t1在遍历集合的同时,线程t2在对集合进行增删元素;或是同一线程在遍历集合的同时增删数据。

不同迭代器在应对该情况时有不同的表现,以此为标准分为 fail-fastnon-fail-fast(文中称为 fail-safe)。前者不允许迭代的过程中对列表进行增删操作,表现为抛出 ConcurrentModificationException,后者则允许该种操作。

此处需要强调的是“增删操作”指的是对集合自身的直接操作,而非迭代器的 remove.


原文

我会在文中解释不以 fail-fast 方式进行迭代的集合类行为。首先需要明确的是,fail-safe 这个在很多技术文章中出现过的术语实际上没有出现在 Java SE 规范中,因此这并不是一个官方说法。但在本文中,我还是会沿用 fail-safe 来表示 非fail-fast 的迭代器。

同步修改:编程中的同步修改意味着,在修改一个对象的同时,还有其他基于该对象的任务在执行。例如有不同的线程同时对同一集合类的对象进行遍历和修改。部分迭代器的实现(包括 JRE 提供的通用迭代器)在检测到这种同时修改和遍历的行为时,可能会选择抛出 ConcurrentModificationException 异常。


1. Fail Fast 与 Fail Safe

Java 中的迭代器就是为了遍历集合类的对象。Fail-Fast 迭代器会在检测到集合对象发生了结构性修改时立即抛出 ConcurrentModificationException。结构性修改指的是当其他线程在遍历集合对象的元素时,对该集合对象进行添加、删除或更新元素的操作。ArrayList, HashMap 返回的迭代器就是 fail-fast 的例子。

Fail-Safe 迭代器在执行遍历的同时,当集合对象发生结构性修改时不会抛出任何异常。这是因为迭代器执行的操作,如遍历、添加或删除等,均基于原集合类对象内部元素的复制,并非原集合类对象的内部元素。也就是说,对原集合类对象的修改不会影响迭代器中的元素。这就是 Fail-Safe 术语的由来。CopyOnWriteArrayList 的迭代器就是这种类型。

2. Fail Fast 迭代器的工作原理

为了知道集合类对象是否发生了结构性修改,fail-fast 迭代器使用一个名为modCount 的内部标识,该标识会在集合类对象被修改时进行更新。Fail-Fast 迭代器在实例化后,当获取下一个元素时(如调用 next())发现原集合对象的 modCount 已被修改,就会抛出 ConcurrentModificationException.

Fail Fast 迭代器示例

import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map; 

public class FailFastExample { 
    public static void main(String[] args) 
    { 
        Map<String, String> cityCode = new HashMap<String, String>(); 
        cityCode.put("Delhi", "India"); 
        cityCode.put("Moscow", "Russia"); 
        cityCode.put("New York", "USA");  // 此时 HashMap 对象的 modCount=3

        // 返回 Iterator 对象时,会使用字段 expectedModCount 记录当前 HashMap 对象的 modCount
        Iterator iterator = cityCode.keySet().iterator(); 

        while (iterator.hasNext()) { 
            // 每次调用 iterator.next() 时都会检查 expectedModCount 是否与 modCount 相等,若不等则抛出 ConcurrentModificationException
            System.out.println(cityCode.get(iterator.next()));

            // 往 Map 对象添加元素,迭代器在下一次调用 next() 时会抛出异常
            cityCode.put("Istanbul", "Turkey"); 
        } 
    } 
} 

输出:

India
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1442)
    at java.util.HashMap$KeyIterator.next(HashMap.java:1466)
    at FailFastExample.main(FailFastExample.java:18)

Fail Fast 迭代器的几个关键点:

  • 遍历时一旦发现原集合对象发生修改则会抛出 ConcurrentModificationException.
  • 被遍历的是原集合对象的元素。
  • 这类迭代器不需要额外内存空间。
  • 如:ArrayList, Vector, HashMap 返回的迭代器

注意点1(来自 java-docs): 一般而言,当并发操作没有同步时(即该类迭代器在 ArrayListHashMap 等非线程安全类中使用时),由于无法严格保证程序的正确性,fail-fast 迭代器选择抛出 ConcurrentModificationException 作为一个保底操作。因此基于 fail-fast 抛出异常的行为来编写程序是错误的,该行为只应该用来检测程序是否有 bug.

注意点2:使用迭代器的 remove() 方法不会抛出异常,但是使用它对应的集合类对象的 remove() 将会抛出异常。参考下列代码片段:

Fail Fast 迭代器示例

import java.util.ArrayList; 
import java.util.Iterator; 

public class FailFastExample { 
    public static void main(String[] args) 
    { 
        ArrayList<Integer> al = new ArrayList<>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(4); 
        al.add(5); 

        Iterator<Integer> itr = al.iterator(); 
        while (itr.hasNext()) { 
            if (itr.next() == 2) { 
                // 调用迭代器的 remove() 不会抛出异常
                itr.remove(); 
            } 
        } 

        System.out.println(al); 

        itr = al.iterator(); 
        while (itr.hasNext()) { 
            if (itr.next() == 3) { // 迭代器的 next() 方法会检查 expectedModCount 是否与 modCount 相等,不相等则抛出异常
                al.remove(3);  // 集合类对象的 remove() 方法不会抛出异常,但是会修改 modCount
            } 
        } 
    } 
} 

输出:

[1, 3, 4, 5]
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at FailFastExample.main(FailFastExample.java:28)

3. Fail Safe 迭代器

首先,在很多技术文章中出现的 fail-safe, 实际上并没有出现在 Java SE 规范中。在这里我使用该词来表明与 fail-fast 相对应的迭代器。该类迭代器在实例化的同时会创建集合类对象内部元素的镜像(即拷贝集合类对象的内部对象数组),并对该镜像进行遍历。任何对迭代器的结构性修改影响的是镜像数组,而非原集合对象的元素数组,因此原集合对象的元素保持不变(即原集合对象对元素的修改与迭代器中元素的修改互不影响)。

Fail Safe 迭代器的几个关键点

  • 允许在进行迭代时对原集合对象的元素进行修改。
  • 在遍历的同时修改集合对象的元素,不会抛出任何异常。
  • 遍历的是原集合类对象元素的拷贝。
  • 需要额外的内存空间用于拷贝的元素数组。
  • ConcurrentHashMap, CopyOnWriteArrayList 等使用了该类迭代器。

Fail Safe 迭代器示例

import java.util.concurrent.CopyOnWriteArrayList; 
import java.util.Iterator; 

class FailSafe { 
    public static void main(String args[]) 
    { 
        CopyOnWriteArrayList<Integer> list 
            = new CopyOnWriteArrayList<Integer>(new Integer[] { 1, 3, 5, 8 }); 
        Iterator itr = list.iterator(); 
        while (itr.hasNext()) { 
            Integer no = (Integer)itr.next(); 
            System.out.println(no); 
            if (no == 8) 
                // 14不会被打印,因为迭代器遍历的是原集合对象内部元素的拷贝
                list.add(14); 
        } 
    } 
} 

输出:

1
3
5
8

同样地,没有使用 fail-fast 概念的迭代器也不一定要对原集合对象的内部元素创建拷贝或快照以避免 ConcurrentModificationException. 例如在 ConcurrentHashMap 中的迭代器,既非 fail-fast,也没有在内部元素的拷贝上进行操作。相反,这种迭代器是通过官方文档从语义上定义为 weakly consistent.(Java 的内存一致性属性)

不开辟新空间的 Fail Safe 迭代器

import java.util.concurrent.ConcurrentHashMap; 
import java.util.Iterator; 

public class FailSafeItr { 
    public static void main(String[] args) 
    { 

        // 创建 ConcurrentHashMap 对象
        ConcurrentHashMap<String, Integer> map 
            = new ConcurrentHashMap<String, Integer>(); 

        map.put("ONE", 1); 
        map.put("TWO", 2); 
        map.put("THREE", 3); 
        map.put("FOUR", 4); 

        // 从集合对象中创建迭代器
        Iterator it = map.keySet().iterator(); 

        while (it.hasNext()) { 
            String key = (String)it.next(); 
            System.out.println(key + " : " + map.get(key)); 

            // 7会被打印,即对原集合元素的修改会在迭代器中反映出来,因此没有额外的拷贝空间
            map.put("SEVEN", 7); 
        } 
    } 
} 

输出:

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

注意点1(来自Java文档):ConcurrentHashMap返回的迭代器为 weakly consistent。 这意味着在迭代器创建后,对集合对象的元素进行的并发修改操作,可以反映在迭代器的遍历过程中(但是并不保证能成功)。

4.Fail Fast 与 Fail Safe 的区别

主要的区别是 fail-safe 迭代器不会抛出任何异常(与 fail-fast 迭代器相反)。这是由于它们操作的对象是原集合对象元素的拷贝,这也是 fail-safe 称谓的由来。

最近的文章

十种基础排序算法

1. 比较排序 1.1 选择排序 1.2 冒泡排序 1.3 归并排序 1.4 快速排序 算法过程 渐进复杂度 示例代码 退化的情况 与归并排序比较 总结 1.5 插入排序 1.6 希尔排序 1.7 堆排序 2. 非比较排序 2....…

algorthm sorting继续阅读