Java中的迭代器

我们都用过for-each来处理集合或数组，我们也用过Iterator对象的hasNext和next来完成同样的工作，它们都是迭代的方式，本质上是做同一件事情。

但Java中的迭代的原理和知识点还是很值得我们去细细品味的，本文试图对其进行分析。

循环和迭代

在 Java 中我们一般用一下两种方式进行循环：

1.基于数组下标的「循环」

for(int i=0; i < len; i ++) …

2.基于对集合的「遍历」

for(String s : strs) …

这两种方是都是通过「循环」的方式对元素集合中的内容逐一进行「遍历」，本质上是做同样的事情。但是第二种方式是一种语法糖，只有满足可以「迭代」的对象才能使用该语法，幸运的是在Java中， Collection 已经继承了 Iterable 接口，这就使得我们可以对任何一个子类进行 for 循环的迭代，如 ArrayList 、LinkedList 等。

Colection 接口的类声明如下：

public interface Collection<E> extends Iterable<E>

Iteratable 接口的定义如下：

public interface Iterable<T> {
    
    // 对元素集合进行迭代的一个迭代器Iterator
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

迭代器其实目的也是为了「循环」，更严谨一些，是为了「遍历」，你可以把迭代器看成比普通循环更高级别的工具，普通循环能搞定的迭代器也能搞定，普通循环搞不定的迭代器还能搞定，并且使用迭代器比普通循环效率更高。

对于这种 for 循环的方式依次访问元素我们称之为「迭代」——iteration
对于ArrayList 、LinkedList 这些集合我们称之为「可迭代的」——iterable
对于Iterator 接口的实现类我们称之为「迭代器」——iterator

ArrayList的迭代器实现

modCount

每个集合都有一个 modCount 全局变量，继承自AbstractList，每次对集合中的数据进行增加和删除的时候都会对该变量进行 ++ 操作，也就是说它记录了对元素集合修改的次数。

The number of times this list has been structurally modified. Structural modifications are those

that change the size of the list, or otherwise perturb it in such a fashion that iterations in

progress may yield incorrect results.

This field is used by the iterator and list iterator implementation returned by the iterator and

listIterator methods. If the value of this field changes unexpectedly, the iterator (or list

iterator) will throw a ConcurrentModificationException in response to the next, remove,

previous, set or add operations. This provides fail-fast behavior, rather than non-deterministic

behavior in the face of concurrent modification during iteration.

迭代器很大程度上是依赖它来做安全性校验的，如果元素集合的内容发生了变动则通过该字段「传递」到迭代器中，迭代器通过对这个元素和自身的 expectedModCount 进行比较来做 Fail-Fast 逻辑。

默认只有迭代器自身才能保证 modCount 和 expectedModCount 的一致性，如通过迭代器删除当前迭代位置元素时，会同步修改这两个变量。

我们来分析一下 ArrayList 实现的 Itr 迭代器中的删除操作：

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        // 删除已经迭代到的位置的元素，注意调用的是外层类即元素集合ArrayList的remove方法，内部会改变modCount
        ArrayList.this.remove(lastRet); 
        cursor = lastRet; // cursor回退
        lastRet = -1; // 防止多次连续调用remove方法
        expectedModCount = modCount; // 重新赋值使二者相等
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

再来看一下 ArrayList 的删除方法的实现：

public E remove(int index) {
    rangeCheck(index);

    modCount++; // 增1
    E oldValue = elementData(index);

    int numMoved = size - index - 1; // 后续受影响的元素个数
    if (numMoved > 0)
        // 原地复制，不会重新建立数组
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved); // 将受影响的元素复制到index开始的位置，即都向前移动一位
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

可以看到每次删除元素都会改变全局变量 modCount ，但通过迭代器进行删除则会自动满足验证条件：

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

该方法在 Itrerator 的 next、remove 和 forEachRemaining 方法中都会被调用，所以迭代器的任何「迭代行为」都会严格确认 modCount 的值和迭代器创建时的值是否一致，如果不一致则证明「外部」已经将元素集合的内容进行了增删，破坏了迭代器创建时的「契约」，所以就会通过抛出 ConcurrentModificationException 来快速失败，提示用户代码存在并发修改异常。

由于迭代器本身不处理并发操作，所以方法内都没有锁，如果在第一次检查没问题之后有其他线程修改了集合怎么办？

next方法

public E next() {
    checkForComodification(); // 1
    int i = cursor; // 通过局部变量来操作，防止并发修改全局变量影响结果
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length) // 2
        throw new ConcurrentModificationException();
    cursor = i + 1; // 指向下一个位置
    return (E) elementData[lastRet = i]; // lastRet向后移动一位
}

