Java迭代器原理

1迭代器模式

迭代器是一種設計模式，這種模式用于順序訪問集合對象的元素，不需要知道集合對象的底層表示。

一般實現方式如下：（來自）

public interface Iterator {public boolean hasNext();public Object next();
}

public interface Container {public Iterator getIterator();
}

public class NameRepository implements Container {public String names[] = {"Robert" , "John" ,"Julie" , "Lora"};@Overridepublic Iterator getIterator() {return new NameIterator();}private class NameIterator implements Iterator {int index;@Overridepublic boolean hasNext() {if(index < names.length){return true;}return false;}@Overridepublic Object next() {if(this.hasNext()){return names[index++];}return null;}        }
}

public class IteratorPatternDemo {public static void main(String[] args) {NameRepository namesRepository = new NameRepository();for(Iterator iter = namesRepository.getIterator(); iter.hasNext();){String name = (String)iter.next();System.out.println("Name : " + name);}     }
}

一般情況，我們自己開發時很少自定義迭代器，因為java本身已經把迭代器做到內部中了

2Java中的迭代器

（1）Iterator接口

package java.util;import java.util.function.Consumer;public interface Iterator<E> {/**
     * 如果迭代器又更多的元素，返回true。* 換句話說，如果next方法返回一個元素而不是拋出一個異常，則返回true。
     */   boolean hasNext();//返回迭代器中的下一個元素，如果沒有，則拋出NoSuchElementException異常
    E next();/**
     * 從底層集合中刪除該迭代器返回的最后一個元素（可選操作）。每執行一次next方法這個方法只能被調用1次。* 如果在迭代過程中，除了調用此方法之外，任何其他方法修改基礎集合，則迭代器的行為是不確定的。 * 默認實現是拋出一個UnsupportedOperationException異常，不執行其他操作。 * 如果每次調用該方法前next方法沒有執行，則拋出IllegalStateException異常。
     */default void remove() {throw new UnsupportedOperationException("remove");}/**
     * @since 1.8（函數編程）。 * 對每個剩余元素執行給定的操作，直到所有元素都被處理或動作拋出異常為止。  * 如果指定了該順序，則按迭代順序執行操作。動作拋出的異常被傳遞給調用者。 * 如果action為null，則拋出NullPointerException
     */default void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);while (hasNext())action.accept(next());}
}

首先，Iterator接口是屬于java.util包的。然后里面只有4個方法（用法介紹請看注釋）。

forEachRemaining方法是Java8函數編程新加入的。作用是對前游標之后的每個元素進行處理（沒有返回值），具體怎么處理根據傳入的函數。這項里操作使得迭代器更加靈活，操作粒度更加細致。

補充：default關鍵字可以讓接口中的方法可以有默認的函數體，當一個類實現這個接口時，可以不用去實現這個方法，當然，這個類若實現這個方法，就等于子類覆蓋了這個方法，最終運行結果符合Java多態特性。（Java8的新特性）

類注釋：

/*** An iterator over a collection.  {@code Iterator} takes the place of {@link Enumeration} in the Java Collections Framework.  Iterators* differ from enumerations in two ways:** <ul>*      <li> Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.*      <li> Method names have been improved.* </ul>** <p>This interface is a member of the <a href="{@docRoot}/../technotes/guides/collections/index.html">Java Collections Framework</a>.*/

Iterator是集合上的迭代器。在Java集合框架中Iterator用來替代Enumeration，Iterator與Enumeration有以下兩點區別：

Iterator允許調用者通過定于語義良好的迭代器刪除底層集合中的元素。
方法名稱已得到改進。

這個接口是Java集合框架的成員。除了如上兩點不同外，Java8版本Iterator還加入了函數式編程。

（2）Iterable接口

package java.lang;// 實現此接口，允許對象成為“for-each loop”語句的目標。
public interface Iterable<T> {
    // 返回類型為 T元素的迭代器。Iterator<T> iterator();/*** @since 1.8
     * 對Iterable的每個元素執行給定的操作，直到所有元素都被處理或動作引發異常。 
     * 除非實現類另有規定，否則按照迭代的順序執行操作（如果指定了迭代順序）。 動作拋出的異常被轉發給調用者。
     * 拋出NullPointerException - 如果指定的動作為空*/default void forEach(Consumer<? super T> action) {Objects.requireNonNull(action);for (T t : this) {action.accept(t);}}/*** @since 1.8
     * 在Iterable描述的元素上創建一個Spliterator。Spliterator繼承了迭代器的fail-fast屬性。
     * */default Spliterator<T> spliterator() {return Spliterators.spliteratorUnknownSize(iterator(), 0);}
}

Java集合包最常用的有Collection和Map兩個接口的實現類。Map的實現類迭代器是內部實現的，而Collection繼承了Iterable接口。

這里以ArrayList為例，梳理一下Iterator的工作流程。

ArrayList是Collection的子類，而Collection又實現了Iterable接口，Iterable接口里面有iterator()方法（該方法返回一個迭代器對象）。所以，ArrayList（或其父類）也必須實現iterator()方法。

iterator()方法返回一個Iterator對象，而前文中Iterator是個接口。我們不能不知道具體用哪個實現類也不能直接new接口，所以我們找到其直接父類AbstractList，查看iterator()到底如何實現的：

 public Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E> {// Index of element to be returned by subsequent call to next.int cursor = 0;/*** Index of element returned by most recent call to next or* previous.  Reset to -1 if this element is deleted by a call* to remove.*/int lastRet = -1;/*** The modCount value that the iterator believes that the backing* List should have.  If this expectation is violated, the iterator* has detected concurrent modification.*/int expectedModCount = modCount;public boolean hasNext() {return cursor != size();}public E next() {checkForComodification();try {int i = cursor;E next = get(i);lastRet = i;cursor = i + 1;return next;} catch (IndexOutOfBoundsException e) {checkForComodification();throw new NoSuchElementException();}}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {AbstractList.this.remove(lastRet);if (lastRet < cursor)cursor--;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException e) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}

這里是通過內部類實現了Iterator接口，然后再將其實例對象返回。

原理很簡單，每調用一次next方法，先返回當前游標指向位置的值，然后游標往下移動一位，直到游標數值等于list的size。

而在ArrayList類里面又提供了一個實現版本：

    /*** An optimized version of AbstractList.Itr*/private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;Itr() {}public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;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();}}@Override@SuppressWarnings("unchecked")public void forEachRemaining(Consumer<? super E> consumer) {Objects.requireNonNull(consumer);final int size = ArrayList.this.size;int i = cursor;if (i >= size) {return;}final Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length) {throw new ConcurrentModificationException();}while (i != size && modCount == expectedModCount) {consumer.accept((E) elementData[i++]);}// update once at end of iteration to reduce heap write trafficcursor = i;lastRet = i - 1;checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}

next方法很好理解，和父類大概是一個意思。remove方法是調用ArrayList.this.remove(lastRet)實現：

public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}