各容器迭代器的实现

十二月的第二周，来学习迭代器在各个容器中的具体实现。

不知道自己能看多少，ArrayList 和 HashSet 的实现是应该必须看完的，如果时间有余也要看看 TreeSet 的实现（哈哈哈……不相信自己的苍白的微笑）。

这周的目标应该不是在迭代器上，而是在容器设计和怎么看源码这两件事上。迭代器是因和果，但从因走到果的那条路是更有价值的。

---

ArrayList

ArrayList 是可调整大小的 List，实现了两种迭代器：迭代器、列表迭代器。

列表迭代器是在原本迭代器的基础上增加了顺序，例如增加了是否有前一个元素、下一个元素的坐标等方法。

我在这里只关注 ArrayList 实现的普通迭代器。

获取 ArrayList 的迭代器，与其他容器的方式一样，都是调用 Iterator() 方法，获得一个迭代器。（这里迭代器支持泛型）

Iterator<E> iterator = arrayList.iterator();

公共方法 Iterator()，返回了一个 ArrayList 类内部实现的迭代器 Itr。

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

private class Itr implements Iterator<E> {
    // Itr类的内部实现...
}

那我们要关注的就是 Itr 类内部是怎么实现的。

ArrayList 的迭代器，Itr 类的基本骨架是这样子的：

private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    int expectedModCount = modCount;

    public boolean hasNext() {
        // ...
    }

    public E next() {
        // ...
    }

    public void remove() {
        // ...
    }
    
    // 还有其他两个方法
    // 包括jdk 1.8版本新增的方法forEachRemaining，以及一个私有的辅助方法
}

ArrayList 在实现迭代器时，自己又定义了三个 int 类型的局部变量：cursor、lastRet、expectedModCount。我们先不看迭代器重写的方法是怎么实现，先关注这三个局部变量是做什么的。

• cursor 坐标

  表示迭代器移动到了 ArrayList 的第几个元素，它会伴随着迭代器的移动而移动。

  用于判断迭代器的位置，也用于错误判断（比如越界）

• lastRet 上个坐标

  最开始是 -1，随着 cursor 一同增加，但始终比 cursor 小 1。

  用于判断迭代器刚刚经过的位置，来删除元素，或是错误判断。

• expectedModCount 列表结构变化次数

  这是一个很有趣的设计，它不光出现在 ArrayList 的迭代器里，而是出现在 ArrayList 的各个方法中。

  这个变量，记录的是列表改变了多少次结构（即列表内元素的数量，发生了多少次变化）。比如初始化一个 ArrayList 之后，add 了一个元素，那么 modCount 就是 1，又 add 了一个元素，那么 modCount 就是 2，之后 remove 了一个元素，列表的结构又发生了改变，modCount 变成了 3。modCount 记录的，就是列表的结构发生了多少次的变化（mod：modification)。

  记录列表结构发生变化的次数，这有什么意义呢。ArrayList 是一个非线程安全的类，当有多个线程共用时，很有可能一边新增或删除了列表的某个元素，另一边对此毫不知情而发生错误。对此，ArrayList 为迭代器专门设计了一个 transient 的变量 modCount，不论任何位置，只要改变了列表的结构，都把这一次记录下来。那么，当迭代器初始化时，记录下来 modCount，之后迭代器工作前简单比较一下，当初记录的次数和现在的次数是否相同，就能知道列表有没有发生结构性变化。虽然这不是一个很保险的方式（即使 modCount 相同也有可能出现问题），但是这种方式很轻便，也基本能覆盖大部分问题。

  实际上 modCount 并不是 ArrayList 独有的设计，在很多容器（ArrayList、LinkedList、HashMap……）都能看到这种设计：记录容器结构变化的次数，迭代器工作时能快速纠错。这被称为 Java 的 fail-fast 机制，一种用于容器的错误检错机制。

好了，那么开始看源码吧。

hasNext

极为简单，当前坐标是否达到容器的长度，达到则返回 false，没达到则返回 true。

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

为什么是容器的长度，而不是长度 - 1，这个要根据其他两个方法来看，cursor 坐标究竟指向哪个元素。

next

next 方法的目的，是返回容器的下一个元素。对于列表而言，元素之间是有顺序的，按顺序返回即可。

public E next() { // E 代表泛型
    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];
}

大致上分两个步骤：

