從集合的遍歷看迭代器模式

??做為后臺開發(fā)人員，集合類的知識是我們必須要掌握的！因為在日常工作中使用得非常非常的多，相關的知識點在面試中也是高頻出現(xiàn)的。我們先看下下面幾個的問題：

1.有哪些方式可以對集合進行遍歷？?
2.迭代器的內(nèi)部實現(xiàn)原理是什么？?
3.非線程安全集合在循環(huán)遍歷時刪除元素有什么陷阱？

??帶著上面的問題，今天我們就通過ArrayList來分析分析！

遍歷集合的方式

??我們先創(chuàng)建一個ArrayList，并且放入幾個元素，然后看看常用的遍歷方式：

 1List?list?=?new?ArrayList<>();
 2list.add("L1");
 3list.add("L2");
 4list.add("L3");
 5
 6//1、for循環(huán)遍歷
 7for?(int?i?=?0;?i? 8???System.out.println(list.get(i));
 9}
10
11//2、foreach循環(huán)遍歷
12for?(String?item?:?list)?{
13???System.out.println(item);
14}
15
16//3、Iterator遍歷
17Iterator?iterator?=?list.iterator();
18while?(iterator.hasNext())?{
19???System.out.println(iterator.next());
20}
21
22//4、forEach遍歷
23list.forEach(s?->?System.out.println(s));

??方式1不需要太多的說明，而方式2就的底層實現(xiàn)就是方法3！所以本文重點說下方式3、4的實現(xiàn)，而要弄懂方式3、4就必須得了解迭代器！

迭代器遍歷

繼承關系圖

??為什么我們可以通過 list.iterator() 的方式進行遍歷呢？Iterator又是什么呢？我們先看下ArrayList的繼承關系圖。

Iterable

??我們能看到ArrayList最頂層的接口是Iterable，Iterable我們?nèi)绻且弥形睦斫饽蔷褪恰?strong style="font-size:inherit;color:inherit;">可迭代的、有迭代能力的”！也就是說如果我們的類實現(xiàn)了Iterable接口，那這個類就具備了迭代的能力！我們看下接口定義的方法：

??這個接口共三個方法，spliterator方法是并行遍歷用的，我們今天不看！我們分析下iterato和forEach方法分別實現(xiàn)了什么樣的功能！

iterator()方法

??我們通過迭代器遍歷就是先調(diào)用了list.iterator()方法，這個方法返回的是一個Iterator類型。我們看下iterator()方法的實現(xiàn)，其實現(xiàn)在抽象類AbstractList中

1public?Iterator?iterator()?{
2????????return?new?Itr();
3????}

??這個方法返回了一個名為Itr的內(nèi)部類，這個內(nèi)部類是Iterator接口的實現(xiàn)類。也就是說我們在使用迭代器遍歷list的時候調(diào)用的hasNext和next方法都是在Itr里面實現(xiàn)的！我們看下Itr的實現(xiàn)：

 1private?class?Itr?implements?Iterator<E>?{
 2????/**
 3?????*?Index?of?element?to?be?returned?by?subsequent?call?to?next.
 4?????*/
 5????int?cursor?=?0;
 6
 7????/**
 8?????*?Index?of?element?returned?by?most?recent?call?to?next?or
 9?????*?previous.??Reset?to?-1?if?this?element?is?deleted?by?a?call
10?????*?to?remove.
11?????*/
12????int?lastRet?=?-1;
13
14????/**
15?????*?The?modCount?value?that?the?iterator?believes?that?the?backing
16?????*?List?should?have.??If?this?expectation?is?violated,?the?iterator
17?????*?has?detected?concurrent?modification.
18?????*/
19????int?expectedModCount?=?modCount;
20
21????public?boolean?hasNext()?{
22????????//只要當前指針不等于size，會返回true
23????????return?cursor?!=?size();
24????}
25
26????public?E?next()?{
27????????//檢查modCount
28????????checkForComodification();
29????????try?{
30????????????//獲取當前需要遍歷的元素
31????????????//將lastRet指針的值設置為cursor
32????????????//將cursor指針值+1
33????????????//返回當前需要遍歷的元素
34????????????int?i?=?cursor;
35????????????E?next?=?get(i);
36????????????lastRet?=?i;
37????????????cursor?=?i?+?1;
38????????????return?next;
39????????}?catch?(IndexOutOfBoundsException?e)?{
40????????????checkForComodification();
41????????????throw?new?NoSuchElementException();
42????????}
43????}
44
45????public?void?remove()?{
46????????if?(lastRet?0)
47????????????throw?new?IllegalStateException();
48????????checkForComodification();
49
50????????try?{
51????????????AbstractList.this.remove(lastRet);
52????????????if?(lastRet?53????????????????cursor--;
54????????????lastRet?=?-1;
55????????????expectedModCount?=?modCount;
56????????}?catch?(IndexOutOfBoundsException?e)?{
57????????????throw?new?ConcurrentModificationException();
58????????}
59????}
60
61????final?void?checkForComodification()?{
62????????if?(modCount?!=?expectedModCount)
63????????????throw?new?ConcurrentModificationException();
64????}
65}

??這個類定義了一個指針變量cursor來標記隨后需要遍歷的對象，lastRet標記上一個已經(jīng)調(diào)用的對象。每次調(diào)用next方法都會設置cursor++。并且每次遍歷之前都會檢查modCount，對于modeCount我們下面會細講！總的來說，這段代碼還是比較簡單的，也沒有太多要說明的。到這里我們就明白了迭代器的方式遍歷集合對象的內(nèi)部實現(xiàn)了！

forEach方法

??我們通過list.forEach方法遍歷的代碼看起來是最簡約的！可能很多人都沒有使用過這種方式，因為這種方式是jdk1.8中才提供的，因此很多開發(fā)者習慣了for或者迭代器的方式去遍歷！我們先看下forEach在ArrayList中的實現(xiàn)：

 1public?void?forEach(Consumersuper?E>?action)?{
 2????Objects.requireNonNull(action);
 3????final?int?expectedModCount?=?modCount;
 4????@SuppressWarnings("unchecked")
 5????final?E[]?elementData?=?(E[])?this.elementData;
 6????final?int?size?=?this.size;
 7????for?(int?i=0;?modCount?==?expectedModCount?&&?i? 8????????action.accept(elementData[i]);
 9????}
10????if?(modCount?!=?expectedModCount)?{
11????????throw?new?ConcurrentModificationException();
12????}
13}

??代碼依然非常簡單！forEach方法的入?yún)⑹且粋€Consumer 類型，這個類型被@FunctionalInterface 注解標記，我們翻譯為函數(shù)式接口！這也是jdk1.8新增的與Lambda表達式相關特性，有興趣的可以自己去了解下！方法內(nèi)部實現(xiàn)也是使用的for進行遍歷，然后調(diào)用Consumer的accept方法。這里每次遍歷之也會檢查modCount，那modCount是什么呢？為什么每次遍歷之前都需要檢查modCount呢？

