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