=a14c id=zoom> Java源码分析:深入探讨Iterator模式

java.util包中包含了系列重要集合类本文将从分析源码入手深入研究个集合类内部结构以及遍历集合迭代模式源码实现内幕

下面我们先简单讨论个根接口Collection然后分析个抽象类AbstractList和它对应Iterator接口并仔细研究迭代子模式实现原理

本文讨论源代码版本是JDK 1.4.2JDK 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 reAll(Collection c);


Object toArray思路方法很简单把集合转换成返回Object toArray(Object a)思路方法就有点复杂了首先返回Object仍然是把集合所有元素变成但是类型和参数a类型是相同比如执行:

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

得到o实际类型是String

其次如果参数a大小装不下集合所有元素返回将是个新如果参数a大小能装下集合所有元素则返回还是a但a内容用集合元素来填充尤其要注意是如果a大小比集合元素个数还多a后面部分全部被置为null

最后个最重要思路方法是iterator返回个Iterator(迭代子)用于遍历集合所有元素

用Iterator模式实现遍历集合


Iterator模式是用于遍历集合类标准访问思路方法它可以把访问逻辑从区别类型集合类中抽象出来从而避免向客户端暴露集合内部结构

例如如果没有使用Iterator遍历个思路方法是使用索引:

for( i=0; 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 erface 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可能返回ArrayIteratorSet可能返回SetIteratorTree可能返回TreeIterator但是它们都实现了Iterator接口因此客户端不关心到底是哪种Iterator它只需要获得这个Iterator接口即可这就是面向对象威力

Iterator源码剖析


让我们来看看AbstracyList如何创建Iterator首先AbstractList定义了个内部类(inner ):

private  Itr implements Iterator {
...
}


而iterator思路方法定义是:

public Iterator iterator {
  Itr;
}

因此客户端不知道它通过Iterator it = a.iterator;所获得Iterator真正类型

现在我们关心是这个申明为privateItr类是如何实现遍历AbstractList:

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

Itr类依靠3个变量(还有个隐含AbstractList引用)来实现遍历cursor是下次next时元素位置第次next将返回索引为0元素lastRet记录上次游标所在位置因此它总是比cursor少1

变量cursor和集合元素个数决定hasNext:

public boolean hasNext {
 cursor != size;
}

思路方法next返回是索引为cursor元素然后修改cursor和lastRet值:

public Object next {
checkForComodication;
try {
Object next = get(cursor);
lastRet = cursor;
 next;
} catch(IndexOutOfBoundsException e) {
checkForComodication;
throw  NoSuchElementException;
}
}

expectedModCount表示期待modCount值用来判断在遍历过程中集合是否被修改过AbstractList包含个modCount变量它值是0当集合每被修改次时(addremove等思路方法)modCount加1因此modCount如果不变表示集合内容未被修改

Itr化时用expectedModCount记录集合modCount变量此后在必要地方它会检测modCount值:

final void checkForComodication {
 (modCount != expectedModCount)
throw  ConcurrentModicationException;
}

如果modCount和开始记录在expectedModeCount中值不等介绍说明集合内容被修改过此时会抛出ConcurrentModicationException

这个ConcurrentModicationException是RuntimeException不要在客户端捕获它如果发生此异常介绍说明代码编写有问题应该仔细检查代码而不是在catch中忽略它

但是Iterator自身remove思路方法删除当前元素是完全没有问题在这个思路方法中会自动同步expectedModCount和modCount值:

public void remove {
...
AbstractList.this.remove(lastRet);
...
// 在了集合remove思路方法的后重新设置了expectedModCount:
expectedModCount = modCount;
...
}

要确保遍历过程顺利完成必须保证遍历过程中不更改集合内容(Iteratorremove思路方法除外)因此确保遍历可靠原则是只在个线程中使用这个集合或者在多线程中对遍历代码进行同步

最后给个完整举例:

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

如果你把第行代码ArrayList换成LinkedList或Vector剩下代码不用改动行就能编译而且功能不变这就是针对抽象编程原则:对具体类依赖性最小         

            (责任编辑:包春林)









TAG: java Java