Java源碼分析 深入探討Iterator模式
Java.util包中包含了一系列重要的集合類。本文將從分析源碼入手，深入研究一個集合類的內部結構，以及遍歷集合的迭代模式的Java源碼實現內幕。
下面我們先簡單討論一個根接口Collection，然后分析一個抽象類AbstractList和它的對應Iterator接口，并仔細研究迭代子模式的實現原理。
本文討論的Java源碼版本是JDK 1.4.2，因為JDK 1.5在Java.util中使用了很多泛型代碼，為了簡化問題，所以我們還是討論1.4版本的代碼。
集合類的根接口Collection
Collection接口是所有集合類的根類型。它的一個主要的接口方法是：
boolean add(Object c)
add()方法將添加一個新元素。注意這個方法會返回一個boolean，但是返回值不是表示添加成功與否。仔細閱讀doc可以看 到，Collection規(guī)定：如果一個集合拒絕添加這個元素，無論任何原因，都必須拋出異常。這個返回值表示的意義是add()方法執(zhí)行后，集合的內容 是否改變了（就是元素有無數量，位置等變化），這是由具體類實現的。即：如果方法出錯，總會拋出異常；返回值僅僅表示該方法執(zhí)行后這個 Collection的內容有無變化。
類似的還有：
- boolean addAll(Collection c);
- boolean remove(Object o);
- boolean removeAll(Collection c);
- boolean remainAll(Collection c);
Object[] toArray()方法很簡單，把集合轉換成數組返回。Object[] toArray(Object[] a)方法就有點復雜了，首先，返回的Object[]仍然是把集合的所有元素變成的數組，但是類型和參數a的類型是相同的，比如執(zhí)行：
String[] o = (String[])c.toArray(new String[0]);
得到的o實際類型是String[]。
其次，如果參數a的大小裝不下集合的所有元素，返回的將是一個新的數組。如果參數a的大小能裝下集合的所有元素，則返回的還是a，但a的內容用集合的元素來填充。尤其要注意的是，如果a的大小比集合元素的個數還多，a后面的部分全部被置為null。
***一個最重要的方法是iterator()，返回一個Iterator（迭代子），用于遍歷集合的所有元素。
用Iterator模式實現遍歷集合
Iterator模式是用于遍歷集合類的標準訪問方法。它可以把訪問邏輯從不同類型的集合類中抽象出來，從而避免向客戶端暴露集合的內部結構。
例如，如果沒有使用Iterator，遍歷一個數組的方法是使用索引：
- for(int i=0; i<array.size();
- i++) { ... get(i) ... }
而訪問一個鏈表（LinkedList）又必須使用while循環(huán)：
- while((e=e.next())!=null)
- { ... e.data() ... }
以上兩種方法客戶端都必須事先知道集合的內部結構，訪問代碼和集合本身是緊耦合，無法將訪問邏輯從集合類和客戶端代碼中分離出來，每一種集合對應一種遍歷方法，客戶端代碼無法復用。
更恐怖的是，如果以后需要把ArrayList更換為LinkedList，則原來的客戶端代碼必須全部重寫。
為解決以上問題，Iterator模式總是用同一種邏輯來遍歷集合：
- for(Iterator it = c.iterater();
- it.hasNext(); ) { ... }
奧秘在于客戶端自身不維護遍歷集合的"指針"，所有的內部狀態(tài)（如當前元素位置，是否有下一個元素）都由Iterator來維護，而這個Iterator由集合類通過工廠方法生成，因此，它知道如何遍歷整個集合。
客戶端從不直接和集合類打交道，它總是控制Iterator，向它發(fā)送"向前"，"向后"，"取當前元素"的命令，就可以間接遍歷整個集合。
首先看看Java.util.Iterator接口的定義：
- public interface Iterator
- { boolean hasNext();
- Object next(); void remove(); }
依賴前兩個方法就能完成遍歷，典型的代碼如下：
- for(Iterator it = c.iterator();
- it.hasNext(); )
- { Object o = it.next();
- // 對o的操作... }
在JDK1.5中，還對上面的代碼在語法上作了簡化：
// Type是具體的類型，如String。 for(Type t ： c) { // 對t的操作... }
每一種集合類返回的Iterator具體類型可能不同，Array可能返回ArrayIterator，Set可能返回 SetIterator，Tree可能返回TreeIterator，但是它們都實現了Iterator接口，因此，客戶端不關心到底是哪種 Iterator，它只需要獲得這個Iterator接口即可，這就是面向對象的威力。
Iterator源碼剖析
讓我們來看看AbstracyList如何創(chuàng)建Iterator。首先AbstractList定義了一個內部類（inner class）：
private class Itr implements Iterator { ... }
而iterator()方法的定義是：
- public Iterator iterator()
- { return new Itr(); }
因此客戶端不知道它通過Iterator it = a.iterator();所獲得的Iterator的真正類型。
現在我們關心的是這個申明為private的Itr類是如何實現遍歷AbstractList的：
- private class Itr implements Iterator
- { int cursor = 0;
- int lastRet = -1;
- int expectedModCount = modCount; }
Itr類依靠3個int變量（還有一個隱含的AbstractList的引用）來實現遍歷，cursor是下一次next()調用時元素的位置，***次調用next()將返回索引為0的元素。lastRet記錄上一次游標所在位置，因此它總是比cursor少1。
變量cursor和集合的元素個數決定hasNext()：
- public boolean hasNext()
- { return cursor != size(); }
方法next()返回的是索引為cursor的元素，然后修改cursor和lastRet的值：
- public Object next() { checkForComodification();
- try { Object next = get(cursor);
- lastRet = cursor++;
- return next;
- } catch(IndexOutOfBoundsException e)
- { checkForComodification();
- throw new NoSuchElementException(); } }
expectedModCount表示期待的modCount值，用來判斷在遍歷過程中集合是否被修改過。AbstractList包含一個 modCount變量，它的初始值是0，當集合每被修改一次時（調用add，remove等方法），modCount加1。因此，modCount如果不 變，表示集合內容未被修改。
Itr初始化時用expectedModCount記錄集合的modCount變量，此后在必要的地方它會檢測modCount的值：
- final void checkForComodification()
- { if
- (modCount != expectedModCount)
- throw new ConcurrentModificationException(); }
如果modCount與一開始記錄在expectedModeCount中的值不等，說明集合內容被修改過，此時會拋出ConcurrentModificationException。
這個ConcurrentModificationException是RuntimeException，不要在客戶端捕獲它。如果發(fā)生此異常，說明程序代碼的編寫有問題，應該仔細檢查代碼而不是在catch中忽略它。
但是調用Iterator自身的remove()方法刪除當前元素是完全沒有問題的，因為在這個方法中會自動同步expectedModCount和modCount的值：
- public void remove()
- { ... AbstractList.this.remove(lastRet);
- ...
- // 在調用了集合的remove()方法之后重新設置了expectedModCount：
- expectedModCount = modCount; ... }
要確保遍歷過程順利完成，必須保證遍歷過程中不更改集合的內容（Iterator的remove()方法除外），因此，確保遍歷可靠的原則是只在一個線程中使用這個集合，或者在多線程中對遍歷代碼進行同步。
***給個完整的示例：
- Collection c = new ArrayList();
- c.add("abc"); c.add("xyz");
- for(Iterator it = c.iterator();
- it.hasNext(); ) { String s = (String)it.next();
- System.out.println(s); }
如果你把***行代碼的ArrayList換成LinkedList或Vector，剩下的代碼不用改動一行就能編譯，而且功能不變，這就是針對抽象編程的原則：對具體類的依賴性最小。
【編輯推薦】
