庖丁解牛之ConcurrentModificationExcep

前言

ConcurrentModificationException 这个异常很常见，如果程序中经常使用集合操作，对这个异常会非常的熟悉，本人在工作中就遇到过两次这个异常，印象非常深刻，为了以后不再范这类问题特此记录一下

出现问题的场景

• 在多线程中一个线程修改了数据，另外一个线程正在遍历集合数据，就出现了这类的问题，大多数人多知道这类场景
• 另外一个场景就是在单线程中，在数据迭代的时候修改集合数据出现的问题

多线程场景

import java.util.ArrayList;
import java.util.Iterator;

/**
 * Created by nate on 2018/7/9.
 */
public class Test {

    static ArrayList<Integer> list = new ArrayList<Integer>();

    public static void main(String args[]) {
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Thread thread1 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer integer = iterator.next();
                    System.out.println(integer);
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            };
        };
        Thread thread2 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer integer = iterator.next();
                    if (integer == 2)
                        iterator.remove();
                }
            };
        };
        thread1.start();
        thread2.start();
    }

}

结果：出现异常了

1
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.ArrayListItr.checkForComodification(ArrayList.java:901) at java.util.ArrayListItr.next(ArrayList.java:851)
at Test$1.run(Test.java:21)

单线程场景

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Created by nate on 2018/7/9.
 */
public class Test1 {


    public static void main(String args[]) {
        List<Integer> data = new ArrayList<>();
        data.add(1);
        data.add(2);
        data.add(3);
        data.add(4);

        Iterator<Integer> iterator = data.iterator();
        while (iterator.hasNext()) {
            Integer next=iterator.next();
            if(next==2){
                data.remove(2);
            }
        }
    }
}

结果：出现异常

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayListItr.checkForComodification(ArrayList.java:901) at java.util.ArrayListItr.next(ArrayList.java:851)
at Test1.main(Test1.java:21)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:497)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

用foreach迭代也是一样的

import java.util.ArrayList;
import java.util.List;

/**
 * Created by nate on 2018/7/9.
 */
public class Test1 {

    public static void main(String args[]) {
        List<Integer> data = new ArrayList<>();
        data.add(1);
        data.add(2);
        data.add(3);
        data.add(4);
        for (Integer integer : data) {
            if (integer == 2) {
                data.remove(integer);
            }
        }
    }
}

结果：出现异常

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayListItr.checkForComodification(ArrayList.java:901) at java.util.ArrayListItr.next(ArrayList.java:851)
at Test1.main(Test1.java:17)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:497)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

但是如果用过for循环就么有问题

import java.util.ArrayList;
import java.util.List;

/**
 * Created by nate on 2018/7/9.
 */
public class Test1 {

    public static void main(String args[]) {
        List<Integer> data = new ArrayList<>();
        data.add(1);
        data.add(2);
        data.add(3);
        data.add(4);

        for (int i = 0; i < data.size(); i++) {
            if (data.get(i) == 2) {
                data.remove(data.get(i));
            }
        }
    }
}

结果正常运行，这是为何呢？

问题原因分析，庖丁解牛

要想分析这个问题，我们只能从源码分析，我们先看一下iterator（）这个方法的源码

public Iterator<E> iterator() {
    return new Itr();
}

实际上是new了一个Itr对象，我们看一下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();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

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

这个类中有这么一个方法checkForComodification，这个方法中抛出了一个异常，这异常就是ConcurrentModificationException用这个异常，接下来我们就看这个异常是哪个地方调用了，在代码中这个异常是next方法调用，我们把分析的重点放到next方法中，在next方法中首先是先调用的checkForComodification(),

这方法的主要逻辑是检测modCount和expectedModCount是否相等，如果不相当就抛出异常，这两个变量是什么意思呢？

modCount变量表示的这个集合被修改的次数，add、remove都会导致modCount变量增加

1.我们分析一下多线程场景出现的问题的情况

thread1中创建了iterator对象，thread2中也创建iterator对象，这个时候这两个iterator中的expectedModCount值是一样的，但是线程2中调用了remove方法，也就modCount这个值改变了，但是这个modCount值不是用volatile修饰的不是多线程可见了，也就是thread1中的iterator对象的中的成员变量expectedModCount还是老的值，这时候在调用next方法发现modCount != expectedModCount然后就报异常了

2.单线程场景问题分析

问题的根源是这行代码 data.remove(2);这个行代码修改了List类中modCount的值，但是这个值并没有同步到Itr 这个对象中，所以在下次迭代的时候就报异常了

foreach 为什么也出现这个问题

因为foreach循环的实现跟iterator迭代是差不多的所以也出现这个问题，先看一下源代码吧

@Override
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

在forEach循环中，首先保存了modCount的值给expectedModCount，然后在for循环中判断 modCount 和expectedModCount的值是否相等，如果相等正常迭代，如果再迭代的过程中改变了modCount的值就抛出异常，我们上面的例子就是在迭代的时候改变了modCount的值

for循环为什么没有出现这个问题呢？

因为for循环中没有加入modCount的值和expectedModCount是否相等这个逻辑，所以可以正常运行

