迭代器设计模式

迭代器设计模式的核心思想是将遍历行为和数据结构分离。迭代器将遍历行为抽象了出来，变成了一个单独的工序，而不是混杂在业务逻辑和数据结构之中。或者也可以说，迭代器封装了遍历操作，并通过泛型和接口使任何类型都能够使用，任何对象都能够获得独立的迭代器实例，实现遍历的功能。

迭代器应用范围非常广泛，文件的读取，数据的读取，bfs和dfs，流，生成器都可以应用。本文主要探讨集合框架Collection的迭代器。

集合的迭代器

集合的迭代器Iterator能够实现不重写代码就可以应用于不同容器。而且，正如它的名字所说，迭代器的作用就是迭代容器内元素。迭代器封装了对所有Collection的遍历操作。Map并没有实现迭代器，但是Map的三个视图entryset、keyset，values 都实现了迭代器。（分别属于set，set，collection类）。有了迭代器就不必为容器中元素的数量而操心了，hasNext()和next()方法会解决此类问题。

collection继承简图

        Iterable--------------------------------------------------------------
            ^                                                               
            |                             若键不存在，put方法返回null，若键已存在，将键对应                                            .                                             的值替换为put函数内的新值，返回原来对应的值    
     collection--------------------------------------------     Map（键值对，实质为数组） 
            ^                        ^                  ^                   ^
            |                        |                  |                   |
            list                    set（集合)       queue                 HashMap
            ^                           ^
            |                           |
    stack  ArrayList  LinkedList        HashSet         

如果出现哈希碰撞（两个不同的值计算出相同的键），在键对应数组存储单项非环链表。

迭代器（Iterator）是一个轻量级对象（这意味着创建它的代价很小），它的工作是遍历并选择序列中的对象。在Java中，迭代器Iterator只能够单向移动，并且只具有如下特性和方法：

1、容器使用方法.iterator()能够返回一个Iterator类，Iterator将返回容器序列内的第一个元素。

2、方法next()用来获取序列中下一个元素。

3、方法hasNext()检查序列之中是否还有下一个元素（是否迭代完成）。

4、方法remove()删除迭代器最新返回的元素。

下为Iterator接口的源码

/**
 * An iterator over a collection.  {@code Iterator} takes the place of
 * {@link Enumeration} in the Java Collections Framework.  Iterators
 * differ from enumerations in two ways:
 *
 * <ul>
 *      <li> Iterators allow the caller to remove elements from the
 *           underlying collection during the iteration with well-defined
 *           semantics.
 *      <li> Method names have been improved.
 * </ul>
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @apiNote
 * An {@link Enumeration} can be converted into an {@code Iterator} by
 * using the {@link Enumeration#asIterator} method.
 *
 * @param <E> the type of elements returned by this iterator
 *
 * @author  Josh Bloch
 * @see Collection
 * @see ListIterator
 * @see Iterable
 * @since 1.2
 */
