JDK集合fail-fast机制源码解读

前情

      这两天一哥们在面试国内大厂问到了，小伙子你知道fail-fast是啥吗？？小伙子一脸懵逼，随口来了句中式翻译，“错的快”？？？,此时此刻的面试官也是一脸懵逼，说道，你觉得怎么走最快就怎么走吧。。。。哈哈，简单的开个玩笑。其实我之前只知道这个玩意的名称，但是不知道底层实现原理是啥，今天我们就来看看到底发生了啥

简述

      fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当使用迭代器时候，进行一定的改变，就有可能会发生fail-fast，
      即抛出ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制通常用来检测bug。在ArrayList源码中有一定的描述。

Note that the fail-fast behavior of an iterator cannot be guaranteed
as it is, generally speaking, impossible to make any hard guarantees in the
presence of unsynchronized concurrent modification. Fail-fast iterators
throw {@code ConcurrentModificationException} on a best-effort basis.
Therefore, it would be wrong to write a program that depended on this
exception for its correctness: the fail-fast behavior of iterators
should be used only to detect bugs.

制造异常

public class Main {
    public static void main(String[] args) {
        testSingleThread();
    }

    //测试单线程的情况下的异常
    public static void testSingleThread() {
        System.out.println("testSingleThread()");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i + "");
        }
        //创建一个迭代器
        Iterator<String> iterator = list.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            if (i == 3) {
                list.remove(3); //不安全的做法
               // iterator.remove();
            }
            System.out.print(iterator.next() + " ");
            i++;
        }
    }

    //测试多线程的情况下
    public static void testConcurrent() {
        System.out.println(" testConcurrent()()");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            list.add(i + "");
        }
        Iterator<String> iterator = list.iterator();
        //线程池创建10个线程
        ExecutorService executorService = Executors.newFixedThreadPool(10);
        //执行线程
        for (int i = 0; i < 10; i++) {
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    while(iterator.hasNext()) {
                        System.err.print(iterator.next() + " ");
                    }
                   list.remove(2);
                }
            });
        }
        executorService.shutdown();
    }
}

运行结果如下

testSingleThread()
Exception in thread “main” java.util.ConcurrentModificationException
0 1 2 at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)atjava.util.ArrayList$Itr.next(ArrayList.java:851)
at com.demo.list.Main.testSingleThread(Main.java:33)
at com.demo.list.Main.main(Main.java:15)

testConcurrent()
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 16 18 19 20 22 23 24 25 26 27 28 29 21 31 32 33 34 35 36 37 38 39 40 41 30 42 44 43 45 46 47 48 49 51 50 52 54 55 56 57 58 59 60 53 61 63 62 65 66 67 68 64 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 93 94 95 96 97 98 99 92
Exception in thread “pool-1-thread-2” java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)atjava.util.ArrayList$Itr.next(ArrayList.java:851)
at com.demo.list.Main$1.run(Main.java:54)atjava.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)atjava.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
at java.lang.Thread.run(Thread.java:748)

上面可以看出，在迭代的过程中调用list.remove(i)的方法就会出现ConcurrentModificationException

源码溯源

接下来就根据源码来查找出现问题的原因

ArrayList中的迭代方法

 public Iterator<E> iterator() {
        return new Itr();
    }
    
  /**
     *内部定义了Itr的内部类来实现迭代器
     * An optimized version of AbstractList.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最后一个元素的索引，没有就为-1
        int expectedModCount = modCount; //期待的修改的次数

        public boolean hasNext() { //当cursor 不等于 元素的个数（size）,说明还没  到最后
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() { //这个就是拿到当索引的值
            checkForComodification(); //检查modCount，看modCount是不是已经被别的线程修改了
            int i = cursor; //i为当前值的索引
            if (i >= size) //当索引大于size就抛异常
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;//拿到值数组
            if (i >= elementData.length) //当索引大于数组长度也直接抛异常，  
            //这是针对size 与 elementData不同步做的检查
                throw new ConcurrentModificationException();
            cursor = i + 1; //游标+1
            return (E) elementData[lastRet = i];//返回值，且将i赋给lastRet
        }

        public void remove() { //请记住，这是ArrayList中iterator的remove方法  
       //不是ArrayList中的remove方法，虽然都是来实现删除操作的，但是底层实现不相同
            if (lastRet < 0) //最后一个下标是小于0，直接抛参数异常
                throw new IllegalStateException();
            checkForComodification(); //检查modCount

            try {
                ArrayList.this.remove(lastRet); //l根据astRet进行删除
                cursor = lastRet; //cursor 也变为 lastRet,因为删除了当前位置的值
                lastRet = -1; 
                expectedModCount = modCount; //得到ModCount
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        //检查modCout是否被其他线程修改
        final void checkForComodification() {
            if (modCount != expectedModCount) //说明modCount已经发生了修改，ArrayList的结构已经发生改变
                throw new ConcurrentModificationException();//直接抛异常
        }
    }

我们再来看看ArrayList中的remove()方法

public E remove(int index) {
        rangeCheck(index); //检查index是否合法

        modCount++; //我去，modCout直接++了，这也就说明为啥terator.next()会报错
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

再次看看出现异常的代码

 public static void testSingleThread() {
        System.out.println("testSingleThread()");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i + "");
        }
        //创建一个迭代器
        Iterator<String> iterator = list.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            if (i == 3) {
                list.remove(3); //不安全的做法，这里调用的是ArrayList的remove方法，由于remove，modCount++;
               // iterator.remove();//这才是最正确的做法
            }
            System.out.print(iterator.next() + " ");//恰好在这里的expectedModCount没有修改，checkForComodification就直接抛异常
            i++;
        }
    }

在高并发环境下也是如此，迭代的时候，其他线程修改了结构，就会抛异常

总结

  其实就是集合中的错误检查机制，Map,List中都存在.
  1.在迭代删除值的时候，要使用iterator,remove()方法，原因就是这modCount != expectedModCount
  2.在高并发环境下，推荐使用CopyOnWriteArrayList,ConcurrentHashMap

文章到此，我是一个出生牛肚不怕虎的99年小伙子，有什么问题大家可以评论区留言，谢谢大家的阅读！！！