Java, Android 開發(fā)也有段時間了，當(dāng)初為了早點學(xué) Android，Java 匆匆了解個大概就結(jié)束了，基礎(chǔ)不夠扎實。

雖然集合框架經(jīng)常用，但是一直沒有仔細(xì)看看原理，僅止于會用，不知道為什么要這么做。

這段時間就開始 Java 集合的源碼學(xué)習(xí)。

點擊查看 Java 集合框架深入理解 系列， - ( ゜- ゜)つロ 乾杯~

Java 提供的 集合類都在 Java.utils 包下，其中包含了很多 List, Set, Map, Queue… 它們的關(guān)系如下面這張類圖所示：

可以看到，Java 集合主要分為兩類：Collection 和 Map. 而 Collection 又繼承了 Iterable< E > 接口，Iterable 接口內(nèi)只有一個 iterator 方法，返回一個 Iterator 迭代器:

public interface Iterable<T> {    /**    * Returns an {@link Iterator} for the elements in this object.    *    * @return An {@code Iterator} instance.    */    Iterator<T> iterator();}

本篇文章將介紹 Iterator 迭代器。 在介紹 Iterator 之前不得不提一下被它替代的 Enumeration< E >:

Enumeration< E >

public interface Enumeration<E> {/** * Returns whether this {@code Enumeration} has more elements. * * @return {@code true} if there are more elements, {@code false} otherwise. * @see #nextElement */    public boolean hasMoreElements();/** * Returns the next element in this {@code Enumeration}. * * @return the next element.. * @throws NoSuchElementException * if there are no more elements. * @see #hasMoreElements */    public E nextElement();}

Enumeration 是一個很古老的迭代器，有兩個方法：

• hasMoreElements() //是否還有元素
• nextElement() //返回下一個元素

Enumeration 的實現(xiàn)類會生成一系列子元素，比如 StringTokenizer；通過 Enumeration 的上述兩個方法可以用來遍歷它實現(xiàn)類的元素，比如這樣：

    //StringTokenizer : 切割, Breaks a string into tokens; new code should probably use {@link String#split}.    Enumeration enumeration = new StringTokenizer("A-B-C", "-");    while (enumeration.hasMoreElements()){        System.out.println(enumeration.nextElement());    }

運行結(jié)果：

Enumeration 接口早在 JDK 1.0 時就推出了，當(dāng)時比較早的容器比如 Hashtable, Vector 都使用它作為遍歷工具。

那 Enumeration 為什么會被廢棄呢？

根據(jù)官方文檔:

NOTE: The functionality of this interface is duplicated by the Iterator interface. In addition, Iterator adds an optional remove operation, and has shorter method names. New implementations should consider using Iterator in preference to Enumeration.

可以大膽猜一下，應(yīng)該是當(dāng)初設(shè)計沒有考慮全，只有兩個方法，而且名字還太長了 - -。 后來在 JDK 1.2 推出了 Iterator 替代它的功能。雖然 Enumeration 在 JDK 1.5 后增加了泛型的應(yīng)用，依舊大勢已去。

Iterator

Iterator 是一個集合上的迭代器，用來替代 Enumeration 進(jìn)行遍歷、迭代。

它 和 Enumeration 有什么不同呢？

根據(jù)官方文檔:

Iterators differ from enumerations in two ways:

• Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
• Method names have been improved.

哈哈首先是名字縮短了，看來大家都懶得輸入那么長的方法名。 其次是 允許調(diào)用者在遍歷過程中語法正確地刪除元素。

注意這個 [語法正確]，事實上我們在使用 Iterator 對容器進(jìn)行迭代時如果修改容器 可能會報 ConcurrentModificationException 的錯。官方稱這種情況下的迭代器是 fail-fast 迭代器。

fail-fast 與 ConcurrentModificationException

以 ArrayList 為例，在調(diào)用迭代器的 next，remove 方法時：

    public E next() {        if (expectedModCount == modCount) {            try {                E result = get(pos + 1);                lastPosition = ++pos;                return result;            } catch (IndexOutOfBoundsException e) {                throw new NoSuchElementException();            }        }        throw new ConcurrentModificationException();    }    public void remove() {        if (this.lastPosition == -1) {            throw new IllegalStateException();        }        if (expectedModCount != modCount) {            throw new ConcurrentModificationException();        }        try {            AbstractList.this.remove(lastPosition);        } catch (IndexOutOfBoundsException e) {            throw new ConcurrentModificationException();        }        expectedModCount = modCount;        if (pos == lastPosition) {            pos--;        }        lastPosition = -1;    }

