一、前言
在 Java 的集合结构中,如果我们同时进行遍历(for-each, iterator)和集合修改(add, set, remove…)操作时,就有可能发生异常。例如,线程 T1 在对集合进行遍历,而此时线程 T2 对集合进行添加元素;亦或者线程 T1 在对集合进行遍历的过程中,进行删除元素操作。
不同的集合在遇到上述这种情况时,会有不同的处理。按照处理的不同,划分为 Fail-Fast 和 Non-Fail-Fast(下文统称为 Fail-Safe)两类。前者不允许在迭代的过程中对集合进行增删操作,否则抛出 ConcurrentModificationException
异常;后者则允许这种操作,不会抛出异常。
注:本处的“对集合进行增删操作”指的是对集合自身的操作,而非借助 iterator 的操作。
二、Fail-Fast
Fail-Fast
类型的数据结构,在进行迭代时如果检测到集合对象发生了结构性修改 会立即抛出 ConcurrentModificationException
,结构性修改指的是对该集合对象进行添加、删除或更新元素的操作。ArrayList
, HashMap
返回的迭代器就是典型的 Fail-Fast。
2.1 样例展示
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import java.util.*;public class FailFastExample { public static void main (String[] args) { Map<String, String> cityCode = new HashMap<>(); cityCode.put("Delhi" , "India" ); cityCode.put("Moscow" , "Russia" ); cityCode.put("New York" , "USA" ); Iterator<String> iterator = cityCode.keySet().iterator(); while (iterator.hasNext()) { System.out.println(cityCode.get(iterator.next())); cityCode.put("Istanbul" , "Turkey" ); } } }
代码运行后输出如下结果:
1 2 3 4 5 India Exception in thread "main" java.util.ConcurrentModificationException at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445 ) at java.util.HashMap$KeyIterator.next(HashMap.java:1469 ) at com.example.demo.FailFastExample.main(FailFastExample.java:12 )
这与 Iterator 自身无关,使用传统的 For-Each 改写也会得到一样的输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 public class FailFastExample { public static void main (String[] args) { Map<String, String> cityCode = new HashMap<>(); cityCode.put("Delhi" , "India" ); cityCode.put("Moscow" , "Russia" ); cityCode.put("New York" , "USA" ); for (String s : cityCode.keySet()) { System.out.println(cityCode.get(s)); cityCode.put("Istanbul" , "Turkey" ); } } }
2.2 工作原理
支持 Fail-Fast 的集合,内部往往会有一个名为 modCount
的字段,该字段会在集合内元素被修改时进行更新。在遍历的过程中,如果发现 modCount
的值被修改,就会抛出 ConcurrentModificationException
。以 ArrayList#forEach()
方法为例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 @Override public void forEach (Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this .elementData; final int size = this .size; for (int i=0 ; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
2.3 小结
线程不安全的集合往往都是 Fail-Fast 的,由于不支持线程并发,Fail-Fast 迭代器选择抛出 ConcurrentModificationException
作为一个保底操作,作为开发者请不要利用该异常进行逻辑操作。
那么当我们使用集合在进行遍历时,如何知道哪些方法会导致 Fail-Fast 呢,粗略的说对集合进行添加、删除、更新操作都会导致,具体哪些方法你需要看该类的源码,到底哪些方法会进行 modCount
变更操作 。
三、Fail-Safe
Fail-Safe
类型的数据结构,当集合对象发生结构性修改时不会抛出任何异常 。这是因为迭代器在执行开始前,基于原集合类元拷贝了一份元素副本,因此迭代器执行的操作,如遍历、添加或删除等,并非原集合类对象的内部元素。也就是说,对原集合类对象的修改不会影响迭代器中的元素。CopyOnWriteArrayList
是这类的典型,例如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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 ) list.add(14 ); } } }
代码运行后输出如下结果:
另一种 Fail-Safe 的实现,不是依赖于拷贝副本的方式来实现,而是基于 Java 的内存弱一致性(weakly consistent,和强一致性相对于),意思就是 T1 线程在遍历的过程中,T2 线程产生的并发修改操作,可能会在 T1 输出中体现,也可能不体现,不强制要求 T1、T2 线程的内存一致。ConcurrentHashMap
是这类的典型,例如:
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 import java.util.concurrent.ConcurrentHashMap; import java.util.Iterator; public class FailSafeItr { public static void main (String[] args) { 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)); map.put("SEVEN" , 7 ); } } }
代码运行后输出如下结果:
1 2 3 4 5 ONE : 1 FOUR : 4 TWO : 2 THREE : 3 SEVEN : 7
四、总结
4.1 关键点
Fail Fast 迭代器的几个关键点:
遍历时一旦发现原集合对象发生修改则会抛出 ConcurrentModificationException
.
被遍历的是原集合对象的元素。
这类迭代器不需要额外内存空间。
Fail Safe 迭代器的几个关键点:
允许在进行迭代时对原集合对象的元素进行修改。
在遍历的同时修改集合对象的元素,不会抛出任何异常。
一种实现是:遍历的是原集合类对象元素的拷贝,需要额外的内存空间用于拷贝的元素数组。
另一种实现是:weakly consistent
,内存弱一致性。
4.2 数据结构枚举
下面列出分别使用 Fail-Fast 和 Fail-Safe 的数据结构,由于相关类太多,仅列出我用到的,欢迎留言补充。
(1)Fail-Fast
ArrayList、LinkedList、Vector【虽然是线程安全的】
HashSet、LinkedHashSet、TreeSet
HashMap、LinkedHashMap、TreeMap、Hashtable【虽然是线程安全的】
Collections.synchronizedXXX() 包装出的【虽然是线程安全的】
(2)Fail-Safe
CopyOnWriteArrayList
CopyOnWriteArraySet、ConcurrentSkipListSet、Sets.newConcurrentHashSet()【Guava 包提供的】
ConcurrentHashMap
Java Fail-Fast 与 Fail-Safe 特性