转载

Java中的迭代器

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

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

循环和迭代

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

1.基于数组下标的「循环」
for(int i=0; i < len; i ++) …
2.基于对集合的「遍历」
for(String s : strs) …

这两种方是都是通过「循环」的方式对元素集合中的内容逐一进行「遍历」，本质上是做同样的事情。但是第二种方式是一种语法糖，只有满足可以「迭代」的对象才能使用该语法，幸运的是在 Java 中， Collection 已经实现了 Iterat 接口，这就使得我们可以对任何一个子类进行 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;
        lastRet = -1;
        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();
}

该方法在 Itr 的 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);
        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;
    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);
            }else{
                System.out.println(str);
            }
        }
}

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

HashIterator

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

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;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return 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的链表
        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) // 否则这里会报错
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null; // 保证不能连续调用多次remove方法
        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(); }
}