从`ArrayList`中了解Java的迭代器

2020-05-17 16:01:24来源：博客园阅读 ()

从`ArrayList`中了解Java的迭代器

目录

什么是迭代器

迭代器的设计意义

ArrayList对迭代器的实现

增强for循环和迭代器

参考链接

什么是迭代器

Java中的迭代器——Iterator是一个位于java.util包下的接口，这个接口里声明了三个重要的方法hasNext()、next()、remove()。下面看看Iterator的声明

public interface Iterator<E> {
    // 判断集合中是否有下一个元素
    boolean hasNext();
	// 获取集合中的下一个元素
    E next();
    // 从集合中移除迭代器返回的最后一个元素
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

值得提一下的是remove()方法，remove()方法在接口中使用了default关键字修饰，这是JDK1.8的一个新特性——接口的方法可以拥有方法体（即默认实现）。当你使用一个类去实现Iterator的时候，如果你不去重写它的remove()方法的话，再调用remove()就会去调用接口里的默认实现，此时程序会抛出UnsupportedOperationException异常。

设计迭代器的意义

首先，迭代器这个东西是针对集合设计的。我们知道，List家族，Set家族，Map家族他们的底层设计都是不一样的，那么在遍历它们的时候，方式也自然不会一样，既然大家都有遍历的需求，那么就可以把这个需求统一一下，设计一个接口来把这些方法抽象出来，于是Iterator这个接口就应运而出。迭代器的设计初衷是：提供一种方法对一个容器对象中的各个元素进行访问，而又不暴露该对象容器的内部细节。

`ArrayList`对迭代器的实现

很多集合都实现了Iterator接口，实现了属于自己的迭代器，在本篇文章中我们以ArrayList中的迭代器为例讲述ArrayList是如何实现自己的迭代器的。

基本使用

想一想，你平时在使用迭代器去遍历ArrayList的时候是怎么做的，是不是像下面这样

// 首先有个ArrayList
ArrayList<Object> list = new ArrayList<>();
// 然后获取到迭代器
Iterator<Object> iterator = list.iterator();
// 再开始遍历ArrayList，使用hasNext()判断ArrayList中是否有下一个元素
while (iterator.hasNext()){
    // 如果ArrayList中有下一个元素，就使用next()方法获取下一个元素
    Object e = iterator.next();
    if ("条件".equals(e)){
        // 如果元素e满足某种条件就使用remove()删除该元素
        iterator.remove();
    }
}

`Iterable`接口

看看下面获取迭代器的这段代码

// 获取迭代器
Iterator<Object> iterator = list.iterator();

可以看到 list.iterator()给我们返回了一个迭代器对象，那么这个iterator()方法是个什么样的方法呢，通过查看源码可以发现，iterator()方法是来自于接口Iterable的一个方法，这个Iterable的声明是这样的

public interface Iterable<T> {
    Iterator<T> iterator();
    
    // 其他方法...
}

其中，iterator()方法返回的就是一个Iterator迭代器。实现了Iterable接口的类我们称它为可迭代的类，该类的对象我们称之为可迭代对象。

`Itr`类及其和接口`Iterator`的关系

我们接着再看看iterator()方法的源码

public Iterator<E> iterator() {
    return new Itr();
}

你会发现发现iterator()方法只是给我们new了一个Itr类的对象，然后就把这个对象的引用返回给我们了。那我们就顺藤摸瓜看看Itr()这个构造方法，看看这个Itr类到底是个啥玩意。

通过查看Itr类的源码我们可以发现Itr类是ArrayList中的一个私有的内部类，并且这个类实现了前面说的Iterator接口，下面看下Itr类的具体源码

private class Itr implements Iterator<E> {
    int cursor;       // 下一个要返回的元素的索引
    int lastRet = -1; // 返回的最后一个元素的索引；如果没有这个值就是-1
    int expectedModCount = modCount; // 期望ArrayList的结构被改变（新增，删除元素都会改变ArrayList的结构）的次数，初始值等于modCount

    // 构造方法
    Itr() {}

    // hasNext方法的具体实现
    public boolean hasNext() {
        return cursor != size;
    }

    // next方法的具体实现
    @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];
    }

    // 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();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        // ...
    }

    // 检查在使用迭代器遍历ArrayList的同时是否有其他的操作改动了ArrayList的结构
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

下面来逐一解释Itr里的成员变量和方法

`Itr`类中的成员变量

`cursor`

int cursor;       // 下一个要返回的元素的索引

由于cursor是一个int类型的成员变量，所以他的初始值是0，也就是说，一开始，下一个要返回的元素的索引是0，实际上就是ArrayList的第一个元素。

`lastRet`

int lastRet = -1; // 返回的最后一个元素的索引；如果没有这个值就是-1

lastRet这个变量存的是迭代器上一个返回的元素的索引，一开始这个值是-1，也就是说还没有使用next()方法返回ArrayList的下一个元素时，这个值就是-1，当我们调用next方法返回ArrayList的下一个元素后，可以从next()方法的源码里看到cursor会+1，然后lastRet被赋值为cursor加一之前的值，所以lastRet里存的就是上一个返回的元素的索引。

`expectedModCount`

// 期望ArrayList的结构被改变（新增，删除元素都会改变ArrayList的结构）的次数，初始值等于modCount
int expectedModCount = modCount;

expectedModCount从字面意思上来看，表示期望被改变的次数，然后它的默认值是modCount。这个modCount是何许人也？我们点进去看看，原来它是ArrayList的父类AbstractList的成员变量，它长这样

protected transient int modCount = 0;

