List的疊代器的了解

目錄

目的

List周遊和删除

使用基本的for循環周遊删除

使用Iterator周遊，list進行删除

iterator原理與fail-fast原理

思考

目的

java中List的周遊和删除問題是個老生常談的問題了，似懂非懂的很多，經得住幾個為什麼的很少，本文解釋幾個問題，有助于去貫通List中iterator的原理，fail-fast機制，這兩點懂了可以應付各種周遊和删除的為什麼？

List周遊和删除

使用基本的for循環周遊删除

很多開發人員已經被灌輸了思想，必須使用iterator才可以周遊删除，其實不然，看如下代碼

// 使用基本的for循環删除
    public static void deleteFor() {
        List<String> names = new ArrayList<>();
        names.add("jack");
        names.add("tim");
        names.add("lili");
        names.add("tim");
        names.add("lucy");
        names.iterator();
        String name;
        for (int i = 0; i < names.size(); ++i) {
            System.out.println(name = names.get(i));
            if ("tim".equals(names.get(i))) {
                // 删除後list整體向前移動一位，i後退一位，保證不跳躍
                names.remove(i--);
            }
        }
        System.out.println(names.toString());
    }
           

這種操作不會有問題，隻是要注意避免遊标變量的跳躍現象。

使用Iterator周遊，list進行删除

先看一段代碼，這段代碼我們使用增強for周遊，并且使用List的remove方法删除周遊元素

// 會不會産生想象中的ConcurrentModificationException？為什麼？
public static void deleteStrongFor() {
        List<String> names = new ArrayList<>();
        names.add("jack");
        names.add("tim");
        names.add("lili");
        for (String name : names) {
            System.out.println(name);
            if ("tim".equals(name)) {
                names.remove(name);
            }
        }
        System.out.println(names.toString());
    }
// 會不會産生想象中的ConcurrentModificationException？為什麼？
public static void deleteStrongFor() {
        List<String> names = new ArrayList<>();
        names.add("jack");
        names.add("tim");
        names.add("lili");
        for (String name : names) {
            System.out.println(name);
            if ("lili".equals(name)) {
                names.remove(name);
            }
        }
        System.out.println(names.toString());
    }
           

結果：第一段代碼不會産生異常，第二段代碼會産生異常。

原因：第一段代碼不會産生異常的原理，沒有觸發fail-fast機制，iterator的原理和fail-fast機制不是那麼完美！第二段代碼會産生異常，fail-fast機制生效。

首先看下增強型for循環在編譯後的代碼，借助idea檢視上述代碼片段的.class檔案，發現增強型for編譯後就是使用while和iterator進行周遊的。是以要解釋前面的現象就得分析一下iterator的原理。

public static void deleteStrongFor() {
        List<String> names = new ArrayList();
        names.add("jack");
        names.add("tim");
        names.add("lili");
        Iterator var1 = names.iterator();

        while(var1.hasNext()) {
            String name = (String)var1.next();
            System.out.println(name);
            if ("tim".equals(name)) {
                names.remove(name);
            }
        }

        System.out.println(names.toString());
    }
           

iterator原理與fail-fast原理

具體原理看ArrayList.Iterator的源碼，如下

/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        // 初始化時為0
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        // 初始化為list外部類的modCount
        int expectedModCount = modCount;
        
        Itr() {}
        // 遊标和size不相同則傳回true
        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();
            // 傳回結果之前，遊标移到下一位置，等待下一次hasNext判斷
            cursor = i + 1;
            // 傳回結果之前，lastRet已确認
            return (E) elementData[lastRet = i];
        }

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

            try {
                ArrayList.this.remove(lastRet);
                // 若删除操作，cursor被修改為上一個傳回位置，保證了不跳躍
                cursor = lastRet;
                // next()方法會重置這個lastRet
                lastRet = -1;
                // 欺騙或者說完成fail-fast機制
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
}
           

• iterator中的cursor是下一個next()将要傳回的元素的下标，初始化為0，第一次運作next傳回第一個元素前，就已經移動到第二個元素的下标，就是1，依次類推。
• hasNext的判斷依據 cursor!=size
• iterator中的  expectedModCount标記操作數，與List自身的modCount對比，不一樣則ConcurrentModificationException，expectedModCount的值在獲得list的iterator時初始化為list的modCount，本例中添加三個元素後，兩者的值都為3
• fail-fast機制隻在next和remove中進行判斷

基于以上三點複現兩代碼的必要過程：

第一段代碼

• 删除"tim"元素後，cursor=2，list的size=2，hasNext的結果為false，循環跳出不執行後面的next，是以沒有意料中的異常

第二段代碼

• 删除"tim"元素後，cursor=3，list的size=2，hasNext的結果為true，modCount=4（因為使用的時list的remove方法），expectedModCount=3(因為删除不是使用iterator進行的，expectedModCount不變)
• 由于hasNext為true，進入next方法，顯而易見ConcurrentModificationException出現了

思考

1. fail-fast的設計目的是快速甄别出邏輯上對集合的“并發”操作異常，而不是解決問題。否則使用基本的for可能抛出得是OutofBound之類的異常，出現此類異常時可能要花點時間去探究，fail-fast盡量将這種隐蔽的邏輯漏洞暴露出來，友善解決問題。
2. 其實這種iterator.remove()是不是和基本的for循環中删除i--的機制很像，iterator接口注釋中寫明其第一個優點就是可以一邊周遊，一邊删除，但使用基本for也可以實作。
3. fail-fast機制是否需要進一步加強在hasNext中？說這個的原因是，看下面代碼

将list最後兩個元素都設定為“tim”，那麼在删除時，隻會删除倒數第二個tim, 最後一個留下了，程式也沒有異常，程式員也覺得沒問題，其實還是有邏輯上的問題的。

public static void deleteStrongFor() {
        List<String> names = new ArrayList<>();
        names.add("jack");
        names.add("tim");
        names.add("tim");
        for (String name : names) {
            System.out.println(name);
            if ("tim".equals(name)) {
                // 這是個錯誤的示例
                // 隻删除了倒數第二個tim，程式依然正常運作
                names.remove(name);
            }
        }
        System.out.println(names.toString());
    }
           

歡迎批評指正，共同進步！