前言

最近還是很忙，寫一些相對(duì)容易的大家都知道的知識(shí)點(diǎn)吧。

ConcurrentModificationException（下文簡(jiǎn)稱CME）呛凶，即并發(fā)修改異常，是Java集合操作中常見的一種異常行贪。本文通過示例及JDK源碼分析產(chǎn)生CME的內(nèi)部機(jī)制漾稀，并提出解決方法。

CME的產(chǎn)生

java.util包下很多集合的操作都可能會(huì)拋出CME建瘫，這里就以ArrayList為例崭捍。下面的程序產(chǎn)生包含10個(gè)元素的ArrayList，遍歷它啰脚，并在遍歷過程中隨機(jī)刪掉其中一個(gè)元素殷蛇。

public class CMEExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            list.add(String.valueOf(i));
        }
        String random = String.valueOf(new Random().nextInt(10) + 1);
        System.out.println(random);
        for (String s : list) {
            if (s.equals(random)) {
                list.remove(s);
            }
        }
    }
}

多次運(yùn)行以上程序，發(fā)現(xiàn)大多數(shù)情況均會(huì)拋出CME橄浓，如以下輸出：

6
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    at me.lmagics.CMEExample.main(CMEExample.java:19)

但是當(dāng)要?jiǎng)h除元素"9"時(shí)粒梦，就不會(huì)拋出異常，執(zhí)行成功荸实。為什么會(huì)有兩種不同的情況匀们？下面就通過JDK源碼來(lái)分析。

CME原因分析（fail-fast機(jī)制）

CMEExample類中使用foreach循環(huán)來(lái)遍歷List准给，也就相當(dāng)于采用了迭代器昼蛀。ArrayList的迭代器實(shí)現(xiàn)位于私有內(nèi)部類Itr中宴猾，其源碼如下。

    public Iterator<E> iterator() {
        return new 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;

        Itr() {}

        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();
        }
    }

查看報(bào)錯(cuò)信息叼旋，CME是在調(diào)用Itr.next()方法時(shí)仇哆，從checkForComodification()方法拋出的，原因是modCount與expectedModCount的值不相等夫植。由上面的代碼可知讹剔，expectedModCount在Itr初始化時(shí)就賦值，其值等于modCount详民，所以modCount的值一定發(fā)生了變化延欠。

modCount字段定義在ArrayList的父類AbstractList中。

protected transient int modCount = 0;

根據(jù)JavaDoc的解釋沈跨，modCount記錄了一個(gè)列表發(fā)生結(jié)構(gòu)化修改（structurally modified由捎，如改變大小或打亂順序）的次數(shù)，類似于版本號(hào)饿凛。

下圖展示了modCount字段會(huì)被ArrayList類中的哪些方法修改狞玛。注意添加元素的add()與addAll()方法并沒有出現(xiàn)，但它們最終調(diào)用了ensureExplicitCapacity()方法涧窒，故也會(huì)修改modCount心肪。

示例代碼中調(diào)用remove(Object)方法后，嵌套的fastRemove()方法會(huì)增加modCount的值纠吴，變成11硬鞍，而expectedModCount的值仍為10，就拋出了CME戴已。

換句話說固该，ArrayList.remove()方法破壞了迭代器內(nèi)維護(hù)的集合修改狀態(tài)。如果在迭代過程中進(jìn)行了任何使modCount改變的操作（不管是單線程還是多線程的環(huán)境下）糖儡，為了防止繼續(xù)迭代下去發(fā)生不可預(yù)見的狀況蹬音，就會(huì)立即失敗并拋出CME，這就是所謂的快速失斝萃妗（fail-fast）機(jī)制著淆。

那么為什么刪除元素"9"就沒問題？這與迭代器的hasNext()方法有關(guān)拴疤。迭代器內(nèi)維護(hù)了指示當(dāng)前元素的游標(biāo)cursor永部，當(dāng)cursor與列表的大小size相同時(shí)，表示沒有下一個(gè)元素呐矾，迭代過程結(jié)束苔埋。刪除掉元素“9”之后，cursor與size的值都是9蜒犯，所以會(huì)退出迭代组橄，next()方法根本不會(huì)執(zhí)行荞膘，只是一種巧合而已。

CME的解決方法

就示例中的刪除操作而言玉工，正確的方式是不調(diào)用容器的remove()方法羽资，而是調(diào)用迭代器本身的remove()方法，即：

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals(random)) {
                iterator.remove();
            }
        }

我們可以參考一下Itr.remove()方法的源碼遵班，它除了調(diào)用ArrayList.remove()方法之外屠升，還做了兩件額外的事：

• 將游標(biāo)cursor重置回上一個(gè)讀取的元素下標(biāo)。
• 將expectedModCount重新賦值成當(dāng)前的modCount狭郑。

這樣在刪除元素的同時(shí)腹暖，也維護(hù)了游標(biāo)位置和修改狀態(tài)，因此能夠安全地繼續(xù)迭代翰萨。如果需要迭代時(shí)添加元素脏答，那么可以利用ArrayList提供的另一種迭代器ListIterator，它的功能更加豐富一點(diǎn)亩鬼，并且機(jī)制幾乎相同殖告，不再贅述。