先在 1 处进行检查，通过后，此时可能发生了并发修改删除了集合中的某些元素，所以还有两个地方需要验证：

如果此时有其他线程删除了集合中的一个元素，导致当前迭代到的位置已经大于集合的大小，即i >= size 则会抛出 NoSuchElementException 异常。
同样还需要校验 i 和集合数组的总长度的关系，如果满足 i >= elementData.length，则会抛出 ConcurrentModificationException。

remove方法

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification(); // 1

    try {
        ArrayList.this.remove(lastRet); // 调用ArrayList的remove方法，内部会变更modCount
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount; // 使条件验证满足
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

先在 1 处进行检查，通过后，此时可能发生了并发修改删除了接种的某些元素，导致 lastRet 位置的数据数组越界，也会抛出 ConcurrentModificationException。

注意由于删除的元素是迭代器的当前位置 cursor ，所以在删除之后需要回退一位，即 cursor = lastRet ，然后对 lastRet = -1 ，而不是 lastRet = lastRet -1 ，这是为什么呢？

如果此时不进行继续迭代，即调用 next 方法，而是再次调用 remove 方法，此时会报错 IllegalStateException ，只有在调用了 next 方法后对 lastRet 重新赋值后才能继续调用 remove 方法。

Java Doc 中对 remove 方法的注释写的很清楚：

Removes from the underlying collection the last element returned by this iterator (optional operation).

This method can be called only once per call to next. The behavior of an iterator is unspecified

if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

Throws:

UnsupportedOperationException - if the remove operation is not supported by this iterator

IllegalStateException - if the next method has not yet been called, or the remove method has already been called after the last call to the next method

forEachRemaining方法

public void forEachRemaining(Consumer<? super E> consumer) {
    Objects.requireNonNull(consumer);
    final int size = ArrayList.this.size;
    int i = cursor; // 赋值给局部变量
    if (i >= size) {
        return;
    }
    final Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length) { // 1
        throw new ConcurrentModificationException();
    }
    while (i != size && modCount == expectedModCount) { // 保证每次处理新元素时都确认集合没有被修改过
        consumer.accept((E) elementData[i++]); // 依次处理后续所有元素
    }
    // update once at end of iteration to reduce heap write traffic
    cursor = i; // i == size
    lastRet = i - 1;
    checkForComodification(); // 再次校验
}

1 处的校验和 next 方法思路一致，即先检查长度是否已经发生变化导致数组会越界，只有在确保数组元素不会越界的前提下，才会对剩余元素依次进行迭代访问。

在每次对剩余的数据迭代时都会对 modCount == expectedModCount 条件进行判断，一旦发现不相等立刻退出 while，并在方法最后再统一做一次校验，如果不满足则抛出 ConcurrentModificationException。

案例分析

为什么下面的输出会是 a b c 呢？难道不是修改了元素内容直接抛异常吗？

public static void main(String[] args){
    List<String> list = new ArrayList<String>();
    //CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");
    Iterator iterator = list.iterator();
    while(iterator.hasNext()){
        String str = (String) iterator.next();
        if(str.equals("d")){
            list.remove(str); // 注意这里用list的remove方法而不是iterator的remove方法，所以cursor没有改变
        }else{
            System.out.println(str);
        }
    }
}