modCount它记录了整个List的结构被改变的次数，我们常用的add()方法，remove()方法都会改动List的结构，相应的，这些方法被调用一次后，modCount就会+1，用以记录List的结构被改变的次数。

`Itr`类中的方法

`hasNext()`

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

hasNext()的实现其实很简单，就是判断下一个元素的索引是否和ArrayList的大小相等。不相等的话，就说明ArrayList中还有下一个元素相等的话，就说明遍历已经走到尽头了，ArrayList中没有下一个元素了。

`checkForComodification()`

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

checkForComodification()方法的作用就是检查迭代器对ArrayList进行遍历的过程中是否有其他的操作对ArrayList本身的结构进行了修改，要知道这种修改操作是不被允许的，如果你这么做了，会导致迭代器在遍历的时候获取或者删除的元素并不是你想要的那个元素，甚至会发生索引越界的现象。那么设计者是如何避免这种不当的情况呢？这就要用到前面说到的expectedModCount和modCount这两个变量了，还记得吗，在new一个Itr对象的时候，expectedModCount的初始值就是modCount的值，前面说了，modCount记录了ArrayList本身结构被改变的次数，那么只要在我们使用迭代器遍历ArrayList的时候，这个值没有发生变化，这说明这期间没有其他的操作来改变ArrayList的结构（比如删除、新增元素），迭代器的这次遍历是安全的。但是与之相反的，在迭代器遍历ArrayList期间，modCount的值发生了变化（有其他的操作改变了ArrayList的结构），modCount的值不等于expectedModCount的值了，这就说明迭代器的这次遍历是不安全，这次遍历应该被停止掉。于是，当modCount != expectedModCount的时候，程序抛出了一个ConcurrentModificationException异常，终止掉了迭代器的这次遍历。

`next()`

@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];
}

梳理一下next()方法的执行过程：

进方法之后，调用checkForComodification()方法检查下本次遍历是否是安全的，如果是安全的，执行第2步，否则checkForComodification()方法里会抛出ConcurrentModificationException异常，阻止这次遍历的进行
声明一个局部变量i，i的值就是cursor的值
判断i（cursor）的值是不是大于或者等于ArrayList的大小，如果是的，就表明迭代器已经遍历完了整个ArrayList了，按道理来说，不应该再调用next()方法获取下一个值了（因为已经没有下一个值了），于是这种情况下，程序就抛出了一个NoSuchElementException异常。从这里也可以看到，对于一个已经被迭代器遍历完的集合，如果你还试图去获取下一个元素，程序会抛出NoSuchElementException异常。
声明了一个Object[]类型的成员变量elementData，这个数组实际上指向了ArrayList内部用来存储元素的数组，就是下面这个
```
transient Object[] elementData; // 非私有以简化嵌套类访问
```
判断cursor的值是否大于elementData的大小，如果是，抛出ConcurrentModificationException异常
cursor的值+1
将lastRet的值设置为i的值
返回ArrayList的索引为i的元素

`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()方法的过程没啥好说的，值得注意的是：

remove()本质上调用的是ArrayList的remove(int index)方法
调用完ArrayList的remove(int index)方法之后，modCount的值会发生变化（+1），这时再将+1后的modCount赋值给expectedModCount以保证接下来的遍历顺利进行下去。

总结：在试用迭代器遍历集合时，如果想要删除集合中的元素，必须使用迭代器提供的remove()方法，否则程序将抛出ConcurrentModificationException异常。

增强for循环和迭代器

背景

增强for循环是JDK1.5以后出来的新特性，是一种高级的for循环，用来方便遍历数组和集合的。

遍历数组

下面先用增强for循环遍历下数组看下，看下示例代码

public  static void testArray(){
    String[] s = {"a", "b", "c", "d"};
    
    for (String e : s) {
        System.out.println(e);
    }
}

输出结果和普通for循环是一样的

a
b
c
d

让我们来看下上面这段示例代码的反编译结果，看看编译器实际执行的代码是怎么样的

public static void testArray() {
    String[] s = new String[]{"a", "b", "c", "d"};
    String[] var1 = s;
    int var2 = s.length;

    for(int var3 = 0; var3 < var2; ++var3) {
        String e = var1[var3];
        System.out.println(e);
    }
}

可以很明显的看到，如果你是用增强for循环来遍历数组的话，实际上编译器执行的代码还是使用普通for循环来遍历这个数组。

遍历可迭代对象

这里仍然以ArrayList举例说明，我们看下使用增强for循环来遍历可迭代对象的示例代码

public static void testList(){
    List<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");

    for (String e : list) {
        System.out.println(e);
    }
}

这段代码的输出结果同上

a
b
c
d

同样的，让我们来看看这个示例代码的反编译结果

public static void testList() {
    List<String> list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    Iterator var1 = list.iterator();

    while(var1.hasNext()) {
        String e = (String)var1.next();
        System.out.println(e);
    }
}

可以很明显的看到，当增强for循环遍历的是一个可迭代的对象时，实际上是使用迭代器来遍历这个可迭代对象的。

使用总结

从上面的两个示例代码的反编译结果来看，我们不难得出下面这几个结论

当增强for循环遍历的是一个数组的时候，实际上还是使用的普通for循环来遍历
当增强for循环遍历的是一个可迭代的对象的时候，实际上使用的是迭代器来遍历这个对象
在增强for循环遍历可迭代对象的时候，不可以执行删除元素的操作，否则程序会抛出java.util.ConcurrentModificationException异常
增强for循环遍一个对象的时候，这个对象不可以为null，否则程序会抛出NullPointerException异常