如何避免这类问题？

知道问题的原因后，我们就想怎么解决这类问题

对于多线程请求如何解决?

解决办法有两种：一种是在iterator迭代的时候加锁,确保没有其他线程干扰，另外一种是使用并发容器CopyOnWriteArrayList代替ArrayList和Vector

对于单线程情况

我建议直接用for 索引的方式迭代数据，不要用foreach方式遍历数据,如果有对数据修改的操作，直接调用iterator的remove方法

迭代的时候加锁

import java.util.ArrayList;
import java.util.Iterator;

/**
 * Created by nate on 2018/7/9.
 */
public class Test {

    static ArrayList<Integer> list = new ArrayList<Integer>();

    public static void main(String args[]) {
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Thread thread1 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                synchronized (list) {
                    while (iterator.hasNext()) {
                        Integer integer = iterator.next();
                        System.out.println(integer);
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }
            };
        };
        Thread thread2 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                synchronized (list) {
                    while (iterator.hasNext()) {
                        Integer integer = iterator.next();
                        if (integer == 2)
                            iterator.remove();
                    }
                }
            }  ;
        };
        thread1.start();
        thread2.start();
    }

}

程序正常运行，通过加锁的方式保证了同一个时候只能有一个线程访问，所以不会出问题，但是效率也下降了

有的人想如果把ArrayList 换成Vector 是不是也可以呢？答案可能令大家失望了，同样会报错

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Vector;

/**
 * Created by nate on 2018/7/9.
 */
public class Test {

    static Vector<Integer> list = new Vector<Integer>();

    public static void main(String args[]) {
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Thread thread1 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer integer = iterator.next();
                    System.out.println(integer);
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            };
        };
        Thread thread2 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer integer = iterator.next();
                    if (integer == 2)
                        iterator.remove();
                }
            }

            ;
        };
        thread1.start();
        thread2.start();
    }

}

结果：

1
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.VectorItr.checkForComodification(Vector.java:1184) at java.util.VectorItr.next(Vector.java:1137)
at Test$1.run(Test.java:22)

也是为什么呢，Vector不是所以的方法都是加锁的吗？Vector的方法是加锁的这个没有错，但是Iterator类的方法可以不加锁的，所以多个线程访问还是会有问题的

CopyOnWriteArrayList 方式

CopyOnWriteArrayList 可以解决迭代的时候崩溃问题，但是要对个这个类有足够的了解才能使用，否则受伤的只是自己

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * Created by nate on 2018/7/9.
 */
public class Test {

    static CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<Integer>();

    public static void main(String args[]) {
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Thread thread1 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    Integer integer = iterator.next();
                    System.out.println(Thread.currentThread().getId()+" : " +integer);
                }
            }

            ;
        };
        Thread thread2 = new Thread() {
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer integer = iterator.next();
                    if (integer == 2) {
//                        iterator.remove();
                        list.remove(integer);
                    }
                    System.out.println(Thread.currentThread().getId()+" : " +integer);

                }
                System.out.println(Thread.currentThread().getId()+" : " +list);

            }

            ;
        };
        thread1.start();
        thread2.start();
    }
}

结果：

12 : 1
12 : 2
12 : 3
12 : 4
12 : 5
12 : [1, 3, 4, 5]
11 : 1
11 : 2
11 : 3
11 : 4
11 : 5

我们关注一下线程id是12的，线程id是12这个输出的list结果是[1, 3, 4, 5]，这个是正确的，因为我们已经移除了2这个数据

但是线程id是11的这个输出的有问题，因为2这个数据我们已经在线程12中已经移除，并且11 : 2这个是在12 : [1, 3, 4, 5]之后打印的，说明数据已经移除了，但是log上会输出11:2这个呢？这个就和CopyOnWriteArrayList的机制有关系了，CopyOnWriteArrayList为了解决ConcurrentModificationException这个异常，在每次在对CopyOnWriteArrayList中的数据进行修改例如add、remove操作的时候，都会创建一个新的Object[] 数组，操作完成后在复制给 CopyOnWriteArrayList中的elements变量，线程11还是访问的旧的数据，所以还会输出2

/**
 * Sets the array.
 */
final void setArray(Object[] a) {
    elements = a;
}

/**
 * Creates an empty list.
 */
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

iterator()方法

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

getArray方法

final Object[] getArray() {
    return elements;
}

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    public boolean hasPrevious() {
        return cursor > 0;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code remove}
     *         is not supported by this iterator.
     */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code set}
     *         is not supported by this iterator.
     */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code add}
     *         is not supported by this iterator.
     */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int size = snapshot.length;
        for (int i = cursor; i < size; i++) {
            action.accept((E) snapshot[i]);
        }
        cursor = size;
    }
}

总结：

1.COWIterator在创建的时候保留了CopyOnWriteArrayList的数组，之后都访问的这个数据，不关CopyOnWriteArrayList中的数据是否有变化

2.COWIterator 不支持remove、add方法

3.每次修改都需要重新new一个数组，并且将array数组数据拷贝到new出来的数组中，效率会大幅下降