弄懂Fail-Safe,Fail-First

今天在做算法题的时候，碰到的如下问题，记录下来加深记忆。很多时候我们都有这样一个需求，在迭代的时候（满足某个给定的条件）添加或者删除元素。结果却是等来了java.util.ConcurrentModificationException这个异常，追踪其原因，就是有些容器是Fail-Safe，Fail-First的。出现异常的代码如下：

public class CollectionTest {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        for (int a : arrayList) {
            if (a == 1)
                arrayList.remove(a);
        }
        System.out.println(arrayList);
    }
}

1. Fail-Safe,Fail-First概念。

在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;
        }

        @SuppressWarnings("unchecked")
        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];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

在初始化的时候，它会让expectedModCount = modCount，modCount在AbstractList，每次对ArrayList的结构性改变（remove,add）都会使得modCount相应的减1或者加1。来分析下我们刚开始出现问题的代码。当我们获取到迭代器的时候，此时expectedModCount = modCount。当remove的时候，modCount会加1，但是expectedModCount却不变，当执行Itr的next()操作时候，会执行上述源码中的checkForComodification()来检查expectedModCount = modCount，若不相等，则会throw ConcurrentModificationException。
所以就不难分析出上述问题。

FailFirst:当我们在迭代获取集合元素的时候，在迭代器创建之后，对集合做一些结构性的改变（remove,add操作)，那么FailFirst容器首先会抛出 ConcurrentModificationException。

2. 如何解决上述问题。

 public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        ArrayList sub=new ArrayList();
        for(int a:arrayList){
            if(a==1)
                sub.add(a);
        }
        arrayList.removeAll(sub);
        System.out.println(arrayList);
    }

上述这个办法好，但是却占额外空间。

public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            int a = iterator.next();
            if (a == 1)
                iterator.remove();
        }

        System.out.println(arrayList);
    }

这样就不占额外的空间，是更好的办法。 iterator.remove()为啥不会抛异常，看看源码

public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

expectedModCount = modCount;这句起作用，它删除元素后它会强制满足条件。所以不会抛异常。

3. Fail-First的出场 。

将刚开始的代码换成如下的形式,问题迎刃而解。

public static void main(String[] args) {
        CopyOnWriteArrayList<Integer> arrayList = new CopyOnWriteArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            int a = iterator.next();
            if (a == 1)
               arrayList.remove(a);
        }

        System.out.println(arrayList);
    }

像CopyOnWriteArrayList这类容器就属于Fail-Safe容器。当集合结构改变的时候不会抛出异常，这是因为他们只是原始集合的复制，它用snapshot这个数组来保存集合。所以你原始集合的修改只会让原来的引用指向新的数组，而旧的引用还是被迭代器的snapshot所引用。因而他们属于Fail-Safe容器。看看其源码

public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 private boolean remove(Object o, Object[] snapshot, int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] current = getArray();
            int len = current.length;
            if (snapshot != current) findIndex: {
                int prefix = Math.min(index, len);
                for (int i = 0; i < prefix; i++) {
                    if (current[i] != snapshot[i] && eq(o, current[i])) {
                        index = i;
                        break findIndex;
                    }
                }
                if (index >= len)
                    return false;
                if (current[index] == o)
                    break findIndex;
                index = indexOf(o, current, index, len);
                if (index < 0)
                    return false;
            }
            Object[] newElements = new Object[len - 1];
            System.arraycopy(current, 0, newElements, 0, index);
            System.arraycopy(current, index + 1,
                             newElements, index,
                             len - index - 1);
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

从上面可以看出每次添加元素都是线程安全的，因为加了锁。另外，每添加一个元素，都会把原来的引用指向一个新的数组。所以对他进行操作没问题。所以使用Fail-Safe容器也是一种很好的解决办法。