可以看到在調(diào)用迭代器的 next，remove 方法時都會比較 expectedModCount 和 modCount 是否相等，如果不相等就會拋出 ConcurrentModificationException ，也就是成為了 fail-fast。

而 modCount 在 add, clear, remove 時都會被修改：

public boolean add(E object) {    //...    modCount++;    return true;}public void clear() {    if (size != 0) {        //...        modCount++;    }}public boolean remove(Object object) {    Object[] a = array;    int s = size;    if (object != null) {        for (int i = 0; i < s; i++) {            if (object.equals(a[i])) {                //...                modCount++;                return true;            }        }    } else {        for (int i = 0; i < s; i++) {            if (a[i] == null) {                //...                modCount++;                return true;            }        }    }    return false;}

因此我們知道了 fail-fast 即 ConcurrentModificationException 出現(xiàn)的原因，怎么解決呢？

方法一:

用 CopyOnWriteArrayList，ConcurrentHashMap 替換 ArrayList， HashMap，它們的功能和名字一樣，在寫入時會創(chuàng)建一個 copy，然后在這個 copy 版本上進(jìn)行修改操作，這樣就不會影響原來的迭代。不過壞處就是浪費內(nèi)存。

方法二：

使用 Collections.synchronizedList 加 同步鎖，不過這樣有點粗暴。

可能得方法三（待考究，目前我還沒搞清楚）：

在學(xué)習(xí) ListView 中的觀察者模式 時，我注意到 DataSetObservable 的 notifyChanged 方法中有如下注釋：

public void notifyChanged() {    synchronized(mObservers) {        // since onChanged() is implemented by the app, it could do anything, including        // removing itself from {@link mObservers} - and that could cause problems if        // an iterator is used on the ArrayList {@link mObservers}.        // to avoid such problems, just march thru the list in the reverse order.        for (int i = mObservers.size() - 1; i >= 0; i--) {            mObservers.get(i).onChanged();        }    }}

to avoid such problems, just march thru the list in the reverse order

為了避免影響 ArrayList 迭代，倒序處理。 待考究，目前我還沒搞清楚。

不過意外的發(fā)現(xiàn)了，原來 for-each 的循環(huán)內(nèi)部也是使用了 Iterator 來遍歷Collection，它也調(diào)用了 Iterator.next()，所以在修改元素時會檢查(元素的)變化并拋出 ConcurrentModificationException。

在從任何 Collection中刪除對象時總要使用 Iterator 的remove 方法， for-each 循環(huán)只是標(biāo)準(zhǔn) Iterator 代碼標(biāo)準(zhǔn)用法之上的一種語法糖（syntactic sugar）而已。

差點忘了 Iterator 的使用

所有 Collection 的子類都有 iterator() 方法來獲得 Iterator，通過 Iterator 的標(biāo)準(zhǔn)操作方法，可以讓我們不必關(guān)心具體集合的類型，從而避免向客戶端暴露出集合的內(nèi)部結(jié)構(gòu)。

不使用 Iterator 遍歷集合是這樣的：

    for(int i=0; i<集合的大小;i++){          // ...     } 

使用 Iterator 遍歷集合是這樣的：

    Iterator iterator = list.iterator();    while (iterator.hasNext()){        System.out.println(iterator.next());    }

對比而言，后者客戶端代碼與具體集合類型耦合性弱，復(fù)用性更強(qiáng)。缺點就是無法獲取指定的元素，只能挨個遍歷。

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/Enumeration.html

https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

http://javahungry.blogspot.com/2014/04/fail-fast-iterator-vs-fail-safe-iterator-difference-with-example-in-java.html

http://www.cnblogs.com/dolphin0520/p/3933551.html

http://blog.csdn.net/chenssy/article/details/38151189

http://blog.csdn.net/mazhimazh/article/details/17730517

http://javarevisited.blogspot.jp/2014/04/for-each-loop-puzzle-in-java-example.html