Java源码阐明：深入探讨Iterator模式

副标题#e#

java.util包中包括了一系列重要的荟萃类。本文将从阐明源码入手，深入研究一个荟萃类的内部布局，以及遍历荟萃的迭代模式的源码实现黑幕。

下面我们先简朴接头一个根接口Collection，然后阐明一个抽象类AbstractList和它的对应Iterator接口，并仔细研究迭代子模式的实现道理。

本文接头的源代码版本是JDK 1.4.2，因为JDK 1.5在java.util中利用了许多泛型代码，为了简化问题，所以我们照旧接头1.4版本的代码。

荟萃类的根接口Collection

Collection接口是所有荟萃类的根范例。它的一个主要的接口要领是：

boolean add(Object c)

add()要领将添加一个新元素。留意这个要了解返回一个boolean，可是返回值不是暗示添加乐成与否。仔细阅读doc可以看到，Collection划定：假如一个荟萃拒绝添加这个元素，无论任何原因，都必需抛出异常。这个返回值暗示的意义是add()要领执行后，荟萃的内容是否改变了（就是元素有无数量，位置等变革），这是由详细类实现的。即：假如要领堕落，总会抛出异常；返回值仅仅暗示该要领执行后这个Collection的内容有无变革。

雷同的尚有：

boolean addAll(Collection c);
boolean remove(Object o);
boolean removeAll(Collection c);
boolean remainAll(Collection c);

Object[] toArray()要领很简朴，把荟萃转换成数组返回。Object[] toArray(Object[] a)要领就有点巨大了，首先，返回的Object[]仍然是把荟萃的所有元素酿成的数组，可是范例和参数a的范例是沟通的，好比执行：

String[] o = (String[])c.toArray(new String[0]);

获得的o实际范例是String[]。

其次，假如参数a的巨细装不下荟萃的所有元素，返回的将是一个新的数组。假如参数a的巨细能装下荟萃的所有元素，则返回的照旧a，但a的内容用荟萃的元素来填充。尤其要留意的是，假如a的巨细比荟萃元素的个数还多，a后头的部门全部被置为null。

最后一个最重要的要领是iterator()，返回一个Iterator（迭代子），用于遍历荟萃的所有元素。

用Iterator模式实现遍历荟萃

Iterator模式是用于遍历荟萃类的尺度会见要领。它可以把会见逻辑从差异范例的荟萃类中抽象出来，从而制止向客户端袒露荟萃的内部布局。

譬喻，假如没有利用Iterator，遍历一个数组的要领是利用索引：

for(int i=0; i<array.size(); i++) { ... get(i) ... }

而会见一个链表（LinkedList）又必需利用while轮回：

while((e=e.next())!=null) { ... e.data() ... }

以上两种要领客户端都必需事先知道荟萃的内部布局，会见代码和荟萃自己是紧耦合，无法将会见逻辑从荟萃类和客户端代码中疏散出来，每一种荟萃对应一种遍历要领，客户端代码无法复用。

更可怕的是，假如今后需要把ArrayList改换为LinkedList，则本来的客户端代码必需全部重写。

为办理以上问题，Iterator模式老是用同一种逻辑来遍历荟萃：

for(Iterator it = c.iterater(); it.hasNext(); ) { ... }

机密在于客户端自身不维护遍历荟萃的"指针"，所有的内部状态（如当前元素位置，是否有下一个元素）都由Iterator来维护，而这个Iterator由荟萃类通过工场要领生成，因此，它知道如何遍历整个荟萃。

客户端从不直接和荟萃类打交道，它老是节制Iterator，向它发送"向前"，"向后"，"取当前元素"的呼吁，就可以间接遍历整个荟萃。

首先看看java.util.Iterator接口的界说：

public interface Iterator {
　boolean hasNext();
　Object next();
　void remove();
}

依赖前两个要领就能完成遍历，典范的代码如下：

for(Iterator it = c.iterator(); it.hasNext(); ) {
　Object o = it.next();
　// 对o的操纵...
}

在JDK1.5中，还对上面的代码在语法上作了简化：

// Type是详细的范例，如String。
for(Type t : c) {
// 对t的操纵...
}

每一种荟萃类返回的Iterator详细范例大概差异，Array大概返回ArrayIterator，Set大概返回SetIterator，Tree大概返回TreeIterator，可是它们都实现了Iterator接口，因此，客户端不体贴到底是哪种Iterator，它只需要得到这个Iterator接口即可，这就是面向工具的威力。

#p#副标题#e#

Iterator源码分解

让我们来看看AbstracyList如何建设Iterator。首先AbstractList界说了一个内部类（inner class）：

private class Itr implements Iterator {
...
}

而iterator()要领的界说是：

public Iterator iterator() {
　return new Itr();
}

因此客户端不知道它通过Iterator it = a.iterator();所得到的Iterator的真正范例。

此刻我们体贴的是这个申明为private的Itr类是如何实现遍历AbstractList的：

private class Itr implements Iterator {
　int cursor = 0;
　int lastRet = -1;
　int expectedModCount = modCount;
}

#p#分页标题#e#

Itr类依靠3个int变量（尚有一个隐含的AbstractList的引用）来实现遍历，cursor是下一次next()挪用时元素的位置，第一次挪用next()将返回索引为0的元素。lastRet记录上一次游标地址位置，因此它老是比cursor少1。

变量cursor和荟萃的元素个数抉择hasNext()：

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

要领next()返回的是索引为cursor的元素，然后修改cursor和lastRet的值：

public Object next() {
　checkForComodification();
　try {
　　Object next = get(cursor);
　　lastRet = cursor++;
　　return next;
　} catch(IndexOutOfBoundsException e) {
　　checkForComodification();
　　throw new NoSuchElementException();
　}
}

expectedModCount暗示等候的modCount值，用来判定在遍历进程中荟萃是否被修悔改。AbstractList包括一个modCount变量，它的初始值是0，当荟萃每被修改一次时（挪用add，remove等要领），modCount加1。因此，modCount假如稳定，暗示荟萃内容未被修改。

Itr初始化时用expectedModCount记录荟萃的modCount变量，从此在须要的处所它会检测modCount的值：

final void checkForComodification() {
　if (modCount != expectedModCount)
　　throw new ConcurrentModificationException();
}

假如modCount与一开始记录在expectedModeCount中的值不等，说明荟萃内容被修悔改，此时会抛出ConcurrentModificationException。

这个ConcurrentModificationException是RuntimeException，不要在客户端捕捉它。假如产生此异常，说明措施代码的编写有问题，应该仔细查抄代码而不是在catch中忽略它。

可是挪用Iterator自身的remove()要领删除当前元素是完全没有问题的，因为在这个要领中会自动同步expectedModCount和modCount的值：

public void remove() {
...
AbstractList.this.remove(lastRet);
...
// 在挪用了荟萃的remove()要领之后从头配置了expectedModCount：
expectedModCount = modCount;
...
}

要确保遍历进程顺利完成，必需担保遍历进程中不变动荟萃的内容（Iterator的remove()要领除外），因此，确保遍历靠得住的原则是只在一个线程中利用这个荟萃，可能在多线程中对遍历代码举办同步。

最后给个完整的示例：

Collection c = new ArrayList();
c.add("abc");
c.add("xyz");
for(Iterator it = c.iterator(); it.hasNext(); ) {
　String s = (String)it.next();
　System.out.println(s);
}

假如你把第一行代码的ArrayList换成LinkedList或Vector，剩下的代码不消窜改一行就能编译，并且成果稳定，这就是针对抽象编程的原则：对详细类的依赖性最小。