從`ArrayList`中了解Java的迭代器-有解無憂

目錄

什么是迭代器

迭代器的設計意義

ArrayList對迭代器的實作

增強for回圈和迭代器

參考鏈接

什么是迭代器

Java中的迭代器——Iterator是一個位于java.util包下的介面，這個介面里宣告了三個重要的方法hasNext()、next()、remove()，下面看看Iterator的宣告

public interface Iterator<E> {
    // 判斷集合中是否有下一個元素
    boolean hasNext();
	// 獲取集合中的下一個元素
    E next();
    // 從集合中移除迭代器回傳的最后一個元素
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

值得提一下的是remove()方法，remove()方法在介面中使用了default關鍵字修飾，這是JDK1.8的一個新特性——介面的方法可以擁有方法體（即默認實作），當你使用一個類去實作Iterator的時候，如果你不去重寫它的remove()方法的話，再呼叫remove()就會去呼叫介面里的默認實作，此時程式會拋出UnsupportedOperationException例外，

設計迭代器的意義

首先，迭代器這個東西是針對集合設計的，我們知道，List家族，Set家族，Map家族他們的底層設計都是不一樣的，那么在遍歷它們的時候，方式也自然不會一樣，既然大家都有遍歷的需求，那么就可以把這個需求統一一下，設計一個介面來把這些方法抽象出來，于是Iterator這個介面就應運而出，迭代器的設計初衷是：提供一種方法對一個容器物件中的各個元素進行訪問，而又不暴露該物件容器的內部細節，

`ArrayList`對迭代器的實作

很多集合都實作了Iterator介面，實作了屬于自己的迭代器，在本篇文章中我們以ArrayList中的迭代器為例講述ArrayList是如何實作自己的迭代器的，

基本使用

想一想，你平時在使用迭代器去遍歷ArrayList的時候是怎么做的，是不是像下面這樣

// 首先有個ArrayList
ArrayList<Object> list = new ArrayList<>();
// 然后獲取到迭代器
Iterator<Object> iterator = list.iterator();
// 再開始遍歷ArrayList，使用hasNext()判斷ArrayList中是否有下一個元素
while (iterator.hasNext()){
    // 如果ArrayList中有下一個元素，就使用next()方法獲取下一個元素
    Object e = iterator.next();
    if ("條件".equals(e)){
        // 如果元素e滿足某種條件就使用remove()洗掉該元素
        iterator.remove();
    }
}

`Iterable`介面

看看下面獲取迭代器的這段代碼

// 獲取迭代器
Iterator<Object> iterator = list.iterator();

可以看到 list.iterator()給我們回傳了一個迭代器物件，那么這個iterator()方法是個什么樣的方法呢，通過查看原始碼可以發現，iterator()方法是來自于介面Iterable的一個方法，這個Iterable的宣告是這樣的

public interface Iterable<T> {
    Iterator<T> iterator();
    
    // 其他方法...
}

其中，iterator()方法回傳的就是一個Iterator迭代器，實作了Iterable介面的類我們稱它為可迭代的類，該類的物件我們稱之為可迭代物件，

`Itr`類及其和介面`Iterator`的關系

我們接著再看看iterator()方法的原始碼

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

你會發現發現iterator()方法只是給我們new了一個Itr類的物件，然后就把這個物件的參考回傳給我們了，那我們就順藤摸瓜看看Itr()這個構造方法，看看這個Itr類到底是個啥玩意，

通過查看Itr類的原始碼我們可以發現Itr類是ArrayList中的一個私有的內部類，并且這個類實作了前面說的Iterator介面，下面看下Itr類的具體原始碼

private class Itr implements Iterator<E> {
    int cursor;       // 下一個要回傳的元素的索引
    int lastRet = -1; // 回傳的最后一個元素的索引；如果沒有這個值就是-1
    int expectedModCount = modCount; // 期望ArrayList的結構被改變（新增，洗掉元素都會改變ArrayList的結構）的次數，初始值等于modCount

    // 構造方法
    Itr() {}

    // hasNext方法的具體實作
    public boolean hasNext() {
        return cursor != size;
    }

    // next方法的具體實作
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = https://www.cnblogs.com/lmw97/p/ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    // remove方法的具體實作
    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) {
        // ...
    }

