Java, Android 開發(fā)也有段時(shí)間了，當(dāng)初為了早點(diǎn)學(xué) Android，Java 匆匆了解個(gè)大概就結(jié)束了，基礎(chǔ)不夠扎實(shí)。
雖然集合框架經(jīng)常用，但是一直沒有仔細(xì)看看原理，僅止于會(huì)用，不知道為什么要這么做。
這段時(shí)間就開始 Java 集合的源碼學(xué)習(xí)。
Java 提供的 集合類都在 Java.utils 包下，其中包含了很多 List, Set, Map, Queue… 它們的關(guān)系如下面這張類圖所示：
可以看到，Java 集合主要分為兩類：Collection 和 Map. 而 Collection 又繼承了 Iterable< E > 接口，Iterable 接口內(nèi)只有一個(gè) iterator 方法，返回一個(gè) 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 是一個(gè)很古老的迭代器，有兩個(gè)方法：
- hasMoreElements() //是否還有元素
- nextElement() //返回下一個(gè)元素
Enumeration 的實(shí)現(xiàn)類會(huì)生成一系列子元素，比如 StringTokenizer；通過 Enumeration 的上述兩個(gè)方法可以用來遍歷它實(shí)現(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());
}
運(yùn)行結(jié)果：
Enumeration 接口早在 JDK 1.0 時(shí)就推出了，當(dāng)時(shí)比較早的容器比如 Hashtable, Vector 都使用它作為遍歷工具。
那 Enumeration 為什么會(huì)被廢棄呢？
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è)計(jì)沒有考慮全，只有兩個(gè)方法，而且名字還太長了 - -。 后來在 JDK 1.2 推出了 Iterator 替代它的功能。雖然 Enumeration 在 JDK 1.5 后增加了泛型的應(yīng)用，依舊大勢(shì)已去。
Iterator
Iterator 是一個(gè)集合上的迭代器，用來替代 Enumeration 進(jìn)行遍歷、迭代。
它 和 Enumeration 有什么不同呢？
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)用者在遍歷過程中語法正確地刪除元素。
注意這個(gè) [語法正確]，事實(shí)上我們?cè)谑褂?Iterator 對(duì)容器進(jìn)行迭代時(shí)如果修改容器 可能會(huì)報(bào) ConcurrentModificationException 的錯(cuò)。官方稱這種情況下的迭代器是 fail-fast 迭代器。
fail-fast 與 ConcurrentModificationException
以 ArrayList 為例，在調(diào)用迭代器的 next，remove 方法時(shí)：
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 方法時(shí)都會(huì)比較 expectedModCount 和 modCount 是否相等，如果不相等就會(huì)拋出 ConcurrentModificationException ，也就是成為了 fail-fast。
而 modCount 在 add, clear, remove 時(shí)都會(huì)被修改：
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，它們的功能和名字一樣，在寫入時(shí)會(huì)創(chuàng)建一個(gè) copy，然后在這個(gè) copy 版本上進(jìn)行修改操作，這樣就不會(huì)影響原來的迭代。不過壞處就是浪費(fèi)內(nèi)存。
方法二：
使用 Collections.synchronizedList 加 同步鎖，不過這樣有點(diǎn)粗暴。
可能得方法三（待考究，目前我還沒搞清楚）：
在學(xué)習(xí) ListView 中的觀察者模式 時(shí)，我注意到 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()，所以在修改元素時(shí)會(huì)檢查(元素的)變化并拋出 ConcurrentModificationException。
在從任何 Collection中刪除對(duì)象時(shí)總要使用 Iterator 的remove 方法， for-each 循環(huán)只是標(biāo)準(zhǔn) Iterator 代碼標(biāo)準(zhǔn)用法之上的一種語法糖（syntactic sugar）而已。
差點(diǎn)忘了 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());
}
對(duì)比而言，后者客戶端代碼與具體集合類型耦合性弱，復(fù)用性更強(qiáng)。缺點(diǎn)就是無法獲取指定的元素，只能挨個(gè)遍歷。
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./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./2014/04/for-each-loop-puzzle-in-java-example.html
|