因为在删除 d 的时候 cursor 为4，而集合的 size 也变成了4。所以在次执行 hasNext 方法时就返回为 true 了，循环结束，从而后面的元素也不会输出了。也没有报异常，因为没有调用 next 方法，也没有发生数组越界等问题。

HashIterator

HashMap 提供了三种迭代器，分别是基于键的 KeyIterator ，基于值的 ValueIterator 和基于 Entry 的 EntryIterator 。

注意 HashMap 本身是基于桶和单链表实现的，所以这里的迭代器的实现是基于链表指针来进行集合数据的迭代的。

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount; // 使用HashMap的全局变量进行赋值
        Node<K,V>[] t = table;
        current = next = null;
        index = 0; // 用于标记bucket的索引
        if (t != null && size > 0) { // advance to first entry
            // 初始化next指针为桶中顺序第一个非空的位置的链表的头结点
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null; // 保证指针的next不为null
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next; // 使用局部变量
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        // 如果当前slot的链表已经遍历完毕next为null了，则继续换table中的下一个slot的链表
        // 注意每次都在这里给current进行赋值为当前返回元素的值，ArrayList中使用lastRet来完成同样的任务
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null); // 跳过slot为null的链表
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current; // current必须每次都是通过next方法更换来的新值
        if (p == null) // 否则这里会报错，即防止多个remove操作中间没有调用next方法，破坏迭代器的使用约束
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null; // 保证不能连续调用多次remove方法，类似lastRet=-1
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount; // 保证一致性
    }
}

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

LinkedHashIterator

LinkedHashMap 提供了三种迭代器，分别是基于键的 LinkedKeyIterator ，基于值的 LinkedValueIterator 和基于 Entry 的 LinkedEntryIterator 。注意，LinkedHashMap 是基于 HashMap 实现的，只不过它内部额外又维护了一个双向链表来记录访问顺序 accessOrder 或 插入顺序 insertionOrder ，方便根据这两种情况进行遍历。使用的结构 LinkedHashMap.Entry 结构如下：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

所以它使用了双向链表的数据结构 LinkedHashMap.Entry 来完成迭代器的实现：

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next; // 继承HashMap的Node类
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;

    LinkedHashIterator() {
        next = head; // 从双向链表的head节点开始迭代
        expectedModCount = modCount;
        current = null;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next; // 使用局部变量
        if (modCount != expectedModCount) // fast-fail
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after; // 简单了很多，直接使用当前节点的after设置next
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null; // 需要重新调用nextNode方法来赋值
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().getKey(); }
}

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