快速失敗機制

??我們先看一段代碼

 1List?list?=?new?ArrayList<>();
 2list.add("L1");
 3list.add("L2");
 4list.add("L3");
 5list.add("L4");
 6
 7for?(String?item?:?list)?{
 8???if?("L1".equals(item))?{
 9??????list.remove(item);
10???}
11}

??運行結果會是什么呢？稍有開發(fā)經(jīng)驗的你應該知道，這里會拋ConcurrentModificationException 異常！為什么呢？這是java中fail-fast機制（快速失敗機制）！如果一個線程在遍歷集合，而另外一個線程對線程進行增加或者刪除元素，jdk則認為這是不合法的而拋異常，因為ArrayList是非線程安全的！雖然上面代碼中只有一個線程，但是同時進行遍歷和刪除就會拋出異常。

??fail-fast的實現(xiàn)就是通過modCount變量，這個變量定義在抽象類AbstractList中，每次對集合元素進行操作如添加元素、移除元素、排序時都會控制modCount++。

??我們前面說過foreach的方式就是迭代器的方式實現(xiàn)的，因此在遍歷的時候先調(diào)用Iterator的hasNext方法判斷是否還有元素，再調(diào)用next方法進行遍歷!在調(diào)用next方法之前會記錄當前modCount的值存儲到expectedModCount變量中，然后每次調(diào)用next方法的時候都會先檢查modCount與expectedModCount是否一致，如果不一致直接拋出異常，相關的代碼在講Itr類的時候已經(jīng)貼過了，我們這里只再看一下checkForComodification方法的實現(xiàn)！

1final?void?checkForComodification()?{
2????if?(modCount?!=?expectedModCount)
3????????throw?new?ConcurrentModificationException();
4}

??那遍歷集合的時候?qū)υ夭僮鞯恼_方式是什么呢？我們看代碼

 1List?list?=?new?ArrayList<>();
 2list.add("L1");
 3list.add("L2");
 4list.add("L3");
 5list.add("L4");
 6
 7Iterator?iterator?=?list.iterator();
 8while?(iterator.hasNext())?{
 9???if?("L1".equals(iterator.next()))?{
10??????iterator.remove();
11???}
12}

??注意我們調(diào)用的是Iterator的remove方法而不是ArrayList類的remove方法！那Iterator的remove方法內(nèi)部是怎么做到能遍歷時刪除元素的呢？我們看下源碼實現(xiàn)：

 1public?void?remove()?{
 2????if?(lastRet?0)
 3????????throw?new?IllegalStateException();
 4????checkForComodification();
 5
 6????try?{
 7????????ArrayList.this.remove(lastRet);
 8????????cursor?=?lastRet;
 9????????lastRet?=?-1;
10????????expectedModCount?=?modCount;
11????}?catch?(IndexOutOfBoundsException?ex)?{
12????????throw?new?ConcurrentModificationException();
13????}
14}

??我們重點看expectedModCount = modCount;這行，每次調(diào)用remove時都會重置expectedModCount變量，因此等到下一輪循環(huán)的時候判斷expectedModCount和modCount時就為true了。這也就能在遍歷的同時進行元素的刪除了。