Java 为我们提供了现成的集合类库，我们常用的 List Set Map 等都是在开发过程中可以直接使用的，设计到集合就不得不说集合的遍历，之前分析迭代器模式时我们提到了在 Java 的集合功能实现中也使用了迭代器模式，这里先简单介绍一下迭代器模式。
一、迭代器模式
迭代器模式(Iterator Pattern) 又称游标(Cursor) 模式，是行为型设计模式之一。迭代器模式源于对容器的访问，比如 Java 中的 List、Map、数组等，我们知道对容器对象的访问必然会涉及到遍历算法，我们可以将遍历的方法封装在容器中，或者不提供遍历方法。如果我们将遍历方法封装在容器中，那么对于容器来说承担了过多的功能，容器类不仅要维护自身内部的数据元素而且还要对外提供遍历的接口方法，因为遍历状态的存储问题还不能对同一个容器同时进行多个便利操作，如果我们不提供便利方法而让使用者自己去实现，又会让容器内部细节暴露，因此，迭代器模式产生，在客户访问类与容器之间插入了一个第三者 - 迭代器，很好的解决了上述的弊端。
二、Java 中的迭代器类
简单了解了迭代器模式之后，我们来分析 Java 中是如何具体通过迭代器模式实现了对集合的遍历，以及由 Java 中的实现方式更深入的理解迭代器模式的应用。
1. Iterable
Iterable 是一个接口，实现了该接口的类是可以通过迭代器进行遍历的，Java 中的 Collection 继承了 Iterable，List 和 Set 有继承了 Collection，所以 List 和 Set 中元素的遍历都是可以通过迭代器模式来实现。
Iterable 的 iterator() 方法的作用就是返回一个迭代器，最终使用迭代器完成遍历工作。
public interface Iterable<T> {
/**
* 返回一个迭代器 Iterator 用于元素集合的遍历
*/
Iterator<T> iterator();
}
2. Iterator
Iterator 类是 Java 中迭代器的接口，Iterator 类中声明了 hashNext() 和 next() 两个重要方法，来判断是否遍历结束以及遍历到下一个位置。
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());
}
}
Java 中的集合实现主要 List 和 Set，下面会先分析 List 中迭代器的使用，然后再由 Set 的迭代器分析延伸到 Map 的迭代方式。
三、List 中的迭代器 Iterator
前面提到了 List 继承了 Iterable，所以也要实现 iterator() 方法用来返回一个可用的迭代器，方法如下,直接返回一个 Itr 对象，重点来分析 Itr 类的实现。
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
/**
* 下一次遍历返回的元素的索引
*/
int cursor = 0;
/**
* 返回上一次 next 返回的元素的索引，如果该元素被删除则返回 -1
*/
int lastRet = -1;
/**
* 迭代器中记录集合的命中数量，在迭代器操作时如果集合的命中数量与记录的不同，此时迭代器会检测到并发修改
*/
int expectedModCount = modCount;
/**
* 返回是否还有元素没有被遍历
*/
public boolean hasNext() {
return cursor != size();
}
/**
* 返回是下一个需要被遍历的元素
*/
public E next() {
// 检测
checkForComodification();
try {
int i = cursor;
// 获取当前需要被遍历的元素
E next = get(i);
// 记录当前被遍历的元素索引
lastRet = i;
// 计算下一个需要被遍历的元素索引
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
/**
* 迭代过程中，从集合中移除当前遍历到的元素的方法
*
* 在遍历时，通过迭代器的 remove() 方法可以安全的移除元素，如果不使用迭代器的 remove() 方法，会造成并发操作，抛出异常
*/
public void remove() {
if (lastRet < 0) // 还没有开始遍历，做移除操作会抛出异常
throw new IllegalStateException();
checkForComodification();
try {
// 调用集合本身的移除方法移除元素
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
// 更新期望的命中数量
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
/**
* 检测集合的命中数量是否于记录的相同，如果不同则说明有并发修改，抛出异常
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
List 的迭代器的实现中，hasNext() 方法是通过当前遍历到的位置是否超过集合的数量来判断的，next() 方法则是返回当前遍历到的位置的元素，在操作过程中都需要进行是否存在并发修改的判断，这个判断通过对比迭代器中记录的集合命中数量与真是的命中数量比较来确定，在 List 的迭代器的 remove() 方法中，出了进行移除操作，还会更新迭代器中保存的命中数量。
在开发过程中，对集合的遍历我们一般都是通过 for 循环的形式，但是 for 循环的方式在遍历过程中如果我们需要移除元素，则需要添加其他的处理(对 for 循环条件的动态调整，因为移除元素后集合数量已经发生了变化，如果不调整会在遍厉过程中跑出 IndexOutOfBoundsException 异常)，而使用迭代器的方式则不需要做特殊处理。
四、Set 中的迭代器
List 的迭代器的代码比较简单，因为 Set 这种数据结构是通过 Map 实现的，所以 Set 的遍历则相对复杂一点，这部分不熟悉的同学，可以出门左转，看看我之前写过的一篇介绍 Java 中提供的集合和 Map 实现方式的文章，地址在这里：Java 集合类实现原理
接下来我们以 HashSet 为例看一下 Set 中迭代器的工作过程。HashSet 中的 iterator() 方法如下，
// HashSet
public Iterator<E> iterator() {
return map.keySet[()].iterator();
}
// HashMap
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
// HashMap
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
// 真正实现 iterator() 方法的地方
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// Android-changed: Detect changes to modCount early.
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// HashMap
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
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; // table 是保存 HashMap 所有数据的 Hash 数组
current = next = null; // current 当前遍历到的元素，next 下一个需要被遍历的元素
index = 0; // 初始化遍历位置
if (t != null && size > 0) { // advance 推进，推进 index 到 Hash 数组中第一个不为 null 的位置，因为 Hash 表中任意位置都可能为 null
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) // 是否存在并发操作的判断，同 List
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) { // 为 current 赋值，并且定位下一个需要被遍历的元素
do {} while (index < t.length && (next = t[index++]) == null); // 如果当前单链表遍历结束，则需要在 Hash 表中继续定位
}
// 返回当前遍历到的元素
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; // 将当前遍历到的元素置空
K key = p.key;
// 调用 HashMap 的方法移除元素
removeNode(hash(key), key, null, false, false);
// 更新期望的命中数量
expectedModCount = modCount;
}
}
上面是 Set 中迭代器的源码，Set 的迭代器还是通过其本身实现的过程中使用到的 HashMap 的迭代，HashMap 的迭代也就是对 Hash 表的迭代，迭代到 HashMap 中每个元素后，这个元素的 key 就是 Set 中存储的元素。由 HashSet 的分析延伸到了 HashMap，对 HashMap 遍历也就是 HashSet 遍历使用的方式。
五、总结
到这里我们就将 Java 中集合和 Map 的遍历都介绍了，List、Set、Map 遍历时每次调用 iterator() 方法都会创建一个 Iterator 的对象，满足了我们对同一个容器进行多次遍历的操作，但是不论是 List 还是 Set 和 Map 在使用时都需要注意多线程同事操作时的并发问题。
