Java集合中的fail-fast快速失败机制
一、什么是 fail-fast 机制
fail-fast 机制是java集合（Collection）中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。例如：当某一个线程A通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛 ConcurrentModificationException 异常，产生 fail-fast 事件
当然，不仅是多个线程，单个线程也会出现 fail-fast 机制，包括 ArrayList、HashMap 无论在单线程和多线程状态下，都会出现 fail-fast 机制，即上面提到的异常
二、单线程下的 fail-fast 机制
通过举例 ArrayList 和 HashMap 这两种 Java 容器来看看在哪种情况下，会出现我们所说的 fail-fast 机制。先看看单线程的时候是如何执行的把~
1. ArrayList
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(10);
arrayList.add(11);
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
Integer next = iterator.next();
if (next == 11) {
arrayList.remove(next);
}
}
}
}
结果是：
10
11
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859)
at java.util.ArrayList$Itr.next(ArrayList.java:831)
at edu.just.failfast.ArrayListTest.main(ArrayListTest.java:15)
从结果看出，在单线程下，在使用迭代器进行遍历的情况下，如果调用 ArrayList 的 remove 方法，此时会报 ConcurrentModificationException 的错误，从而产生 fail-fast 机制
错误信息告诉我们，发生在 iterator.next() 这一行，继续点进去，定位到 checkForComodification() 这一行
public E next() {
checkForComodification(); // 错误在这儿
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
继续点进去，可以在 ArrayList 的 Itr 这个内部类中找到该方法的详细定义，这里涉及到两个变量，modCount 和 expectedModCount，modCount 是在 ArrayList 的父类 AbstractList 中进行定义的，初始值为 0，而 expectedModCount 则是在 ArrayList 的 内部类中进行定义的，在执行 arrayList.iterator() 的时候，首先会实例化 Itr 这个内部类，在实例化的同时也会对 expectedModCount 进行初始化，将 modCount 的值赋给 expectedModCount
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
// modCount 初始值为 0
protected transient int modCount = 0;
}
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
public Iterator<E> iterator() {
// 实例化内部类 Itr
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// expectedModCount 一开始等于 modCount
int expectedModCount = modCount;
// 检查是否发生异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}
知道了这两个变量是从何而来之后，我们来看 checkForComodification() 这个方法，如果 modCount 和 expectedModCount 不等，就会抛出 ConcurrentModificationException 这个异常，换句话说，一般情况下，这两个变量是相等的，那么啥时候起？这两个变量会不等呢？
经过观察，发现 ArrayList 在增加、删除（根据对象删除集合元素）、清除等操作中，都有 modCount++ 这一步骤，即代表着，每次执行完相应的方法，modCount 这一变量就会加 1
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 根据传入的对象来删除，而不是根据位置
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index); // modCount++
return true;
}
}
return false;
}
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
分析到这儿，似乎有些明白了，我们来完整的分析一下整个过程，在没有执行删除操作之前，ArrayList 中的 modCount 变量和迭代器中的 expectedModCount 的值一直都是相同的。在迭代的过程中，调用了 ArrayList 的 remove(Object o) 方法，使得 ArrayList 的 modCount 这个变量发生变化（删除成功一次加1），一开始和 modCount 相等的 expectedModCount 是属于内部类的，它直到迭代结束都没能发生变化。在迭代器执行下一次迭代的时候，因为这两个变量不等，所以便会抛出 ConcurrentModificationException 异常，即产生了 fail-fast 异常
通过一张图片更加清晰的观察整个过程
可以看到，在迭代器执行了 remove(Object o) 方法之后，modCount 等于 3，而 expectedModCount 依然等于 2，此时在执行 checkForComodification() 方法的时候，因为这两个变量不等，便产生了异常
2. HashMap
public class HashMapTest {
public static void main(String[] args) {
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(1, "QQQ");
hashMap.put(2, "JJJ");
hashMap.put(3, "EEE");
Set<Map.Entry<Integer, String>> entries = hashMap.entrySet();
Iterator<Map.Entry<Integer, String>> iterator = entries.iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> next = iterator.next();
if (next.getKey() == 2) {
hashMap.remove(next.getKey());
}
}
System.out.println(hashMap);
}
}
输出结果是：
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:922)
at java.util.HashMap$EntryIterator.next(HashMap.java:962)
at java.util.HashMap$EntryIterator.next(HashMap.java:960)
at edu.just.failfast.HashMapTest.main(HashMapTest.java:20)
根据错误的提示，找到出错的位置，也是在 Map.Entry<Integer, String> next = iterator.next() 这一行，继续寻找源头，定位到了 HashMap 中的内部类 EntryIterator 下的 next() 方法
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
继续往下找，来到了 HashMap 下的另一个私有内部类 HashIterator，该内部类也有 expectedModCount，modCount 是直接定义在 HashMap 中的，初始值为 0，expectedModCount 直接定义在 HashMap 的内部类中，当执行 arrayList.iterator() 这段代码的时候，便会初始化 HashIterator 这个内部类，同时调用构造函数 HashIterator()，将 modCount 的值赋给 expectedModCount
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
// 初始值为 0
transient int modCount;
// HashMap 的内部类 HashIterator
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
// 期待改变的值，初始值为 0
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
// expectedModCount 和 modCount 一样，初始值为 0
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
...
}
}
来看抛出异常的 nextEntry() 这个方法，只要 modCount 和 expectedModCount 不等，便会抛出 ConcurrentModificationException 这个异常，即产生 fast-fail 错误
同样，我们看一下 modCount 这个变量在 HashMap 的哪些方法中使用到了，和 ArrayList 类似，也是在添加、删除和清空等方法中，对 modCount 这个变量进行了加 1 操作
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 将 modCount 加 1
modCount++;
addEntry(hash, key, value, i);
return null;
}
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key); //该方法里面，如果删除成功，则将 modCount 加 1
return (e == null ? null : e.value);
}
public void clear() {
// 将 modCount 加 1
modCount++;
Arrays.fill(table, null);
size = 0;
}
我们来捋一下整个过程，在对 HashMap 和 Iterator 进行初始化之后，没有执行 remove 方法之前，HashMap 中的 modCount 和内部类 HashIterator 中的 expectedModCount 一直是相同的。在 HashMap 调用 remove(Object key) 方法时，如果删除成功，则会将 modCount 这个变量加 1，而 expectedModCount 是在内部类中的，一直没有发生变化，当进行到下一次迭代的时候（执行 next 方法），因为 modCount 和 expectedModCount 不同，所以抛出 ConcurrentModificationException 这个异常
根据图示来看一下
在 HashMap 添加了三个键不同的元素，且 Iterator 完成初始化之后，modCount 和 expectedModCount 的值都为 3，直到 HashMap 执行 remove(Object key) 方法，modCount 加 1 变成 4，而 expectedModCount 依然为 3，在下一次循环执行 next() 方法的时候，会检查这两个值，如果不同，则会抛出 ConcurrentModificationException 异常，即产生 fail-fast 机制
三、多线程的下的 fail-fast 机制
我们来分析一下多线程情况下，这两种容器是如何产生 fail-fast 机制的
1. ArrayList
public class ArrayListThreadTest {
public static void main(String[] args) throws InterruptedException {
final ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
Thread thread = new Thread("线程1") {
@Override
public void run() {
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer next = iterator.next();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("线程1: " + next);
}
}
};
Thread thread1 = new Thread("线程2") {
@Override
public void run() {
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer next = iterator.next();
if (next == 2) {
iterator.remove();
}
System.out.println("线程2: " + next);
}
}
};
thread.start();
thread1.start();
}
}
其中的一种输出是这样的：
线程2: 1
线程2: 2
线程2: 3
线程2: 4
线程2: 5
线程1: 1
Exception in thread "线程1" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859)
at java.util.ArrayList$Itr.next(ArrayList.java:831)
at edu.just.failfast.ArrayListThreadTest$1.run(ArrayListThreadTest.java:21)
同样，在 next 处，抛出了 ConcurrentModificationException 这个异常。
这里和单线程中不同的是，在删除的时候，调用的是 Iterator 对象的 remove() 方法，这是个内部类 Itr 中的方法。该内部类下的 remove 方法，其实还是调用 ArrayList 下的 remove(int index) 方法，但是，删除完之后，会将修改后的 modCount 赋值给 expectedModCount，相当于将这两个变量进行同步了
// ArrayList 中的内部类 Itr
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 将 modCount 赋给 expectedModCount
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
那么既然已经同步了，为什么还是会抛出这样的异常呢？通过输出的结果，大概可以分析出两个线程执行的流程
- 线程1先获得处理器的资源，进入运行状态，即执行 run() 方法里的代码，执行完
Iterator<Integer> iterator = list.iterator()这段代码之后，线程1因为执行了 sleep 方法，线程1进入阻塞状态 - 线程2获取处理器的资源，开始执行 run() 方法里面的代码，当迭代到 key 等于 2 的时候，执行
iterator.remove()，同时，ArrayList 下的 modCount 加 1，同时线程2迭代器下的 expectedModCount 的值和 modCount 一样，需要注意的是，modCount 是个共享的变量，即两个线程都可以同时对其进行操作，而 expectedModCount 则是各个线程各自拥有的，这一点很重要。最终，线程1下的 modCount 和 expectedModCount 都变成了 6 - 当线程2执行完毕，线程1重新获得处理器资源，开始执行，第一次循环没问题，第二次循环时，当执行到
Integer next = iterator.next()的时候，因为共享变量 modCount 已经变成了 6，而线程 1 的 expectedModCount 依然是 5，两个变量不等，此时抛出 ConcurrentModificationException 异常，即产生 fail-fast 机制
简单的说，因为 modCount 是共享变量，expectedModCount 则是各自独有的变量，这就导致了，一个线程更新了 modCount，同时更新了自己拥有的 expectedModCount，当另一个线程执行的时候，发现 modCount 更新了，但是自己的 expectedModCount 并没有更新，便会产生这样的错误
2. HashMap
public class HashMapThreadTest {
public static void main(String[] args) {
final HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(1, "AAA");
hashMap.put(2, "BBB");
Thread thread = new Thread("线程1") {
@Override
public void run() {
Iterator<Map.Entry<Integer, String>> iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> next = iterator.next();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("线程1: " + next);
}
}
};
Thread thread1 = new Thread() {
@Override
public void run() {
Iterator<Map.Entry<Integer, String>> iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> next = iterator.next();
if (next.getKey() == 2) {
hashMap.remove(next.getKey());
}
System.out.println("线程2: " + next);
}
}
};
thread.start();
thread1.start();
}
}
结果是：
线程2: 1=AAA
线程2: 2=BBB
线程1: 1=AAA
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:922)
at java.util.HashMap$EntryIterator.next(HashMap.java:962)
at java.util.HashMap$EntryIterator.next(HashMap.java:960)
at edu.just.failfast.HashMapThreadTest$1.run(HashMapThreadTest.java:19)
HashMap 的过程和上面的 ArrayList 类似，因为 modCount 是共享变量，expectedModCount 是每个线程独有的变量，线程2的 HashMap 执行了 remove()，导致 modCount 和expectedModCount 同时加 1，而线程1的 expectedModCount 变量的值并没有修改，导致了 modCount 和 expectedModCount 这两个变量的值不同，因此抛出异常
四、解决方案
1.
对应单线程来说，我们执行删除操作的时候，不要使用集合自身的删除方法，而使用集合中迭代器的删除方法
因为无论是 ArrayList 还是 HashMap，他们对应的迭代器中的 remove 方法中，都有这么一句代码，expectedModCount = modCount，这就意味着，即使删除了，这两个变量也是一直同步的，不会发生 modCount 加 1，而 expectedModCount 不变的情况
2.
使用采用了 fail-safe 机制的集合类，比如 CopyOnWriteArrayList、CopyOnWriteArraySet，这些集合在遍历的时候不是直接在原来集合的内容上进行访问的，而是先复制原来集合的底层数组，然后对拷贝的数组进行遍历，此时就算在遍历的时候进行了删除操作，此时也是对原来集合的内容进行删除的，拷贝过来的内容并没有受到影响
采用了安全失败机制的集合的底层并没有类似 expectedModCount 这样进行修改次数标识的属性，所以也永远不会抛出 ConcurrentModificationException 这种异常
五、参考
https://www.cnblogs.com/dolphin0520/p/3933551.html
https://www.cnblogs.com/chenssy/p/3870107.html
https://blog.****.net/u011240877/article/details/52743564
https://www.nowcoder.com/questionTerminal/95e4f9fa513c4ef5bd6344cc3819d3f7?pos=101&mutiTagIds=570&orderByHotValue=1