Java疊代器Iterator

之前我們實作了疊代器模式，很多程式設計語言實際上已經内置了疊代器類，比如Java就為我們實作了疊代器Iterator。我們首先來看Iterator中的源碼。

通過JDK源碼我們發現Iterator是一個接口，包含三個方法：hasNext、next、remove。

1 package java.util;
 2 
 3 public interface Iterator<E> {
 4 
 5     /**
 6     *如果疊代器中還有元素則傳回true
 7     */
 8     boolean hasNext();
 9 
10     /**
11     *傳回疊代器中的下一個元素
12     */
13     E next();
14 
15     /**
16     *通過疊代器删除處于集合中最底層的元素
17     */
18     void remove();
19 }

Iterator是一個接口，那如何來建立一個執行個體呢？要記住，疊代器和集合類的關系非常緊密，我們可以通過集合類來建立一個Iterator執行個體，ArrayList、LinkedList、Vector都有對它的實作。我們來看ArrayList是如何建立一個Iterator疊代器執行個體的。在此之前我們先來看看集合和疊代器之間的繼承關系。

由于集合的關系相對來說比較複雜，在此我們主要看注釋部分，通過閱讀源代碼會發現ArrayList覆寫了AbstractList抽象類中的iterator方法并聲稱效果更佳，而LinkedList則沒有覆寫，由此可判斷ArrayList的iterator方法比LinkedList中的iterator方法更為高效。

我們直接看ArrayList裡中實作的iterator方法。

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

從代碼來看它傳回類一個Itr的對象執行個體，順着代碼看看這個Itr類是什麼。

1 private class Itr implements Iterator<E> {
 2     int cursor;       // 傳回下一個元素的索引
 3     int lastRet = -1; // 傳回最後一個元素的索引；如果沒有則傳回-1
 4     int expectedModCount = modCount;
 5 
 6     public boolean hasNext() {
 7         return cursor != size;
 8     }
 9 
10     @SuppressWarnings("unchecked")
11     public E next() {
12         checkForComodification();
13         int i = cursor;
14         if (i >= size)
15             throw new NoSuchElementException();
16         Object[] elementData = ArrayList.this.elementData;
17         if (i >= elementData.length)
18             throw new ConcurrentModificationException();
19         cursor = i + 1;
20         return (E) elementData[lastRet = i];
21     }
22 
23     public void remove() {
24         if (lastRet < 0)
25             throw new IllegalStateException();
26         checkForComodification();
27 
28         try {
29             ArrayList.this.remove(lastRet);
30             cursor = lastRet;
31             lastRet = -1;
32             expectedModCount = modCount;
33         } catch (IndexOutOfBoundsException ex) {
34             throw new ConcurrentModificationException();
35         }
36     }
37 
38     final void checkForComodification() {
39         if (modCount != expectedModCount)
40             throw new ConcurrentModificationException();
41     }
42 }

原來Itr它是一個私有的内部類，實作Iterator接口。

我們來一行一行讀。在第3行中有一個modCount變量。跟蹤這個變量，發現這個變量有點意思：

protected transient int modCount = 0;

發現有一個“transient”關鍵字，查閱資料發現這個關鍵字的意思是：表示一個域不是該對象序列化的一部分。意思是在對象被序列化時不包括這個變量，至于為什麼要這麼做呢，我們可以留下一個疑問。（JDk源碼注釋中是這麼說的：The modCount value that the iterator believes that the backing List should have. If this expectation is violated, the iterator has detected concurrent modification.英語太次隻能讀懂最後一句：如果這個期望是可見性的，那麼這個疊代器會檢測到有一個并發的修改。猜測是和并發多線程相關。）

hasnext的實作較為簡單：

1 public boolean hasNext() {
2     return cursor != size;　　//下一個元素的索引是否等于ArrayList的大小
3 }

next的實作：

public E next() {
    checkForComodification();　　//檢查是否并發修改
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();　　//索引大于ArrayList大小抛出異常
    Object[] elementData = ArrayList.this.elementData;　　//後面實際是在取ArrayList中的資料
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

在next方法中我們看到有一個checkForCommodification方法：

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

看來這個modCount變量确實是和并發相關，如果expectedModCount和modCount這兩個值不同，則抛出目前正在并發修改的異常。

最後我們來看remove方法的實作：

public void remove() {
    if (lastRet < 0)　　//這個地方格外注意，不能在未調用next時直接調用remove方法，必須在remove調用前調用next方法，将通過cursor索引值将其值賦給lastRet
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

在remove方法中我們要格外注意，在第一句是檢測lastRet是否小于0，我們初始化了lastRet變量-1的值，這意味着，如果我們如果建立完Iterator執行個體後直接調用remove方法會抛出一個IllegalStateException異常，那怎麼才能正确調用呢？那就是在調用remove方法前先調用next方法，此時lastReturn通過cursor索引被指派，這個時候才能正确使用remove方法。同時它也會調用checkForCommodification方法做并發修改檢測。其實我們可以看到JDK源碼之是以寫到好，是因為它每個方法都做了很多的檢測，以確定在盡量多的場景下準确無誤地運作。今天關于Java的疊代器就通過JDK源碼簡單介紹，通過對源碼的閱讀能夠加深我們的了解，這還隻是簡單的閱讀，并沒有做很深的了解。最後，我們以為一個Iterator的例子結尾。

1 package day_29_iterator;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Iterator;
 5 import java.util.List;
 6 
 7 /**
 8  * @author turbo
 9  *
10  * 2016年9月29日
11  */
12 public class Main {
13 
14     /**
15      * @param args
16      */
17     public static void main(String[] args) {
18         List list = new ArrayList();
19         list.add(1);
20         list.add(2);
21         Iterator iterator = list.iterator();
22         while (iterator.hasNext()){
23             System.out.println(iterator.next());
24         }
25     }
26 
27 }

不積跬步，無以至千裡；不積小流，無以成江海。