public interface Iterator<E> {
    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    boolean hasNext();
​
    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    E next();
​
    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.
     * <p>
     * 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, unless an overriding class has specified a
     * concurrent modification policy.
     * <p>
     * The behavior of an iterator is unspecified if this method is called
     * after a call to the {@link #forEachRemaining forEachRemaining} method.
     *
     * @implSpec
     * The default implementation throws an instance of
     * {@link UnsupportedOperationException} and performs no other action.
     *
     * @throws UnsupportedOperationException if the {@code remove}
     *         operation is not supported by this iterator
     *
     * @throws IllegalStateException if the {@code next} method has not
     *         yet been called, or the {@code remove} method has already
     *         been called after the last call to the {@code next}
     *         method
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
​
    /**
     * Performs the given action for each remaining element until all elements
     * have been processed or the action throws an exception.  Actions are
     * performed in the order of iteration, if that order is specified.
     * Exceptions thrown by the action are relayed to the caller.
     * <p>
     * The behavior of an iterator is unspecified if the action modifies the
     * collection in any way (even by calling the {@link #remove remove} method
     * or other mutator methods of {@code Iterator} subtypes),
     * unless an overriding class has specified a concurrent modification policy.
     * <p>
     * Subsequent behavior of an iterator is unspecified if the action throws an
     * exception.
     *
     * @implSpec
     * <p>The default implementation behaves as if:
     * <pre>{@code
     *     while (hasNext())
     *         action.accept(next());
     * }</pre>
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

remove 方法在 Iterator 接口中默认抛出异常，这样设计的目的是：

不可变集合（如 List.of() 返回的集合）不需要重写 remove，直接继承默认实现，调用时自动抛出异常；可变集合（如 ArrayList）则重写 remove方法，提供真正的删除逻辑。

remove方法的默认实现使实现类不必写重复代码，减少了代码冗余。

如果说hasNext是手动挡，那么forEachRemaining就是自动挡，它将 while (hasNext())封装成了方法，能够一次性跑完集合剩下的所有元素，并对各个元素执行action操作。forEachRemaining()方法接收一个函数式接口Consumer，共有四种传入方式：lambda表达式，匿名内部类，Consumer对象，方法引用。简而言之，就是向方法中传入了需要对元素执行的操作。

强大的子类型ListIterator

ListIterator是一个更加强大的Iterator子类型，它只能用于各种List类的访问。于Iterator不同的是，ListIterator可以双向移动，还可以产生相对于迭代器在列表中指向的当前位置的前一个元素和后一个元素的索引，并使用set()方法替换它访问的最后一个元素。而且，在创建ListIterator时，不仅可以通过调用listIterator()方法产生一个指向list开头的迭代器，还可以调用listIterator(n)方法指定迭代器指向列表索引为n的元素。

实际应用：

示例代码：

public class IteratorTest{
    public static void main(String[] args) {
        Random random = new Random();
        List<Integer> list = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            list.add(i, random.nextInt(100)+1);
        }
        System.out.println("list" + list);              // 输出list的值
        Iterator<Integer> iterator = list.iterator();   // 创建迭代器
        System.out.println("单次迭代");
        if (iterator.hasNext()) System.out.println(iterator.next());    //单次迭代
        System.out.println("一次性完成");
        iterator.forEachRemaining(System.out::println);                 // 语法糖，迭代到结尾
​
        // listIterator演示
        ListIterator<Integer> integerListIterator = list.listIterator(5);   // 设置index指针为5
        System.out.println("listIterator");
        if (integerListIterator.hasPrevious()){                             // 判断是否有上一个元素
            System.out.println(integerListIterator.previous());             // 输出上一个元素并将指针前移
        }
        integerListIterator.set(102);   //随机数最大100
        integerListIterator = list.listIterator(0); // 设置指针为开头
        integerListIterator.forEachRemaining(System.out::println);          // 迭代到结尾
​
    }
​
}

输出结果：

相似接口iterable

iterable的源码：

/**
 * Implementing this interface allows an object to be the target of the enhanced
 * {@code for} statement (sometimes called the "for-each loop" statement).
 *
 * @param <T> the type of elements returned by the iterator
 *
 * @since 1.5
 * @jls 14.14.2 The enhanced {@code for} statement
 */
public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
​
    /**
     * Performs the given action for each element of the {@code Iterable}
     * until all elements have been processed or the action throws an
     * exception.  Actions are performed in the order of iteration, if that
     * order is specified.  Exceptions thrown by the action are relayed to the
     * caller.
     * <p>
     * The behavior of this method is unspecified if the action performs
     * side-effects that modify the underlying source of elements, unless an
     * overriding class has specified a concurrent modification policy.
     *
     * @implSpec
     * <p>The default implementation behaves as if:
     * <pre>{@code
     *     for (T t : this)
     *         action.accept(t);
     * }</pre>
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
​
    /**
     * Creates a {@link Spliterator} over the elements described by this
     * {@code Iterable}.
     *
     * @implSpec
     * The default implementation creates an
     * <em><a href="../util/Spliterator.html#binding">early-binding</a></em>
     * spliterator from the iterable's {@code Iterator}.  The spliterator
     * inherits the <em>fail-fast</em> properties of the iterable's iterator.
     *
     * @implNote
     * The default implementation should usually be overridden.  The
     * spliterator returned by the default implementation has poor splitting
     * capabilities, is unsized, and does not report any spliterator
     * characteristics. Implementing classes can nearly always provide a
     * better implementation.
     *
     * @return a {@code Spliterator} over the elements described by this
     * {@code Iterable}.
     * @since 1.8
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

从第一行类注释中我们可以知道，实现iterable接口之后，对象即可成为增强型for语句（有时称为“for-each循环”语句）的目标。也就是说，如果一个对象想使用for-each循环，那么它所属的类必须实现iterable接口。

当然，iterable只是一张for-each的通行证，实质上发挥作用的还是iterator接口。一个类实现了iterable接口后，需要

实现Iterator<T> iterator();方法，自动创建了一个iterator迭代器对象。那么肯定就有人要问了，欸接口中也没有其他方法要用到iterator啊，即使没有iterator，forEach方法不也能执行增强for循环吗？

问题就出在增强for循环上。因为增强for循环的底层就是iterator。

for (T t : this) 编译后等价于：

Iterator<T> it = this.iterator(); // 调用了 iterator()

while (it.hasNext()) {

        T t = it.next();

        action.accept(t);

}

看，iterator又出现了，所以，强制创建一个当前对象的迭代器就是必要的操作了。

iterable接口中还有一个方法spliterator()，这个方法返回了一个拆分器。拆分器是java用于并行遍历的迭代器，可以对对象进行拆分之后并行多线程同步遍历。