為什麼需要疊代器Iterator？

疊代器是一種模式，它可以使得對於序列類型的數據結構的遍歷行為與被遍歷的對象分離，即我們無需關心該序列的底層結構是什麼樣子的。只要拿到這個對象,使用疊代器就可以遍歷這個對象的內部。這麼說到底是什麼意思呢。比如我們已經了解了ArrayList和LinkedList集合的內部結構，那我們也就了解了它們的api的用途，就知道

arrayList.get(i)可以獲取到元素也可以通過arrayList.remove()來刪除元素。那現在有一個以前沒有見過的集合UnkownCollection,如果要遍歷它，我們首先想到的就是無查詢該集合的API,那去查api也就相當於了解去了解結構了呀，之所以無法在不知道API或內部結構的時候獲取元素是因為訪問集合元素的邏輯與集合本身耦合度太高了，無法將訪問邏輯從集合類和客戶端中分離出來。那麼疊代器就是為了將訪問邏輯從集合類與客戶端代碼分離而出現的。

什麼是疊代器呢？

疊代器我們可以簡單的理解為遍歷。是一個遍歷各類容器裡面的所有對象的標準。由於疊代器總是用同一種邏輯來遍歷集合，因此只要該集合內部實現了疊代器就可以在不知道API或者集合內部結構的情況下通過疊代器遍歷該集合的元素。

用ArrayList為例:我們對比一下用普通的for循環和疊代器之間的分別：

普通for循環:

 ArrayList<String> arrayList=new ArrayList<>(); arrayList.add("hello"); arrayList.add("how are you"); arrayList.add("I'm ok"); //這裡就需要了解arrayList的api和內部結構 for(int i=0;i<arrayList.size();i++){ String string=arrayList.get(i); }

使用疊代器：

ArrayList<String> arrayList=new ArrayList<>();arrayList.add("hello");arrayList.add("how are you");arrayList.add("I'm ok");Iterator<String> iterator=arrayList.iterator();while (iterator.hasNext()){String string=iterator.next();}

因為在java中疊代器提供一個標準化的接口：

public interface Iterator<E> {//如果有更多的元素則返回true boolean hasNext();//返回下一個元素，如果沒有下一個元素則會拋出NoSuchElementException E next();//如果當前疊代器不支持remove操作則拋出UnsupportedOperationException//如果next方法還沒有被調用或是在remove 方法調用之後再調用next 方法會拋出IllegalStateException異常 default void remove() { throw new UnsupportedOperationException("remove"); }}

大多數情況下我們一般只需要使用next(),hasNext()兩個方法即可完成元素疊代。

在ArrayList中Iterator的實現

其中Itr是Arraylist的內部類

 private class Itr implements Iterator<E> { int cursor; //下個返回元素的位置 int lastRet = -1; // 上一個返回元素的位置; 如果是-1則一個表示沒有這個元素 //這個關於快速失敗機制的實現，稍後會有講解 int expectedModCount = modCount; //如果下一個可返回元素位置不等於list的size（內部類可訪問外部類的成員） public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor;//如果下一個元素的位置大於size則拋出NoSuchElementException if (i >= size) throw new NoSuchElementException(); //獲取外部類ArrayList實例中的數據 Object[] elementData = ArrayList.this.elementData; //快速失敗機制 if (i >= elementData.length) throw new ConcurrentModificationException(); //下一個可訪問的元素位置+1 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 = lastRet;//給上一個訪問元素復原 lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } //快速失敗機制的實現 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

這個源碼比較簡單易懂。

我們可以根據上面總結一下：

疊代器Iterator內部最終操作的也是ArrayList的數組和方法
hasNext()通過curor判斷將要被訪問的元素是否存在
next()返回的正在被訪問的元素，同時會保存該元素的下標指向lastRet，而cursor會指向下一下未被訪問的元素。
remove()移除後數組需要移動，同時cursor指向需要更新為lastRet,因為lastRet此時代表著往前移動的元素。

快速失敗（fast-fail）機制

剛剛上面有說

 int expectedModCount = modCount;//快速失敗機制的實現 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

在next和remove中都會調用這個checkForComodification這個方法。這樣做是為什麼呢？在上面我們看到我們通過 ArrayList的疊代器遍曆元素的時候此時為調用next(),其內部還是用的ArrayList.this.elementData。

 Object[] elementData = ArrayList.this.elementData;

疊代器會先獲取整個數組對象，然後進行取捨操作，但是在使用iterator的同時，假設我們又去操作調用了ArrayList本身的方法比如ArrayList.remove(index),那麼elementData數組的元素就會發生變化，而疊代器也要通過hasNext()方法判斷，正好調用next方法，但是數據發生了變化而造成了數據不一致的問題。那下面通過一個例子說明一下問題：

 ArrayList<String> arrayList=new ArrayList<>(); arrayList.add("hello"); arrayList.add("how are you"); arrayList.add("I'm ok"); Iterator<String> iterator=arrayList.iterator(); boolean shouldDelete=true; while (iterator.hasNext()){ String string=iterator.next(); if(shouldDelete){ shouldDelete=!shouldDelete; arrayList.remove(2); } }

運行結果：

拋出異常

這就是我們的快速失敗機制。

我們什麼時候拋出ConcurrentModificationException呢？

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

就是每次在疊代器調用next()和remove()的時候都會先調用checkForComodification()方法，其中modCount是ArrayList中的成員變量。會次ArrayList在調用add(),remove(),clear(),ensureCapacity()這些會修改數據結構的方法中都會使modCount++。在獲取疊代器的時候會把modCount賦值給疊代器的expectedModCount變量。此時modCount與expectedModCount肯定相等，在疊代元素的過程中如果ArrayList調用自身方法使集合發生變化，那麼modCount肯定會變，此時modCount與expectedModCount肯定會不相等。在疊代過程中，只要發現modCount!=expectedModCount，則說明結構發生了變化也就沒有必要繼續疊代元素了。此時會拋出ConcurrentModificationException，終止疊代操作。這就是java JDK的常用的集合中的快速失敗機制。

理解快速失敗機制(fast-fail機制)

我們大概了解了快速失敗機制的執行原理。重新整理一下快速失敗機制，"快速失敗"即fail-fast,它是java集合的一種錯誤檢測機制。當多錢程對集合進行結構上的改變或者集合在疊代元素時直接調用自身方法改變集合結構而沒有通知疊代器時，有可能會觸發fast-fail機制並拋出異常。需要注意一點，有可能觸發fast-fail機制而不是肯定。觸發時機是在疊代過程中，集合的結構發生了變化而此時疊代器並不知道或者還沒來得及反應時便會產生fail-fast機制。這裡再次強調，疊代器的快速失敗行為無法得到保證，因為一般來說，不可能對是否出現不同步並發修改或者自身修改做出任何硬性保證。快速失敗疊代器會盡最大努力拋出 ConcurrentModificationException。

而我們把上面拋出異常的例子用疊代器的remove替換一下：

 ArrayList<String> arrayList=new ArrayList<>(); arrayList.add("hello"); arrayList.add("how are you"); arrayList.add("I'm ok"); //這裡就需要了解arrayList的api和內部結構 Iterator<String> iterator=arrayList.iterator(); boolean shouldDelete=true; while (iterator.hasNext()){ String string=iterator.next(); if(shouldDelete){ shouldDelete=!shouldDelete; //arrayList.remove(2); iterator.remove(); } }

這個時候程序運行就是正常的。並不會拋出異常。

在ArrayList中得到疊代器方法：

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

這是一個疊代器模式（游標模式）的應用

看到什麼自己不懂的記下來。