深入理解Java迭代器

逃离我推掉我的手 2022-06-14 23:57 234阅读 0赞

迭代器是一种设计模式，它可以使得对于序列类型的数据结构的遍历行为与被遍历的对象分离，即我们无需关心该序列的底层结构是什么样子的。只要拿到这个对象，使用迭代器就可以遍历这个对象的内部。当你需要访问一个聚合对象，而且不管这些对象是什么都需要遍历的时候，就应该考虑使用迭代器模式。

## **1、Java迭代器接口** ##

我们先来看下Collection接口的定义：

public interface Collection<E> extends Iterable<E>

首先，它使用了一个类型参数，其次，它实现了Iterable接口，我们再来简单看下Iterable<E>接口的定义：

public interface Iterable<T> {  
         Iterator<T>  iterator();  
    }

我们可以看到这个接口只定义了一个方法，这个方法要求我们返回一个实现了Iterator<T>接口的对象，所以我们看下Iterator的定义：

public interface Iterator<E> {  
        boolean hasNext();  
        E next();  
        void remove();  
    }

上面我们一共提到了两个和迭代器相关的接口：Iterable接口和Iterator接口，从字面意义上来看，前者的意思是“可迭代的”，后者的意思是“迭代器”。所以我们可以这么理解这两个接口：实现了Iterable接口的类是可迭代的；实现了Iterator接口的类是一个迭代器。

迭代器就是一个我们用来遍历集合中的对象的东西。也就是说，对于集合，我们不是像对原始类型数组那样通过直接访问元素来迭代，而是通过迭代器来遍历对象。这么做的好处是将对于集合类型的遍历行为与被遍历的集合对象分离，这样一来我们无需关心该集合类型的具体实现是怎样的。只要获取这个集合对象的迭代器，便可以遍历这个集合中的对象了。而像遍历对象的顺序这些细节，全部由它的迭代器来处理。现在我们来梳理一下前面提到的这些东西：首先，Collection接口实现了Iterable<E>接口，这意味着所有实现了Collection接口的具体集合类都是可迭代的。

既然要迭代，我们就需要一个迭代器来遍历相应集合中的对象，所以Iterable<E>接口要求我们实现iterator方法，这个方法要返回一个迭代器对象。一个迭代器对象也就是实现了Iterator<E>接口的对象，这个接口要求我们实现hasNext()、next()、remove()这三个方法。其中hasNext方法判断是否还有下一个元素（即是否遍历完对象了），next方法会返回下一个元素（若已经没有下一个元素了，调用它会抛出一个NoSuchElementException异常），remove方法用于移除最近一次调用next方法返回的元素（若没有调用next方法而直接调用remove方法会报错）。我们可以想象在开始对集合进行迭代前，有一个指针指向集合第一个元素的前面，第一次调用next方法后，这个指针会“扫过”第一个元素并返回它，调用hasNext方法就是看这个指针后面还有没有元素了。也就是说这个指针始终指向刚遍历过的元素和下一个待遍历的元素之间。通常，迭代一个集合对象的代码是这个样子的：

Collection<String> c = ...;  
    Iterator<String> iter = c.iterator();  
    while (iter.hasNext()) {  
        String element = iter.next();  
        do something with element;  
    }

Java SE 5.0为我们提供了for each语法，以上代码段的等价但更加简洁的版本：

for (String element : c) {  
        do something with element;  
    }

可以看出，使用for each循环语句的优势在于更加简洁，更不容易出错，不必关心下标的起始值和终止值。for each不是关键字，关键字还是for，语句是由iterator实现的。

## **2、迭代器遍历陷阱** ##

使用迭代器遍历集合需要特别注意的问题在于remove()方法的使用上。以下代码运行中抛出异常：

List list = ...;  
    for(Iterator iter = list.iterator(); iter.hasNext();) {  
        Object obj = iter.next();  
        ...  
        if(***) {  
            list.remove(obj);  
        }  
    }

在执行了remove方法之后，再去执行循环iter.next()的时候，报Java.util.ConcurrentModificationException（如果remove的是最后一个元素，就不会再去执行next()操作了），为了探索问题的根源，来看一下Iterator接口和Collection接口的源码：

public interface Iterator<E> {   
        boolean hasNext();  
        E next();  
        void remove();  
    }  
    public interface Collection<E> extends Iterable<E> {   
        ...  
        Iterator<E> iterator();  
        boolean add(E o);  
        boolean remove(Object o);  
        ...  
    }

这里有两个remove方法，一般删除和添加元素时习惯调用具体集合自己的方法，也就是Collection接口中定义的那个remove方法。例如：

List list = new ArrayList();   
    list.add(...);   
    list.remove(...);

但是，如果在使用迭代器循环遍历的过程中调用集合自己的remove()方法，就会导致循环出错，因为循环过程中list.size()的大小变化了，就导致了错误。 所以，如果想在循环语句中删除集合中的某个元素，就要用迭代器iterator提供的remove()方法，因为它的remove()方法不仅会删除元素，还会维护一个标志，用来记录目前是不是可删除状态，例如，你不能连续两次调用它的remove()方法，调用之前至少有一次next()方法的调用。同理，使用迭代器循环遍历的过程中也不能调用集合自己的add()方法。

## **3、iterator原理与快速失败** ##

在用iterator遍历容器的时候，实际上是在这个迭代器上创建了一个数据结构，iterator用这个数据结构来访问这个容器，这时候如果你用容器自身的add和remove方法进行增减时，这个iterator产生的数据结构不会发生变化，所以迭代器循环会抛出异常。如果用iterator迭代器本身进行增减，则相应的数据结构会发生变化。

Iterator是工作在一个独立的线程中，并且拥有一个mutex锁。Iterator被创建之后会建立一个指向原来集合的单链索引表，当原来的集合中元素数量发生变化时，这个索引表的内容不会同步改变，当索引指针往后移动的时候就会出现找不到要迭代对象的情况。按照“快速失败”原则（“快速失败”这个词在Java API官方文档中经常出现），Iterator此时会抛出java.util.ConcurrentModificationException异常。所以Iterator在工作的时候是不允许被迭代的集合发生改变的，但你可以使用Iterator本身提供的方法remove()或add()来删除或添加对象，Iterator.remove()方法会在删除当前迭代对象的同时更新索引表。

“快速失败”是指某个线程在迭代Collection的时候，通常不允许其他线程修改该Collection的内容，因为这样迭代器迭代出来的结果就会不准确，如用iterator迭代collection的时候，iterator就是另外起的一个线程，由这个另起的线程正在遍历collection，如果此时用collection.remove(obj)这个方法修改了collection里面的内容，就会出现ConcurrentModificationException异常，这时候该迭代器就快速失败。