1. 检查

   ArrayList 实现的 next 方法首先检查 modCount，如果列表发生结构性变化，快速失败。

   // 迭代器的内部方法
   final void checkForComodification() {
       if (modCount != expectedModCount)
           throw new ConcurrentModificationException();
   }

   检查非常简单，比较迭代器初始化时的 modCount（expectedModCount），和当前列表的 modCount 是否相同，不同就是结构变了。

   然后还会检查 cursor 坐标是否指向了越界的位置。

2. 移动

   在检查完结构后，next 方法正式工作。

   它利用 cursor 来判断位置，返回列表的第 cursor 个元素，由于 ArrayList 的背后是由数组实现的，next 方法实际上返回的是数组的第 cursor 个元素，即 return elementData[cursor];。

   在迭代器执行 next 方法返回下一个元素的同时，它的两个类变量 cursor、lastRet 也自增 1。

观察发现，cursor 始终指向迭代器的下一个元素的位置，当 next 方法还没执行时，cursor 指向的是要返回的那个“下一个元素”，但当 next 方法要返回下个元素的时候，cursor 就又自增 1，指向了更下一个的元素。还有一种说法是，迭代器是以 cursor 为当前坐标的，next 方法是越过当前元素，到下一个元素的位置上，并返回刚刚越过去的那个元素。

lastRet 是 cursor 的跟班，紧跟在 cursor 一步远的距离，做迭代器的校验工具人。

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();
    }
}

照例还是分两步走，第一步校验。next 方法校验的是结构是否变化、下个位置是否越界。与之对称的，remove 方法校验的是结构是否变化，当前元素是否不存在。

第二步移除。这里迭代器的 remove 方法，实际上就是列表自己的 remove 方法。列表的 remove 方法实际上是在调用 System.arraycopy 方法，将数组需要移除那个元素，之后的所有元素逐个往前挪位置，以达到数组复制的效果，是个开销不小的实现方法。不过仔细看，迭代器的 remove 方式是只能执行一次的，执行之后 lastRet 就归为初始的 -1 值，不能再 remove 了。

---

HashSet

看了源码才知道，原来 HashSet 基本就是 HashMap，它的迭代器实现也是 HashMap 里面的。

HashSet 内部维护一张 HashMap 表，HashMap 有 key 和 value，key 就是 HashSet 的值，而 value 统一都是一个空对象。当创建一个 HashSet 时，实际上就是在创建一张 HashMap，修改 set 的值实际上就是在修改 map 的键值对。可以从 HashSet 的 add 方法来粗略一窥：

// HashSet内部用map存储
private transient HashMap<E, Object> map;

// HashSet存储时，key是集合的值，value是这个空对象
private static final Object PRESENT = new Object();

// HashSet的add方法，增加元素实际上就是在往map里存键值对
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

向 HashSet 里增加一个元素，实际上就是在内部维护的 HashMap 里，存入一个 key 为想要增加的元素、value 为空对象的键值对。

HashMap 自己是没有迭代器的，因为 map 里的每个元素都是有两部分的键和值，迭代器无法同时迭代两个部分。但是迭代其中的一部分是可行的，例如迭代 key，或是迭代 value。实际上，HashSet 的迭代器，就是在迭代 key。

在 HashMap 的源码中，与迭代器相关的内部类有四个，它们被码在同一个区域。

/* ------------------------------------------------------------ */
// iterators

abstract class HashIterator {
}

final class KeyIterator {
}

final class ValueIterator {
}

final class EntryIterator {
}

// 其实还有四个与 Spliterator 相关的迭代器类 （Spliterator：splitable iterator）
// 它们是可分隔迭代器，用于并行迭代，但我们目前忽视它们

这四个迭代器，第一个是抽象类，后面三个是我们能使用的类：

• KeyIterator key 迭代器
• ValueIterator value 迭代器
• EntryIterator key-value （键值对）迭代器

第一个迭代器 HashIterator 是上面这三个迭代器的父类，它算是实现了迭代器的 hasNext、next、remove 三个方法，后面三个迭代器直接继承了它的 hasNext 和 remove 方法，简单写了 next 方法。

是怎么简单实现 next 方法的呢，以 KeyIterator 类为例：

// K 是泛型类，与迭代器的泛型类相同
public final K next() { return nextNode().key; }

就是返回了父类定义的键值对的 key 值，一行代码。

其他两个类也是如此，返回 value 和返回 key-value，因此我们就不提 HashMap 的后面三个迭代器了，重点看第一个迭代器的实现。

从整体上看，HashIterator 类的骨架是这样的：