通过和 HashIterator 的对比我们发现， LinkedHashIterator 的迭代器写起来简单很多，因为它内部又一个单独的双向链表将所有元素串联起来，不像 HashIterator 需要依次处理 table 数组中的各个单链表。所以，迭代的速度上前者性能更好，因为它只需要迭代n个元素，时间复杂度为 O(n) ，但后者的n其实是 O(capacity + size） 。但因为需要维护额外的数据结构（访问和变更可能都需要重新调整双向链表的结构），所以 LinkedHashMap 的插入和删除性能（虽然都是常数时间）稍微差一点。

同时需要指出的是 Load Factor 和 Initial Capacity 选择比较大的值的时候对 LinkedHashMap 的迭代的影响不大，因为它的迭代次数并不受 capacity 影响。

ListIterator

ListIterator 是一个功能更加强大的迭代器，它不但可以完成基本的迭代读取类型的操作，如 next 、 previous 、 hasNext 、 hasPrevious 等，还能实现更多的写类型的操作，如 add 和 set ，而不是局限于 remove 。它只能用于对各种 List 类型的访问并操作。可以通过调用 listIterator() 方法产生一个指向 List 开始处的 ListIterator 对象，还可以调用 listIterator(n) 方法创建一个一开始就指向列表索引为 n 的元素处的 ListIterator 对象。

public interface ListIterator<E> extends Iterator<E> {
    // Query Operations
    
    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    // Modification Operations

    void remove();

    void set(E e);

    void add(E e);
}

可以看到，它不但支持向前移动 previous 方法，还支持了 add 和 set 方法，比 Iterator 接口扩展了增加元素的操作。

ArrayList 的默认实现是 ListItr 类，它继承了 Itr 类，下面是它的源码：

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0) // 保证移动到最开始的位置后不能再获取previous了
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i; // 回退
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0) // 注意remove和add方法调用之后不可以调用set方法
            throw new IllegalStateException();
        checkForComodification();

        try {
            // 注意set不会更新modCount
            ArrayList.this.set(lastRet, e); // 对lastRet位置的数据进行赋值
            // 故这里无需使得 expectedModCount = modCount
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 注意与next方法的区别，后者只进行cursor的移动，这里还要进行插入新元素
    // 并且让cursor跳过当前的位置，即只能使用previous来访问插入的元素而不能通过next方法
    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e); // 变更了modCount，增加了一个元素，size也++
            cursor = i + 1;
            lastRet = -1; // 不能连续调用add方法
            expectedModCount = modCount; // 保持相等
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

和 Itr 的思路差不多（毕竟是它的子类），但是可以实现「边迭代边增加元素」或者「边迭代边修改元素」的操作，而不是仅仅「边迭代边删除」。

COWIterator

CopyOnWriteArrayList 是 ArrayList 的一个线程安全的变体，其中所有可变操作（ add 、 set 等等）都是通过对底层数组进行一次新的复制来实现的。

该类产生的开销比较大，但是在两种情况下，它非常适合使用：

在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。
当遍历操作的数量大大超过可变操作的数量时。

那么为什么 CopyOnWriterArrayList 可以在这些场景替代 ArrayList 呢？

先来看下一下它的源码：

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    public boolean hasPrevious() {
        return cursor > 0; // previousIndex=cursor-1
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code remove}
     *         is not supported by this iterator.
     */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code set}
     *         is not supported by this iterator.
     */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code add}
     *         is not supported by this iterator.
     */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        Object[] elements = snapshot;
        final int size = elements.length;
        for (int i = cursor; i < size; i++) {
            @SuppressWarnings("unchecked") E e = (E) elements[i];
            action.accept(e);
        }
        cursor = size;
    }
}

可以看到它继承了 ListIterator 接口，不支持 add 、 remove 、 set 等写操作，默认抛出 UnsupportedOperationException 异常。

而在 next 和 previous 方法中也并未对 modCount 进行校验，其实它根本就没有这个变量，因为遍历操作本质上是读操作，读操作是对快照数据进行的操作，而写操作是独立复制了一份新的数据结构，对快照数据无影响，所以无需校验。

既然没有 modCount 那么在变更方法里也不会对这类变量进行操作，以add 方法为例：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 新建一个数组，空间复杂度为n
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

通过加锁使得变更操作串行化，同时通过复制原有数组到新的数组来保证其他正在读取和迭代的操作无需担心它们的数据（快照）会受影响。

任何对 array 在结构上有所改变的操作（add、remove、clear 等），CopyOnWriterArrayList 都会 copy 现有的数据，再在 copy 的数据上修改，这样就不会影响 COWIterator 中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的 copy 也是相当有损耗的。

References

https://segmentfault.com/a/1190000007208388
https://www.baeldung.com/java-linked-hashmap
https://www.baeldung.com/java-hashmap-advanced
https://openjdk.java.net/jeps/180
https://javabypatel.blogspot.com/2015/10/time-complexity-of-hashmap-get-and-put-operation.html
https://stackoverflow.com/questions/4553624/hashmap-get-put-complexity

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

Iterator in Java