    // 檢查在使用迭代器遍歷ArrayList的同時是否有其他的操作改動了ArrayList的結構
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

下面來逐一解釋Itr里的成員變數和方法

`Itr`類中的成員變數

`cursor`

int cursor;       // 下一個要回傳的元素的索引

由于cursor是一個int型別的成員變數，所以他的初始值是0，也就是說，一開始，下一個要回傳的元素的索引是0，實際上就是ArrayList的第一個元素，

`lastRet`

int lastRet = -1; // 回傳的最后一個元素的索引；如果沒有這個值就是-1

lastRet這個變數存的是迭代器上一個回傳的元素的索引，一開始這個值是-1，也就是說還沒有使用next()方法回傳ArrayList的下一個元素時，這個值就是-1，當我們呼叫next方法回傳ArrayList的下一個元素后，可以從next()方法的原始碼里看到cursor會+1，然后lastRet被賦值為cursor加一之前的值，所以lastRet里存的就是上一個回傳的元素的索引，

`expectedModCount`

// 期望ArrayList的結構被改變（新增，洗掉元素都會改變ArrayList的結構）的次數，初始值等于modCount
int expectedModCount = modCount;

expectedModCount從字面意思上來看，表示期望被改變的次數，然后它的默認值是modCount，這個modCount是何許人也？我們點進去看看，原來它是ArrayList的父類AbstractList的成員變數，它長這樣

protected transient int modCount = 0;

modCount它記錄了整個List的結構被改變的次數，我們常用的add()方法，remove()方法都會改動List的結構，相應的，這些方法被呼叫一次后，modCount就會+1，用以記錄List的結構被改變的次數，

`Itr`類中的方法

`hasNext()`

public boolean hasNext() {
    return cursor != size;
}

hasNext()的實作其實很簡單，就是判斷下一個元素的索引是否和ArrayList的大小相等，不相等的話，就說明ArrayList中還有下一個元素相等的話，就說明遍歷已經走到盡頭了，ArrayList中沒有下一個元素了，

`checkForComodification()`

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

checkForComodification()方法的作用就是檢查迭代器對ArrayList進行遍歷的程序中是否有其他的操作對ArrayList本身的結構進行了修改，要知道這種修改操作是不被允許的，如果你這么做了，會導致迭代器在遍歷的時候獲取或者洗掉的元素并不是你想要的那個元素，甚至會發生索引越界的現象，那么設計者是如何避免這種不當的情況呢？這就要用到前面說到的expectedModCount和modCount這兩個變數了，還記得嗎，在new一個Itr物件的時候，expectedModCount的初始值就是modCount的值，前面說了，modCount記錄了ArrayList本身結構被改變的次數，那么只要在我們使用迭代器遍歷ArrayList的時候，這個值沒有發生變化，這說明這期間沒有其他的操作來改變ArrayList的結構（比如洗掉、新增元素），迭代器的這次遍歷是安全的，但是與之相反的，在迭代器遍歷ArrayList期間，modCount的值發生了變化（有其他的操作改變了ArrayList的結構），modCount的值不等于expectedModCount的值了，這就說明迭代器的這次遍歷是不安全，這次遍歷應該被停止掉，于是，當modCount != expectedModCount的時候，程式拋出了一個ConcurrentModificationException例外，終止掉了迭代器的這次遍歷，

`next()`

@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = https://www.cnblogs.com/lmw97/p/ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

梳理一下next()方法的執行程序：

進方法之后，呼叫checkForComodification()方法檢查下本次遍歷是否是安全的，如果是安全的，執行第2步，否則checkForComodification()方法里會拋出ConcurrentModificationException例外，阻止這次遍歷的進行
宣告一個區域變數i，i的值就是cursor的值
判斷i（cursor）的值是不是大于或者等于ArrayList的大小，如果是的，就表明迭代器已經遍歷完了整個ArrayList了，按道理來說，不應該再呼叫next()方法獲取下一個值了（因為已經沒有下一個值了），于是這種情況下，程式就拋出了一個NoSuchElementException例外，從這里也可以看到，對于一個已經被迭代器遍歷完的集合，如果你還試圖去獲取下一個元素，程式會拋出NoSuchElementException例外，
宣告了一個Object[]型別的成員變數elementData，這個陣列實際上指向了ArrayList內部用來存盤元素的陣列，就是下面這個
```
transient Object[] elementData; // 非私有以簡化嵌套類訪問
```
判斷cursor的值是否大于elementData的大小，如果是，拋出ConcurrentModificationException例外
cursor的值+1
將lastRet的值設定為i的值
回傳ArrayList的索引為i的元素

`remove()`

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();
    }
}

