快速失效与安全失效，是针对迭代数据结构过程出现的两种说法。
Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。
fail-fast机制，是一种错误检测机制。它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。若在多线程环境下使用fail-fast机制的集合，建议使用“java.util.concurrent包下的类”去取代“java.util包下的类”。
以ArraryList举例，何时出现fail-fast事件，抛出ConcurrentModificationException异常。
public abstract class AbstractListextends AbstractCollectionimplements List {
...
// AbstractList中唯一的属性
// 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1
protected transient int modCount =0;
// 返回List对应迭代器。实际上，是返回Itr对象。
public Iteratoriterator() {
return new Itr();
}
// Itr是Iterator(迭代器)的实现类
private class Itrimplements Iterator {
int cursor =0;
int lastRet = -1;
// 修改数的记录值。
// 每次新建Itr()对象时，都会保存新建该对象时对应的modCount；
// 以后每次遍历List中的元素的时候，都会比较expectedModCount和modCount是否相等；
// 若不相等，则抛出ConcurrentModificationException异常，产生fail-fast事件。
int expectedModCount =modCount;
public boolean hasNext() {
return cursor != size();
}
public E next() {
// 获取下一个元素之前，都会判断“新建Itr对象时保存的modCount”和“当前的modCount”是否相等；
// 若不相等，则抛出ConcurrentModificationException异常，产生fail-fast事件。
checkForComodification();
try {
E next = get(cursor);
lastRet =cursor++;
return next;
}catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet
cursor--;
lastRet = -1;
expectedModCount =modCount;
}catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount !=expectedModCount)
throw new ConcurrentModificationException();
}
}
...
}
在调用 next() 和 remove()时，都会执行 checkForComodification()。若 “modCount 不等于 expectedModCount”，则抛出ConcurrentModificationException异常，产生fail-fast事件。
在创建iterator的时候，modCount 与 expectedModCount 是相等的，但是何时会被修改呢？下面可以看一下ArraryList的源码。
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable {
...
// list中容量变化时，对应的同步函数
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity *3) /2 +1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
// 添加元素到队列最后
public boolean add(E e) {
// 修改modCount
ensureCapacity(size +1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 添加元素到指定的位置
public void add(int index, E element) {
if (index > size || index <0)
throw new IndexOutOfBoundsException(
"Index: " + index +", Size: " + size);
// 修改modCount
ensureCapacity(size +1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index +1,
size - index);
elementData[index] = element;
size++;
}
// 添加集合
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
// 修改modCount
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew !=0;
}
// 删除指定位置的元素
public E remove(int index) {
RangeCheck(index);
// 修改modCount
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index -1;
if (numMoved >0)
System.arraycopy(elementData, index +1, elementData, index, numMoved);
elementData[--size] =null; // Let gc do its work
return oldValue;
}
// 快速删除指定位置的元素
private void fastRemove(int index) {
// 修改modCount
modCount++;
int numMoved = size - index -1;
if (numMoved >0)
System.arraycopy(elementData, index +1, elementData, index,
numMoved);
elementData[--size] =null; // Let gc do its work
}
// 清空集合
public void clear() {
// 修改modCount
modCount++;
// Let gc do its work
for (int i =0; i < size; i++)
elementData[i] =null;
size =0;
}
...
}
通过代码我们可以看到：只要更改集合中的元素个数：例如add(),remove(),clear()都会改变ModCount的值。
接下来，我们再系统的梳理一下fail-fast是怎么产生的。步骤如下：
(01) 新建了一个ArrayList，名称为arrayList。
(02) 向arrayList中添加内容。
(03)新建一个“线程a”，并在“线程a”中通过Iterator反复的读取arrayList的值。
(04) 新建一个“线程b”，在“线程b”中删除arrayList中的一个“节点A”。
(05) 之后，就会产生fail-fast事件了，即：“线程a”创建了arrayList的Iterator。此时“节点A”仍然存在于arrayList中，创建arrayList时，expectedModCount = modCount(假设它们此时的值为N)。
在“线程a”在遍历arrayList过程中的某一时刻，“线程b”执行了，并且“线程b”删除了arrayList中的“节点A”。“线程b”执行remove()进行删除操作时，在remove()中执行了“modCount++”，此时modCount变成了N+1！
“线程a”接着遍历，当它执行到next()函数时，调用checkForComodification()比较“expectedModCount”和“modCount”的大小；而“expectedModCount=N”，“modCount=N+1”,这样，便抛出ConcurrentModificationException异常，产生fail-fast事件。
如何避免fail-fast问题的产生呢？java.util.current包帮你解决。看一下CopyOnWriteArrayList
public class CopyOnWriteArrayList
implements List, RandomAccess, Cloneable, java.io.Serializable {
...
// 返回集合对应的迭代器
public Iteratoriterator() {
return new COWIterator(getArray(), 0);
}
...
private static class COWIteratorimplements ListIterator {
private final Object[]snapshot;
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
// 新建COWIterator时，将集合中的元素保存到一个新的拷贝数组中。
// 这样，当原始集合的数据改变，拷贝数据中的值也不会变化。
snapshot = elements;
}
public boolean hasNext() {
return cursor
}
public boolean hasPrevious() {
return cursor >0;
}
public E next() {
if (!hasNext())
throw new NoSuchElementException();
return (E)snapshot[cursor++];
}
public E previous() {
if (!hasPrevious())
throw new NoSuchElementException();
return (E)snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor -1;
}
public void remove() {
throw new UnsupportedOperationException();
}
public void set(E e) {
throw new UnsupportedOperationException();
}
public void add(E e) {
throw new UnsupportedOperationException();
}
}
...
}
(01) 和ArrayList继承于AbstractList不同，CopyOnWriteArrayList没有继承于AbstractList，它仅仅只是实现了List接口。
(02) ArrayList的iterator()函数返回的Iterator是在AbstractList中实现的；而CopyOnWriteArrayList是自己实现Iterator。
(03) ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常。
个人公号：【排骨肉段】，可以关注一下。
网友评论