迭代器
迭代器
迭代器：绝大多数Java容器都有的modCount属性是做什么用的？
讲到容器，我们不得不讲一下迭代器。迭代器是遍历容器的常用方法。Java中的迭代器是迭代模式的经典实现。虽然大部分情况下迭代器的使用都比较简单，但有些情况下也会比较复杂，比如在创建迭代器之后，增删容器中的元素，再使用迭代器遍历容器，会导致未决行为（结果不确定）。为了解决这一问题，迭代器又设计了一套复杂的保护机制，而这套机制在面试中又经常被考察。所以，本节我们就来详细讲一讲迭代器。
一、容器的几种遍历方法
常用的遍历容器的方法有4种：for循环、for-each循环、迭代器、forEach()函数。关于这4种遍历方式如何使用，我们拿List容器做示例，如下所示。
List<String> list = new ArrayList<>();
list.add("xiao");
list.add("zheng");
list.add("ge");
// 第一种遍历方式：for循环
for (int i = 0; i < list.size(); ++i) {
System.out.println(list.get(i));
}
// 第二种遍历方式：for-each循环
for (String s : list) {
System.out.println(s);
}
// 第三种遍历方式：迭代器
Iterator<String> itr = list.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
// 第四种遍历方式：forEach()函数
list.forEach(s->System.out.println(s));
实际上，并不是每种容器都支持以上4种遍历方式。在第11节中，我们将JCF分为5类：List、Stack、Queue、Set、Map。其中，因为Stack、Queue是操作受限的容器，只支持一端或两端操作，所以，一般不支持遍历。我们重点分析List、Set、Map这三类容器的遍历方式。
1）第一种遍历方式（for循环遍历），只能用于List容器，比如ArrayList、LinkedList。因为这种遍历方式需要根据下标获取元素，而Set、Map并没有下标的概念，所以不支持这种遍历方式。尽管LinkedList底层使用链表实现，但实现了List接口，在用法上支持按照下标查找元素。不过，对于LinkedList来说，使用for循环遍历的性能会比较差。因为在LinkedList上调用get()函数需要遍历链表，所以，get()函数的时间复杂度是O(n)，因此，for循环遍历的时间复杂度是O(n^2)。
2）第二种遍历方式（for-each循环）和第三种遍历方式（迭代器）是等价的。for-each循环遍历也叫做增强for循环，实际上是一种语法糖，其底层就是采用迭代器来实现的。
迭代器遍历方式只支持实现了Iterable接口的类。在之前展示的JCF类图中，我们发现，List、Set实现了Iterable接口，Map没有实现Iterable接口，因此，List、Set支持迭代器遍历，Map不支持迭代器遍历。如果要想通过迭代器遍历Map容器，我们需要通过间接的方式来实现：通过entrySet()获取EntrySet对象，然后，通过EntrySet提供的迭代器来遍历。具体参看上一节的讲解。
3）第四种遍历方式（forEach()函数）是JDK8引入函数式编程时引入的，在JDK7及其以前版本中不能使用。List、Set、Map都实现了forEach()函数。关于forEach()函数的介绍，我们留在函数式编程中讲解。
对于这4种遍历方式，for循环遍历非常简单，forEach()函数稍后章节再讲，for-each循环是迭代器的语法糖，所以，接下来，我们重点讲解迭代器遍历方式。
二、迭代器存在的意义
对于简单容器来说，比如ArrayList、LinkedList，其底层的存储结构比较简单，我们直接使用for循环遍历会比较简单。但是，对于复杂容器，比如HashSet、TreeSet，其底层的存储结构比较复杂，遍历的逻辑比较复杂，如果让程序员自己去实现，势必增加了开发成本。所以，这些复杂容器便自己实现了遍历逻辑，包裹为迭代器，供程序员使用，以此降低程序员的开发成本。当然，为了统一访问方式，不管是简单容器还是复杂容器，Java都提供了直接或间接的迭代器的遍历方式。
三、迭代器的基本实现原理
Java中的迭代器是迭代器设计模式的经典实现。关于迭代器模式的更多介绍，你可以阅读我的另一本书《设计模式之美》。迭代器设计模式的代码结构如下图所示。
从上图中，我们得出，所有支持迭代器遍历方式的类都要实现Iterable接口。Iterable接口在JDK8中的定义如下所示。从代码中，我们也可以得到这样一个信息，但凡是支持迭代器遍历的容器，都支持forEach()函数遍历。
public interface Iterable<T> {
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
//用于配合实现forEach()函数式编程
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
我们结合ArrayList容器来看下，具体如何为容器提供迭代器。
从在第11节中展示的JCF类图中，ArrayList实现了List接口，List接口又继承自Collection接口，Collection接口又继承自Iterable，层层追溯，我们得出，ArrayList实现了Iterable接口。ArrayList中iterator()函数的代码实现如下所示。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable,
java.io.Serializable {
//...省略其他属性和方法...
protected transient int modCount = 0;
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
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];
}
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();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}
如上代码所示，每个容器都定义了自己的迭代器，用于遍历自己的元素，并且，Iterator接口是所有迭代器类的统一接口。Iterator接口的定义如下所示，最基本最常用到的两个函数是hasNext()和next()，remove()函数非必须，不常用到。
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
}
其他容器的迭代器的实现，跟ArrayList容器的迭代器的实现类似，都遵从迭代器模式的代码结构。容器实现Iterable接口，迭代器实现Iterator接口，容器中定义迭代器类，并通过iterator()函数返回迭代器类对象。
不过，除了Iterator之外，List容器还补充提供了增强版的迭代器ListIterator，除了hasNext()、next()、remove()函数之外，ListIterator还提供了hasPrevious()、previous()、set()、add()等函数。ListIterator接口的定义如下所示。
//ListIterator继承自Iterator，是Iterator的增强版
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
void set(E e);
void add(E e);
}
ListIterator迭代器使用方法示例代码如下。
List<Integer> list = new ArrayList<>();
list.addAll(Arrays.asList(0, 1, 2, 3, 4));
// 从下标为2的位置开始遍历
ListIterator<Integer> litr = list.listIterator(2);
while (litr.hasNext()) {
System.out.println(litr.next()); //输出 2 3 4
}
while(litr.hasPrevious()) {
System.out.println(litr.previous()); //输出 4 3 2 1 0
}
四、迭代器遍历存在的问题
在上述给出的ArrayList的迭代器类Itr的代码实现中，除了实现hasNext()、next()的必要成员变量cursor，以及实现remove()的必要成员变量lastRet之外，还有引入了一个特殊的成员变量expectedModCount，其初始化为容器的modCount值，并且在调用next()函数时，通过调用checkForComodification()函数检查expectedModCount和modCount是否相等，为什么引入expectedModCount和modCount这两个成员变量呢？
因为在创建迭代器之后，增删容器中的元素，再使用迭代器遍历容器，会导致未决行为（结果不确定），所以才引入了这两个成员变量。我们先来看未决行为是如何产生的，再来看如何通过这两个成员变量来解决。
我们先暂时假设，ArrayList的迭代器Itr类中，未使用这两个成员变量，简化之后的Itr类代码如下所示。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public E next() {
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
cursor = i + 1;
return (E) ArrayList.this.elementData[i];
}
}
如果在使用以上简化之后的迭代器来遍历容器的同时，增加或者删除容器中的元素，有可能会出现某个元素被重复遍历或遍历不到的情况。但是，这种情况并非总是发生，所以，我们称这种情况称为未决行为或不确定行为，也就是说，运行结果到底是对还是错，要视情况而定。
我们分两种情况展开讲解。
1）第一种情况是，在创建迭代器之后，增加集合中的元素。示例代码如下所示。
List<String> list = new ArrayList<>(); //第1行
list.addAll(Arrays.asList("a", "b", "c", "d")); //第2行
Iterator<String> itr = list.iterator(); //第3行
itr.next(); //第4行
list.add(0, "x"); //第5行
ArrayList底层依赖数组这种数据结构来存储数据。当执行完第4行代码之后，数组中包含“a”、“b”、“c”、“d”这四个元素，cursor值为1，“a”元素已经被遍历，下一次调用next()函数将输出“b”。如下所图所示。在执行完第5行代码之后，“x”插入到数组中下标为0的位置，“a”、“b”、“c”、“d”这四个元素依次往后挪移一位。此时，cursor值不变，仍然为1。cursor重新指向了元素“a”。下一次调用next()函数将再次输出元素“a”，元素“a”被重复遍历了。不过，如果我们将元素“x”插入到cursor所指元素之后，便不会出现重复遍历的情况。
2）第二种情况是，在创建迭代器之后，删除集合中的元素。示例代码如下所示。
List<String> list = new ArrayList<>(); //第1行
list.addAll(Arrays.asList("a", "b", "c", "d")); //第2行
Iterator<String> itr = list.iterator(); //第3行
itr.next(); //第4行
list.remove(0); //第5行
对于上述代码，执行完第4行代码之后，数组中包含“a”、“b”、“c”、“d”这四个元素，cursor值为1，下一次调用next()函数将输出“b”。如下所图所示。在执行完第5行代码之后，元素“a”被删除，其他三个元素会依次往前移动一位。此时，cursosr值不变，仍然为1。cursor原来指向元素“b”，现在指向元素“c”。再次调用next()将输出元素“c”，元素“b”无法遍历到了。不过，如果删除的元素位于cursor所指元素之后，便不会出现某个元素无法遍历的情况。
五、迭代器问题的解决思路
当通过迭代器来遍历容器时，增加或删除容器中的元素，会导致不可预期的遍历结果。实际上，“不可预期”比直接出错更加可怕，有的时候运行正确，有的时候运行错误，一些隐藏很深、很难debug的bug就是这么产生的。那么，我们如何才能避免出现这种不可预期的运行结果呢？
Java采用这样的方式来解决的：增删元素之后，让遍历报错。怎么确定在遍历时候，容器有没有增删元素呢？凡是支持迭代器遍历，也就是实现了Iterable接口的容器，都定义了modCount这样一个成员变量，用来记录容器被修改的次数，容器每调用一次增加或删除元素的函数，就会给modCount加1。如下ArrayList中的remove()函数所示。
//ArrayList的remove()函数的代码实现
public E remove(int index) {
rangeCheck(index);
modCount++; //modCount加1
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData,
index, numMoved);
elementData[--size] = null;
return oldValue;
}
当通过调用容器上的iterator()函数来创建迭代器时，我们把容器上的modCount成员变量值传递给迭代器的expectedModCount成员变量，之后每次调用迭代器上的next()函数，我们都会调用checkForComodification()函数，检查容器上的modCount成员变量值是否等于迭代器上的expectedModCount成员变量值，也就是看，在创建完迭代器之后，modCount是否改变过。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
如果两个值不相同，那就说明容器要么增加了元素，要么删除了元素，之前创建的迭代器已经不能正确运行了，再继续使用就会产生不可预期的结果，所以我们选择fail-fast解决方式，抛出运行时异常ConcurrentModificationException，结束掉程序，让程序员尽快修复这个因为不正确使用迭代器而产生的bug。上述处理逻辑可以对照参看ArrayList的迭代器类Itr的代码实现。
六、利用迭代器安全删除元素
Iterator接口中除了最基本的hasNext()、next()方法之外，还定义了一个remove()方法。ArrayList的迭代器Itr中的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();
}
}
使用remove()方法，我们能够在遍历容器的同时，安全地删除容器中的元素。示例代码如下所示。
List<String> list = new ArrayList<>(); //第1行
list.addAll(Arrays.asList("a", "b", "c", "d")); //第2行
Iterator<String> itr = list.iterator(); //第3行
System.out.println(itr.next()); //"a" 第4行
System.out.println(itr.next()); //"b" 第5行
itr.remove(); //删除"b" 第6行
System.out.println(itr.next()); //"c" 第7行
上述代码的打印结果，如上述代码中的注释所示。remove()函数会删除cursor所指的前一个元素，也就是lastRet成员变量的值作为下标对应的元素。执行前两个next()函数之后，cursor等于2，lastRet等于1，此时cursor指向元素“c”。调用remove()函数，会删除元素“b”，cursor重新赋值为lastRet，也就是等于1，lastRet被赋值为-1。数组中的元素“c”和“d”往前移动一位。一番操作之后，cursor仍然指向元素“c”。如下图所示。
不过，Java迭代器中提供的remove()方法还是比较鸡肋的，作用有限。如ArrayList的迭代器Itr中的remove()函数的实现所示，它只能删除cursor指向的前一个元素，而且调用一个next()函数之后，只能跟着最多一个remove()操作，多次调用remove()操作会报错。这是因为调用完remove()函数之后，lastRet便变为了-1，而调用remove()函数时，会检查lastRet是否小于0，如果小于0，则报IllegalStateException异常。示例代码如下所示。
List<String> list = new ArrayList<>();
list.addAll(Arrays.asList("a", "b", "c", "d"));
Iterator<String> itr = list.iterator();
System.out.println(itr.next()); //"a"
System.out.println(itr.next()); //"b"
itr.remove(); //删除"b"
itr.remove(); //报IllegalStateException异常
按理来说，lastRet等于cursor-1，我们没必要记录lastRet。而且，在调用完remove()函数之后，我们也没必要将lastRet值设置为-1，我们可以将lastRet值设置为lastRet-1，这样就可以实现连续调用remove()函数多次。
ArrayList底层采用数组来实现，刚刚的分析一点问题都没有，实际上，LinkedList问题也不大，因为其基于双向链表来实现，也很容易追溯到前一个节点。但对于哈希表实现的Set来说，我们用lastRet记录上一次输出的元素，在调用remove()函数之后，我们将cursor设置为lastRet，但是lastRet无法指向上上次输出的元素了，因此我们就没法再次调用remove()函数了。为了统一各个容器的迭代器的remove()函数的表现，我们限制在调用next()函数之后只能调用remove()函数一次。
七、课后思考题
本节中讲到，List容器还支持增强版迭代器ListIterator。ListIterator中包含add()函数，支持通过迭代器添加元素，请研究一下源码，分析如下代码的运行结果。
List<String> list = new ArrayList<>();
list.addAll(Arrays.asList("a", "b", "c", "d"));
ListIterator<String> litr = list.listIterator();
System.out.println(litr.next());
litr.add("x");
litr.add("y");
System.out.println(litr.next());