【Java多线程】迭代器与并发修改异常

本文参考自《Java并发编程实战》

引子

同步容器

在介绍具体内容前，我们先认识一下Java的同步容器类。

Java的同步容器类包括Vector和Hashtable，二者是JDK早期的一部分，此外还包括在JDK1.2中添加的一些功能相似的类。这些同步的封装器类是由Collections.synchronizedxxx等工厂方法创建的。例如 Map<String,String> map =Collections.synchronizedMap(new HashMap<String,String >());

这些类实现线程安全的方法是：将他们的状态封装起来，并对每个公有方法进行同步（synchronized修饰），使得每次只能有一个线程访问容器的状态。

同步容器类都是线程安全的，但在某些情况下可能需要额外的客户端锁来保护复合操作，比如：迭代、跳转（根据指定顺序找到当前元素的下一个元素）以及条件运算（例如：Map的若没有则添加），在同步类容器中，这些复合操作在没有客户端加锁的情况下是仍然是线程安全的，但是当其他线程并发的修改容器时，他们可能会出现异常。

    public static Object getLat(Vector list){
        int lastIndex =list.size()-1;
        return list.get(lastIndex);
    }
    public static void deleteLast(Vector list){
        int lastIndex =list.size()-1;
        list.remove(lastIndex);
    }

上面的代码，如果线程A在包含10个元素的Vector上调用getLast,同时线程B在同一个Vector上调用deleteLast，这时可能会抛出ArrayIndexOutOfBoundsException异常。因为在调用size与调用get这个两个操作期间，其他线程调用了remove，导致之前调用size的索引值不再有效，那么就抛出了指针越界异常。
想要避免上面异常的出现，可以再迭代过程中持有容器的锁，即客户端加锁，确保调用size与调用get这个两个操作之间不会插入其他的指令，这就保证了两个操作的原子性。

    public static Object getLat(Vector list){
        synchronized (list) {
            int lastIndex =list.size()-1;
            return list.get(lastIndex);
        }
    }
    public static void deleteLast(Vector list){
        synchronized (list) {
            int lastIndex =list.size()-1;
            list.remove(lastIndex);
        }
    }

然而在迭代期间对容器加锁，并不是一个很好的方法，例如，某些线程在可以访问容器之前，必须等待迭代过程结束，如果容器的规模很大，那么这些线程就会长时间得到等待，这可能会产生死锁，极大地降低了脱吐量和CPU的利用率。这无疑降低了并发性。

并发修改异常ConcurrentModificationException

以下部分内容转载自Java3y公众号。

在JDK5以后，Java推荐使用for-each(迭代器)来遍历我们的集合，好处就是简洁、数组索引的边界值只计算一次。

我们来对比一下使用for和使用for-each迭代对于同一段代码抛出异常的区别。

    public static void main(String[] args) {

        // 初始化Vector
        Vector<String> vector = new Vector();
        vector.add("关注公众号");
        vector.add("Java3y");
        vector.add("买Linux可到我下面的链接，享受最低价");
        vector.add("给3y加鸡腿");

        // 遍历Vector
        for (int i = 0; i < vector.size(); i++) {

            // 比如在这执行vector.clear();
            //new Thread(() -> vector.clear()).start();

            System.out.println(vector.get(i));
        }
    }

同样地：如果在遍历Vector的时候，有别的线程修改了Vector的长度，那还是会有问题！
线程A遍历Vector，执行vector.size()时，发现Vector的长度为5
此时很有可能存在线程B对Vector进行clear()操作
随后线程A执行vector.get(i)时，抛出异常ArrayIndexOutOfBoundsException。

如果使用for-each(迭代器)来做上面的操作，会抛出ConcurrentModificationException异常。

ConcurrentModificationException是如何产生的呢？

为了将问题阐述清楚，我们使用了Vector，虽然这是一个古老的容器类。然而许多“现代”的容器类也并没有消除复合操作的问题。无论在直接迭代还是foreach循环语法中，对容器类进行迭代的标准方式都是使用Iterator。然而如果有其他线程并发地修改容器，那么即使是使用迭代器也无法避免在迭代期间对容器加锁。在设计同步容器类的迭代器时并没有考虑到并发修改的问题，并且它们表现出的行为是“及时失败”的。这意味着当发现容器在迭代过程中被修改时，就会抛出一个ConcurrentModificationException异常。

这种“即时失败”的迭代器并不是一种完备的处理机制，只是“善意地”捕获并发错误，因此只能作为并发问题的预警指示器。他们采用的实现方式是：将计数器的变化与容器关联起来，如果在迭代期间计数器被修改，那么hasNext或next将抛出ConcurrentModificationException。然而这种异常是在没有同步的情况下进行的，也就是说可能看到失效的计数值，因为此时可能在迭代器没有意识到的情况下发生了容器的修改。这是一种设计上的权衡，从而将低并发修改操作的检测代码对程序性能带来的影响。

例如如下代码，如果不想出现ConcurrentModificationException，就必须在迭代过程持有容器的锁：

        List<myObject> list = Collections.synchronizedList(new ArrayList<>());
        //可能发生ConcurrentModificationException
        for (myObject i : list) {
            doSomething(i);
        }

然而有时候开发人员并不希望在迭代期间对容器加锁。如果不希望在迭代期间对容器加锁，那么一种替代方法就是“克隆”容器，并在副本上进行迭代。由于副本被封闭在线程内，因此其他线程不会在迭代期间对其进行修改，这样就避免了抛出ConcurrentModificationException异常。在克隆容器时存在显著的性能开销。这种方式的好坏取决于多个因素，包括容器的大小，在每个元素上执行的工作，迭代操作相对于容器其他操作的调用频率，以及在响应时间和吞吐量等方面的需求。

为了解决同步容器低并发和ConcurrentModificationException的问题，Java5.0中，添加了并发容器类，例如用来替代Vector和Hashtable的CopyOnWriteArrayList和ConcurrentHashMap。通常，使用并发容器代替同步容器，能够极大提升伸缩性和安全性。

那么，我们平常也需要在循环中删除ArrayList元素的，怎么办？其实也很简单，代码如下：

        Iterator it=list.iterator();

        while(it.hasNext()){
            Object e=it.next();
            if("b".equals(e)){
                it.remove();
            }
        }
        System.out.println(list);

通过迭代器自身的remove和add方法来对列表做修改
迭代器对列表中元素的遍历是通过next函数来实现的，新创建的迭代器默认指向列表中的第一个元素，每执行一次next，Iterator迭代器的游标都会指向下一个元素。
迭代器的remove操作删除的是最近一次由next操作获取的元素，而不是当前游标所指向的元素。