迭代對(duì)于我們搞 Java 的來(lái)說絕對(duì)不陌生。我們常常使用 JDK 提供的迭代接口進(jìn)行 Java 集合的迭代。
Iterator iterator = list.iterator();
while(iterator.hasNext()){
String string = iterator.next();
//do something
}
迭代其實(shí)我們可以簡(jiǎn)單地理解為遍歷,是一個(gè)標(biāo)準(zhǔn)化遍歷各類容器里面的所有對(duì)象的方法類,它是一個(gè)很典型的設(shè)計(jì)模式。Iterator 模式是用于遍歷集合類的標(biāo)準(zhǔn)訪問方法。它可以把訪問邏輯從不同類型的集合類中抽象出來(lái),從而避免向客戶端暴露集合的內(nèi)部結(jié)構(gòu)。 在沒有迭代器時(shí)我們都是這么進(jìn)行處理的。如下:
對(duì)于數(shù)組我們是使用下標(biāo)來(lái)進(jìn)行處理的:
int[] arrays = new int[10];
for(int i = 0 ; i < arrays.length ; i++){
int a = arrays[i];
//do something
}
對(duì)于 ArrayList 是這么處理的:
List<String> list = new ArrayList<String>();
for(int i = 0 ; i < list.size() ; i++){
String string = list.get(i);
//do something
}
對(duì)于這兩種方式,我們總是都事先知道集合的內(nèi)部結(jié)構(gòu),訪問代碼和集合本身是緊密耦合的,無(wú)法將訪問邏輯從集合類和客戶端代碼中分離出來(lái)。同時(shí)每一種集合對(duì)應(yīng)一種遍歷方法,客戶端代碼無(wú)法復(fù)用。 在實(shí)際應(yīng)用中如何需要將上面將兩個(gè)集合進(jìn)行整合是相當(dāng)麻煩的。所以為了解決以上問題, Iterator 模式騰空出世,它總是用同一種邏輯來(lái)遍歷集合。使得客戶端自身不需要來(lái)維護(hù)集合的內(nèi)部結(jié)構(gòu),所有的內(nèi)部狀態(tài)都由 Iterator 來(lái)維護(hù)??蛻舳藦牟恢苯雍图项惔蚪坏溃偸强刂?Iterator,向它發(fā)送”向前”,”向后”,”取當(dāng)前元素”的命令,就可以間接遍歷整個(gè)集合。
上面只是對(duì) Iterator 模式進(jìn)行簡(jiǎn)單的說明,下面我們看看 Java 中 Iterator 接口,看他是如何來(lái)進(jìn)行實(shí)現(xiàn)的。
在 Java 中 Iterator 為一個(gè)接口,它只提供了迭代了基本規(guī)則,在 JDK 中他是這樣定義的:對(duì) collection 進(jìn)行迭代的迭代器。迭代器取代了 Java Collections Framework 中的 Enumeration。迭代器與枚舉有兩點(diǎn)不同:
1、迭代器允許調(diào)用者利用定義良好的語(yǔ)義在迭代期間從迭代器所指向的 collection 移除元素。
2、方法名稱得到了改進(jìn)。
其接口定義如下:
public interface Iterator {
boolean hasNext();
Object next();
void remove();
}
其中:
Object next():返回迭代器剛越過的元素的引用,返回值是 Object,需要強(qiáng)制轉(zhuǎn)換成自己需要的類型
boolean hasNext():判斷容器內(nèi)是否還有可供訪問的元素
void remove():刪除迭代器剛越過的元素
對(duì)于我們而言,我們只一般只需使用 next()、hasNext() 兩個(gè)方法即可完成迭代。如下:
for(Iterator it = c.iterator(); it.hasNext(); ) {
Object o = it.next();
//do something
}
前面闡述了 Iterator 有一個(gè)很大的優(yōu)點(diǎn),就是我們不必知道集合的內(nèi)部結(jié)果,集合的內(nèi)部結(jié)構(gòu)、狀態(tài)由 Iterator 來(lái)維持,通過統(tǒng)一的方法 hasNext()、next() 來(lái)判斷、獲取下一個(gè)元素,至于具體的內(nèi)部實(shí)現(xiàn)我們就不用關(guān)心了。但是作為一個(gè)合格的程序員我們非常有必要來(lái)弄清楚 Iterator 的實(shí)現(xiàn)。下面就 ArrayList 的源碼進(jìn)行分析分析。
下面就 ArrayList 的 Iterator 實(shí)現(xiàn)來(lái)分析,其實(shí)如果我們理解了 ArrayList、Hashset、TreeSet 的數(shù)據(jù)結(jié)構(gòu),內(nèi)部實(shí)現(xiàn),對(duì)于他們是如何實(shí)現(xiàn) Iterator 也會(huì)胸有成竹的。因?yàn)?ArrayList 的內(nèi)部實(shí)現(xiàn)采用數(shù)組,所以我們只需要記錄相應(yīng)位置的索引即可,其方法的實(shí)現(xiàn)比較簡(jiǎn)單。
在 ArrayList 內(nèi)部首先是定義一個(gè)內(nèi)部類 Itr,該內(nèi)部類實(shí)現(xiàn) Iterator 接口,如下:
private class Itr implements Iterator<E> {
//do something
}
而 ArrayList 的 iterator() 方法實(shí)現(xiàn):
public Iterator<E> iterator() {
return new Itr();
}
所以通過使用 ArrayList.iterator() 方法返回的是 Itr() 內(nèi)部類,所以現(xiàn)在我們需要關(guān)心的就是 Itr() 內(nèi)部類的實(shí)現(xiàn):
在 Itr 內(nèi)部定義了三個(gè) int 型的變量:cursor、lastRet、expectedModCount。其中 cursor 表示下一個(gè)元素的索引位置,lastRet 表示上一個(gè)元素的索引位置
int cursor;
int lastRet = -1;
int expectedModCount = modCount;
從 cursor、lastRet 定義可以看出,lastRet 一直比 cursor 少一所以 hasNext() 實(shí)現(xiàn)方法異常簡(jiǎn)單,只需要判斷 cursor 和 lastRet 是否相等即可。
public boolean hasNext() {
return cursor != size;
}
對(duì)于 next() 實(shí)現(xiàn)其實(shí)也是比較簡(jiǎn)單的,只要返回 cursor 索引位置處的元素即可,然后修改 cursor、lastRet 即可,
public E next() {
checkForComodification();
int i = cursor; //記錄索引位置
if (i >= size) //如果獲取元素大于集合元素個(gè)數(shù),則拋出異常
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1; //cursor + 1
return (E) elementData[lastRet = i]; //lastRet + 1 且返回cursor處元素
}
checkForComodification() 主要用來(lái)判斷集合的修改次數(shù)是否合法,即用來(lái)判斷遍歷過程中集合是否被修改過。在 Java 提高篇(二一)—–ArrayList 中已經(jīng)闡述了。modCount 用于記錄 ArrayList 集合的修改次數(shù),初始化為 0,,每當(dāng)集合被修改一次(結(jié)構(gòu)上面的修改,內(nèi)部update不算),如 add、remove 等方法,modCount + 1,所以如果 modCount 不變,則表示集合內(nèi)容沒有被修改。該機(jī)制主要是用于實(shí)現(xiàn) ArrayList 集合的快速失敗機(jī)制,在 Java 的集合中,較大一部分集合是存在快速失敗機(jī)制的,這里就不多說,后面會(huì)講到。所以要保證在遍歷過程中不出錯(cuò)誤,我們就應(yīng)該保證在遍歷過程中不會(huì)對(duì)集合產(chǎn)生結(jié)構(gòu)上的修改(當(dāng)然 remove 方法除外),出現(xiàn)了異常錯(cuò)誤,我們就應(yīng)該認(rèn)真檢查程序是否出錯(cuò)而不是 catch 后不做處理。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
對(duì)于 remove() 方法的是實(shí)現(xiàn),它是調(diào)用 ArrayList 本身的 remove() 方法刪除 lastRet 位置元素,然后修改 modCount 即可。
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();
}
}
這里就對(duì) ArrayList 的 Iterator 實(shí)現(xiàn)講解到這里,對(duì)于 Hashset、TreeSet 等集合的 Iterator 實(shí)現(xiàn),各位如果感興趣可以繼續(xù)研究,個(gè)人認(rèn)為在研究這些集合的源碼之前,有必要對(duì)該集合的數(shù)據(jù)結(jié)構(gòu)有清晰的認(rèn)識(shí),這樣會(huì)達(dá)到事半功倍的效果!?。。?/p>