remove()方法的程序沒啥好說的，值得注意的是：

remove()本質上呼叫的是ArrayList的remove(int index)方法
呼叫完ArrayList的remove(int index)方法之后，modCount的值會發生變化（+1），這時再將+1后的modCount賦值給expectedModCount以保證接下來的遍歷順利進行下去，

總結：在試用迭代器遍歷集合時，如果想要洗掉集合中的元素，必須使用迭代器提供的remove()方法，否則程式將拋出ConcurrentModificationException例外，

增強for回圈和迭代器

背景

增強for回圈是JDK1.5以后出來的新特性，是一種高級的for回圈，用來方便遍歷陣列和集合的，

遍歷陣列

下面先用增強for回圈遍歷下陣列看下，看下示例代碼

public  static void testArray(){
    String[] s = {"a", "b", "c", "d"};
    
    for (String e : s) {
        System.out.println(e);
    }
}

輸出結果和普通for回圈是一樣的

a
b
c
d

讓我們來看下上面這段示例代碼的反編譯結果，看看編譯器實際執行的代碼是怎么樣的

public static void testArray() {
    String[] s = new String[]{"a", "b", "c", "d"};
    String[] var1 = s;
    int var2 = s.length;

    for(int var3 = 0; var3 < var2; ++var3) {
        String e = var1[var3];
        System.out.println(e);
    }
}

可以很明顯的看到，如果你是用增強for回圈來遍歷陣列的話，實際上編譯器執行的代碼還是使用普通for回圈來遍歷這個陣列，

遍歷可迭代物件

這里仍然以ArrayList舉例說明，我們看下使用增強for回圈來遍歷可迭代物件的示例代碼

public static void testList(){
    List<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");

    for (String e : list) {
        System.out.println(e);
    }
}

這段代碼的輸出結果同上

a
b
c
d

同樣的，讓我們來看看這個示例代碼的反編譯結果

public static void testList() {
    List<String> list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    Iterator var1 = list.iterator();

    while(var1.hasNext()) {
        String e = (String)var1.next();
        System.out.println(e);
    }
}

可以很明顯的看到，當增強for回圈遍歷的是一個可迭代的物件時，實際上是使用迭代器來遍歷這個可迭代物件的，

使用總結

從上面的兩個示例代碼的反編譯結果來看，我們不難得出下面這幾個結論

當增強for回圈遍歷的是一個陣列的時候，實際上還是使用的普通for回圈來遍歷
當增強for回圈遍歷的是一個可迭代的物件的時候，實際上使用的是迭代器來遍歷這個物件
在增強for回圈遍歷可迭代物件的時候，不可以執行洗掉元素的操作，否則程式會拋出java.util.ConcurrentModificationException例外
增強for回圈遍一個物件的時候，這個物件不可以為null，否則程式會拋出NullPointerException例外

參考鏈接

[迭代器]https://www.cnblogs.com/zhuyeshen/p/10956822.html

[迭代器]https://www.cnblogs.com/zyuze/p/7726582.html

[增強for回圈]https://blog.csdn.net/baidu_25310663/article/details/80222534

[增強for回圈]https://www.cnblogs.com/miaoxingren/p/9413320.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/191466.html

標籤：Java

上一篇：Mockito如何mock一條鏈式呼叫

下一篇：spring動態代理的理解(java)

從`ArrayList`中了解Java的迭代器

什么是迭代器

設計迭代器的意義

ArrayList對迭代器的實作

基本使用

Iterable介面

Itr類及其和介面Iterator的關系

Itr類中的成員變數

cursor

lastRet

expectedModCount

Itr類中的方法

hasNext()

checkForComodification()

next()

remove()