abstract class HashIterator {
    // Node 类是 HashMap 里定义的键值对类，它继承了 Map.Entry 类
    Node<K,V> next;        
    Node<K,V> current;     
    int expectedModCount;  
    int index;             

    HashIterator() {
        // ...
    }

    public final boolean hasNext() {
        // ...
    }

    final Node<K,V> nextNode() {
        // ...
    }

    public final void remove() {
        // ...
    }
}

一共四个内部变量，

• next 下一个键值对
• current 当前键值对
• expectedModCount 预期 hashMap 的结构变化次数
• index 当前键值对的坐标（HashMap 存放键值对，是以数组的方式来存储的）

以及四个方法。

• HashIterator 构造方法，初始化迭代器
• hasNext 是否有下一个元素
• nextNode 下一个键值对
• remove 删除当前元素

四个内部变量，跟 ArrayList 实现迭代器的逻辑是相同的，就不写两遍了，看后面的四个方法是怎么实现的。

HashIterator

HashMap 的迭代器的构造器，初始化了四个内部变量。

HashIterator() {
    expectedModCount = modCount;
    Node<K,V>[] t = table;
    current = next = null;
    index = 0;
    if (t != null && size > 0) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
}

初始化 modCount 和 current 没什么好讲的，简单赋值。

table 是 HashMap 内部存储键值对的数组，具体内容这周不看，但是我们需要知道的是，这个数组内部并不是连续排列，一个键值对紧跟着一个键值对的，中间可能会有 null。

为了考虑内部存储的结构，当前元素存储的下一个数组格子，可能没有存储任何东西，只是 null，因此需要跳过这些空格。为 next 变量赋值时，以及为 index 变量赋值时，是需要跳过空白格子的。

do {} 
while (index < t.length && (next = t[index++]) == null);

（这行代码还真是紧凑……）

hasNext

迭代器是否有下个元素，去掉方法的结构体只有一行代码：

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

nextNode

HashMap 的抽象迭代器并没有 next 方法，next 方法交由子类实现，但是它实现了 next 方法所必需的，搜索下一个键值对的逻辑。

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();
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

首先检查 HashMap 的结构是否发生变化（fail-fast 机制），然后检查存储键值对的数组是否为 null（即没有初始化过）。再之后是两行密度很高的代码：

if ((next = (current = e).next) == null && (t = table) != null) {
	do {} while (index < t.length && (next = t[index++]) == null);
}

这两行代码的含义是：

1. 为迭代器的当前元素赋值（也就是上一轮迭代器的 next 元素）。
2. 如果没遍历完存储的内容，那么让 index 移动，让 next 键值对往后挪。
3. 存储键值对的数组，可能存在 null 值，要跳过这些 null 值，让 next 变量指向真正的下一个元素，让 index 坐标指向真正的下一个元素的再下一个位置。

从 HashMap 的迭代器，能够大概看出，HashMap 似乎用链表和数组两种方式来存储键值对，数组中放着一个个的链表节点，而链表节点又能指向下一个元素。在数组中的每个元素都连续排列的情况下，用链表检索下一个；当数组中出现“缝隙”，元素之间断开时，又用数组来检索下一个。

没看 HashMap 的其他源码，不知道这种处理方式有什么好处。

（次日改：我智障了，我原来以为链表和数组是互补的，同时使用提高效率，其实链表的作用是让同一个数组格子能够存放多个元素，因为 HashMap 存储元素时，存储的位置是计算出来的，如果计算出来结果相同，那就要存在相同的地方。）

remove

感觉 remove 方法没什么太多可说的，检查完然后调用 HashMap 的删除方法，代码如下：

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;
    removeNode(hash(key), key, null, false, false);
    expectedModCount = modCount;
}

---

写这篇迭代器的原因，是因为写业务代码时犯了错误，在 for-each 循环里调用了容器的 remove 方法，结果让生产代码回滚了。

for (String str : list) {
    // 执行逻辑...
    list.remove(str);
}

for-each 实际上是用迭代器实现的（这个找不到源码，但可以从反编译代码中推断出来），容器使用了 remove 方法改变了结构，modCount 改变了，和迭代器中的 expectModCount 不相同，会直接抛异常（ConcurrentModificationException）。

当时测试没有看出来，因为只测试了列表的倒数第二个元素。很有趣的是，列表迭代器中的每个元素都会报错，唯独倒数第二个不会报错，就这样侥幸通过了代码自测……至于为什么倒数第二个不会报错，这个跟坐标有关，就不写下去了。