Collection迭代器的底层原理

Iterator Source Code

JDK17中迭代器源码


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

/**
 * An optimized version of AbstractList.Itr.
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount; // for fast-fail

    // Prevent creating a synthetic constructor
    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();
        }
    }

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

Iterator Methods Explanation

在调用迭代器方法时，内部会创建一个 Itr 实例，其中包含三个成员变量：

int cursor; // 下一个要返回元素的索引
int lastRet = -1; // 上一次返回元素的索引；如果没有则是 -1
int expectedModCount = modCount; // 记录外部集合操作的次数

cursor 相当于指针，lastRet 用于追踪迭代器最后更新的元素的索引。

expectedModCount 用于检测并发修改异常（ConcurrentModificationException）。

hasNext 方法


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

调用 hasNext 方法时，会判断当前指针（cursor）是否等于集合的长度（size）。如果相等，则表示没有更多元素可以迭代，返回 false；否则返回 true。

next 方法


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];
}

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

调用 next 方法时：

首先调用 checkForComodification 方法检查操作次数是否发生了变化。如果发生了变化（即 modCount != expectedModCount），则抛出 ConcurrentModificationException 异常（通常是由于对集合进行了增删操作导致的）。
然后判断要取的元素是否超过或等于集合长度。如果满足条件，则抛出 NoSuchElementException 或 ConcurrentModificationException 异常。
更新 cursor（加1），并更新 lastRet 变量的值为更新前的索引值。
返回当前元素。

Avoiding ConcurrentModificationException

如何避免并发修改异常（ConcurrentModificationException）

为了避免在迭代过程中发生 ConcurrentModificationException 异常，可以使用迭代器自带的修改方法，如 remove 方法。该方法会在执行时自动调整内部状态，以确保不会抛出异常。

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 方法时：

首先检查 lastRet 是否小于 0。如果是，则抛出 IllegalStateException，因为没有上一个返回的元素可以删除。
然后调用 checkForComodification 检查是否有并发修改。
尝试从列表中删除 lastRet 索引处的元素。
关键步骤：将 cursor 设置为 lastRet 的值，这相当于将指针回退到上一个元素的位置。
重置 lastRet 变量为 -1，表示当前没有最后更新的元素。
同步 expectedModCount 和 modCount 的值，确保它们一致，从而避免下一次调用 next() 或其他方法时抛出 ConcurrentModificationException。