Iterator(迭代器)模式

  当通过添加新类型的集合来扩展代码库时,你也许发现有必要通过增加迭代器进一步扩展你的扩展类.本章讨论对组合结构进行迭代的特殊情况.除了对新类型的集合进行迭代之外,在多线程环境下进行迭代会导致一些值得关注的问题.迭代看起来简单,但是其中还有很多需要探讨的地方,并不成熟.

 

  Iterator模式的意图在于为开发人员提供一种顺序访问集合元素的方法.

 

1.常规迭代:

  Java对迭代提供很多支持:

  (1)For,while和repeat循环,通常使用整数的索引;

  (2)Enumeration类(在java.util中);

  (3)Iterator类(也存在于java.util中),支持JDK1.2中的集合;

  (4)JDK 1.5中增加的对循环的扩展(foreach).

我们将使用Iterator类作为本章介绍重点,本部分主要关注扩展的for循环.

Iterator类有三个方法:hasNext(),next()和remove().如果Iterator不支持remove()操作,将会抛出UnsupportedOperationException异常.

  扩展的for循环的形式如下:

for(Type element:collection)

此处没有必要把element映射到特定类型, 这些操作都是隐含处理的.上述语句也适合于处理数组.提供扩展的for循环的类必须实现Iterable接口,并提供一个iterator()方法.

  下面代码演示Iterator类和改进的for循环:

package app.iterator;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ShowForeach
{
	public static void main(String[] args){
		ShowForeach example = new ShowForeach();
		example.showIterator();
		System.out.println():
		example.showForeach();
	}

	public void showIterator(){
		List names = new ArrayList();
		names.add("Fuser:1101");
		names.add("StarPress:991");
		names.add("Robot:1");

		System.out.println("JDK 1.2-style Iterator:");
		for(Iterator  it = names.iterator();it.hasNext();){
			String name = (String)it.next();
			System.out.println(name);
		}
	}

	public void showForeach(){
		List<String> names = new ArrayList<String>();
		names.add("Fuser:1101");
		name.add("StarPress:991");
		names.add("Robot:1");

		System.out.println("JDK 1.5-style Extended For Loop");
		for(String name:names)
			System.out.println(name);
	}
} 

  运行结果相同.

  到目前为止,Oozinoz应用程序继续使用老式的Iterator类;在保证客户拥有更新的编译器之前,我们不能更新该类.无论如何,你都可以从现在开始学习扩展的for循环.

 

2.线程安全的迭代:

  强大的应用程序经常使用线程来实现同时执行任务的操作.尤其值得关注的是,我们经常把那些耗时的任务放在后台处理,这样就不会影响前台GUI的显示效果.线程化是非常有用的,但同时也很危险.很多应用程序崩溃,其主要原因是线程化任务之间没有很好地协作.当多线程应用程序失效时,对集合进行迭代的方法肯定是潜在的故障源.

  java.util.collections中的集合类通过提供synchronized()方法来量度线程安全.从本质上看,该方法可返回底层集合的版本,以此防止两个线程同时去更改集合.

  集合和迭代器共同检测在迭代过程中列表是否变换,也就是说,列表是否被同步.为查看这个效果,假设Oozinoz Factory单例可以告诉我们在特定时间哪些机器是正常的,并可显示"正常的"机器列表.app.iterator.concurrent包中的范例代码把这个列表硬编码在方法upMachineNames()中.

 如下程序显示当前处于正常状态的机器列表,但是当程序显示这个列表时模拟机器被逐个发现的状况:

package app.iterator.concurrent;
import java.util.*;

public class ShowConcurrentIterator implements Runnable
{
	private List list;

	protected static List upMachineNames(){
		return new ArrayList(Arrays.asList(new String[]{
			"Mixer 1201","ShellAssembler1301",
			"StarPress1401","UnloadBuffer1501"}));
	}

	public static void main(String[] args){
		new ShowConcurrentIterator().go();
	}