多線程環(huán)境

文章開頭的例子是在單線程環(huán)境演示的辛孵，但從CME的命名“并發(fā)修改異炒园梗”來(lái)看赡磅，它似乎更偏向于多線程的情況魄缚。由于ArrayList本身就是線程不安全的，因此我們采用線程安全的列表Vector再做一次實(shí)驗(yàn)焚廊，以排除干擾冶匹。

public class CMEExample {
    public static void main(String[] args) {
        Vector<String> vector = new Vector<>();
        for (int i = 1; i <= 20; i++) {
            vector.add(String.valueOf(i));
        }
        String random = String.valueOf(new Random().nextInt(20) + 1);
        System.out.println("Random: " + random);

        Thread threadA = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            while (iterator.hasNext()) {
                String s = iterator.next();
                System.out.println("Thread-A: " + s);
                if (s.equals(random)) {
                    iterator.add(s);
                }
            }
        }, "Thread-A");

        Thread threadB = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            while (iterator.hasNext()) {
                System.out.println("Thread-B: " + iterator.next());
            }
        }, "Thread-B");

        threadA.start();
        threadB.start();
    }
}

這個(gè)示例創(chuàng)建了有20個(gè)元素的Vector與兩個(gè)線程。線程A遍歷該Vector咆瘟，并從中隨機(jī)選擇一個(gè)元素嚼隘，使用安全的ListIterator.add()方法再插入一個(gè)相同的元素；線程B則只做遍歷袒餐。其輸出如下：

Random: 16
Thread-A: 1
Thread-A: 2
Thread-A: 3
Thread-B: 1
Thread-B: 2
Thread-B: 3
Thread-B: 4
Thread-B: 5
Thread-A: 4
Thread-A: 5
Thread-A: 6
Thread-A: 7
Thread-B: 6
Thread-A: 8
Thread-A: 9
Thread-A: 10
Thread-A: 11
Thread-A: 12
Thread-A: 13
Thread-A: 14
Thread-A: 15
Thread-A: 16
Thread-B: 7
Thread-A: 17
Thread-A: 18
Thread-A: 19
Thread-A: 20
Exception in thread "Thread-B" java.util.ConcurrentModificationException
    at java.util.Vector$Itr.checkForComodification(Vector.java:1210)
    at java.util.Vector$Itr.next(Vector.java:1163)
    at me.lmagics.CMEExample.lambda$main$1(CMEExample.java:37)
    at java.lang.Thread.run(Thread.java:748)

可見飞蛹，CME與容器本身線程安全與否并沒有關(guān)系。在這種情況下灸眼，當(dāng)線程A添加元素之后卧檐，線程A中迭代器的expectedModCount會(huì)隨著modCount更新，但線程B中迭代器的expectedModCount并不會(huì)更新焰宣，進(jìn)而拋出CME霉囚。

要解決多線程CME問題，可以考慮對(duì)迭代過程加鎖匕积，確保多個(gè)線程不會(huì)同時(shí)遍歷列表盈罐，即：

        Thread threadB = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            synchronized (vector) {
                while (iterator.hasNext()) {
                    System.out.println("Thread-B: " + iterator.next());
                }
            }
        }, "Thread-B");

我們還可以使用并發(fā)容器CopyOnWriteArrayList來(lái)替代普通的ArrayList與Vector榜跌。

CopyOnWriteArrayList（以及其他j.u.c包中的集合）是與快速失敗相反的安全失敗（fail-safe）機(jī)制的典型應(yīng)用盅粪。它會(huì)在寫操作時(shí)將集合復(fù)制一份副本钓葫，在副本上寫數(shù)據(jù)，即COW（copy on write）湾揽，寫完成之后再將正本的引用指向副本瓤逼，而讀操作直接在正本上進(jìn)行。這種讀寫分離的方法使得它不會(huì)拋出CME库物，之后有時(shí)間的話霸旗，也會(huì)詳細(xì)地閱讀它的源碼。

fail-safe的容器比起fail-fast固然安全了很多戚揭，但是由于每次寫都要復(fù)制诱告，時(shí)間和空間的開銷都更高，因此只適合讀多寫少的情景民晒。在寫入時(shí)精居，為了盡量保證效率，也應(yīng)盡量做批量插入或刪除潜必，而不是單條操作靴姿。并且它的正本和副本有可能不同步，因此無(wú)法保證讀取的是最新數(shù)據(jù)磁滚，這也是CAP理論中一致性（consistency）與可用性（availability）矛盾的體現(xiàn)佛吓。

The End

晚安晚安（但是凌晨有全鏈路壓測(cè)，希望窩的流式計(jì)算任務(wù)們能挺過去垂攘，bless

順便维雇，今晚終于下定決心升級(jí)Catalina了，為毛下載這么慢呢……

最后與Mojave合影留念（