各容器迭代器的实现


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

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

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


ArrayList

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

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

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


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

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

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

1
2
3
4
5
6
7
public Iterator<E> iterator() {
return new Itr();
}

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

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


ArrayList 的迭代器,Itr 类的基本骨架是这样子的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 类型的局部变量:cursorlastRetexpectedModCount。我们先不看迭代器重写的方法是怎么实现,先关注这三个局部变量是做什么的。

  • 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。

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

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


next

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

1
2
3
4
5
6
7
8
9
10
11
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,如果列表发生结构性变化,快速失败。

    1
    2
    3
    4
    5
    // 迭代器的内部方法
    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 方法的目的,就是把迭代器的当前元素,在整个列表里剔除掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 有 keyvaluekey 就是 HashSet 的值,而 value 统一都是一个空对象。当创建一个 HashSet 时,实际上就是在创建一张 HashMap,修改 set 的值实际上就是在修改 map 的键值对。可以从 HashSet 的 add 方法来粗略一窥:

1
2
3
4
5
6
7
8
9
10
// 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 的源码中,与迭代器相关的内部类有四个,它们被码在同一个区域。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* ------------------------------------------------------------ */
// 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 类为例:

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

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

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


从整体上看,HashIterator 类的骨架是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 的迭代器的构造器,初始化了四个内部变量。

1
2
3
4
5
6
7
8
9
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 变量赋值时,是需要跳过空白格子的。

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

(这行代码还真是紧凑……)


hasNext

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

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

nextNode

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

1
2
3
4
5
6
7
8
9
10
11
12
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(即没有初始化过)。再之后是两行密度很高的代码:

1
2
3
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 的删除方法,代码如下:

1
2
3
4
5
6
7
8
9
10
11
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 方法,结果让生产代码回滚了。

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

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

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