    protected void go(){
		list = Collections.synchronizedList(upMachineNames());
		Iterator iter = list.iterator();
		int i = 0;
		while(iter.hasNext()){
			i++;
			if(i==2){
				new Thread(this).start();
				try{Thread.sleep(100);}
				catch(InterruptedException ignored){}
			}
			System.out.println(iter.next());
		}
	}

	public void run(){
		list.add(0,"Fuser1101");
	}
}

上述代码中main()方法构造该类的一个实例,并调用go()方法.该方法会对正常机器列表进行迭代处理,注意构造该列表的同步版本.代码模拟当该方法迭代处理这个列表时,其他机器逐个被发现的状况.run()方法修改本列表,在单个线程中运行.

  ShowConcurrentIterator程序会输出一个或者两个机器,然后崩溃:

D:\Java_Test>java app.iterator.concurrent.ShowConcurrentIterator
Mixer 1201
Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:4
49)
        at java.util.AbstractList$Itr.next(AbstractList.java:420)
        at app.iterator.concurrent.ShowConcurrentIterator.go(ShowConcurrentItera
tor.java:29)
        at app.iterator.concurrent.ShowConcurrentIterator.main(ShowConcurrentIte
rator.java:15)  

 

该程序之所以运行失败,是因为迭代器对象检测到迭代过程中列表已经被改变了.我们不必使用新线程就可以观察到这种现象.你可以创建一个程序,使其仅仅实现在迭代循环中更改处理集合时就崩溃.不过,在多线程应用环境中,当迭代器在遍历一个列表时,列表更加有可能会被意外的修改.

  对于列表迭代处理,我们可以开发线程安全的方法;首先需要注意到,ShowConcurrent-Iterator程序崩溃的原因是它使用迭代器.使用for循环对同步列表进行迭代处理不会触发程序以前遇到的异常,但是仍旧会出现问题:

package app.iterator.concurrent;
import java.util.*;

public class ShowConcurrentFor implements Runnable
{
	private List list;

	protected static List upMachineNames(){
		return new ArrayList(Arrays.asList(new String[]{
			"Mixer 1201","ShellAssembler1301",
			"StarPress1401","UnloadBuffer1501"}));
	}

	public static void main(String[] args){
		new ShowConcurrentFor().go();
	}

    protected void go(){
		System.out.println("This version lets new things " + "be added in concurrently:");

		list = Collections.synchronizedList(upMachineNames());
		display();
	}

    private void display(){
		for(int i=0;i<list.size();i++){
			if(i==1) { //simulate wake-up
			   new Thread(this).start();
			   try{Thread.sleep(100);}
			   catch(InterruptedException ignored){}
			}
			System.out.println(list.get(i));
		}
	}

	//在一个单独的进程中向列表中添加一个元素
	public void run(){
		list.add(0,"Fuser1101");
	}
}

运行本程序会得到如下输出:

D:\Java_Test>java app.iterator.concurrent.ShowConcurrentFor
This version lets new things be added in concurrently:
Mixer 1201
Mixer 1201
ShellAssembler1301
StarPress1401
UnloadBuffer1501

 

突破题:请解释ShowConcurrentFor程序的输出结果:

答:display()方法启动可以在任何时间被唤醒的新线程,尽管sleep()调用有助于确保run()过程在display()方法正在睡眠时运行.输出结果表明,在特定运行过程中,display()方法通过一次迭代保留了对CPU的控制权,并打印列表中索引0的数据项:

    Mixer1201

在这个时候,Second线程被唤醒,该线程将Fuser1101放在了列表的开头,并将其他机器名称下移一位.特别是将Mixer1201从索引0的位置移到了索引1的位置.

  当主线程重新获得控制权之后,display()方法将继续输出列表中的其余内容,即从索引1开始到列表结束:

Mixer 1201
ShellAssembler1301
StarPress1401
UnloadBuffer1501

 

    我们已经看到这个程序的两个版本:一个会崩溃,另一个会产生不正确输出.两个程序的输出结果都不理想,所以,需要考虑使用其他方法来保护被迭代的列表.

    在多线程应用程序中,有两种方法可以实现对集合的安全迭代处理.两个方法都涉及使用对象,有时被称作互斥量(mutex),参与竞争该对象控制权的线程将共享该对象.其中一个方法要求,每个线程在访问集合前都必须先获得对集合互斥量锁的控制.下面代码说明了这个方法:

 

package app.iterator.concurrent;
import java.util.*;

public class ShowConcurrentMutex implements Runnable
{
	private List list;

	protected static List upMachineNames(){
		return new ArrayList(Arrays.asList(new String[] {
			"Mixer1201","ShellAssembler1301","StarPress1401","UnloadBuffer1501"}));
	}

	public static void main(String[] args){
		new ShowConcurrentMutex().go();
	}

	protected void go(){
		System.out.println("This version synchronizes properly:");
		list = Collections.synchronizedList(upMachineNames());
		synchronized(list){
			display();
		}
	}

	private void display(){
		for(int i=0;i<list.size();i++){
			if (i==1) 
			{  //simulate wake-up
			  new Thread(this).start();
			  try
			  {
				Thread.sleep(100);
			  }
			  catch (InterruptedException ignored)
			  {
			  }
			}
			System.out.println(list.get(i));
		}
	}

	public void run(){
		synchronized (list){
			list.add(0,"Fuser1101");
		}
	}
}

 

输出结果如下:

D:\Java_Test>java app.iterator.concurrent.ShowConcurrentMutex
This version synchronizes properly:
Mixer1201
ShellAssembler1301
StarPress1401
UnloadBuffer1501

上面输出的结果与run()方法插入新对象之前的结果一致.程序的输出是一致的,没有重复内容,原因是本程序的处理逻辑要求run()方法等待display()方法中迭代完成之后再执行.尽管结果正确,但是设计思路有点不合适:我们通常不希望一个线程对集合进行迭代时,其他线程被阻塞.

 

替代解决方式是在一个互斥操作中对集合进行克隆,然后对该克隆体进行迭代,这样做的效率会更高.克隆集合通常比在遍历前等待其他线程完成对集合操作所花费的时间少得多.但是克隆一个集合,然后对克隆体进行迭代,这样可能会带来一些问题.

  ArrayList的clone()方法会产生一个浅复制(shallow copy):它们仅仅创建一个引用原来对象的新集合.当另外一个线程改变了我们所使用的对象的时候,对克隆体进行迭代还是会导致失败.但是在某些情况下,这种危险是很小的.例如,如果我们仅仅期望显示机器名的列表,在迭代克隆体的时候,机器名被其他线程修改的可能性极小,而且修改机器名也是不合理的.

  总的来说,我们已经介绍在多线程环境下迭代处理列表的四种方法.其中两种方法使用synchronized()方法,但是程序要么崩溃,要么产生不正确结果.后两种方法使用锁和克隆机制,也许会产生正确结果,但是也存在不同程度的负面影响.

 

突破题:请解释为什么不使用synchronized()方法,为什么不使用基于锁的方法?

答:反对使用syncrhonized()方法的一个论点是:如果使用for循环进行迭代,synchronized()方法会产生错误结果;如果没有捕获InvalidOperationException异常,则程序会崩溃.

  反对使用基于 锁的方法的论点是:提供线程安全迭代的设计思路依赖于访问集合的线程间的合作. 基于锁的方法关键的一点是线程不能协作.

  内置于Java语言的synchronized()方法和锁机制都不能方便多线程程序开发.如想进一步了解并发程序设计,请参考《Java并发编程》[Lea,2000]。

  Java及其类库为多线程环境的迭代提供坚实的支持，但是这种支持并没有降低并发设计的复杂性。Java类库对自身的很多集合提供强有力的迭代支持，但是对于开发者自己引入的集合类型，也许有必要同时引入对应的迭代器。