java源码详解iterator

1、迭代器模式

在将jdk中的iterator之前必须先讲讲迭代器模式。因为iterator就是迭代器模式的具体实现。我们都知道在java中的集合有很多种，比如ArrayList,LinkedList,HashSet等等。他们底层的数据结构都不一样，有的是数组，有的是双向链表。所以我们有必要抽象出一种统一的方法来遍历所有不同类型的集合，即便他底层的内容不一样也没关系。那么Iterator的迭代器模式就是做这个事情的。具体的迭代器模式详解可以看到这里详细学习。

2、Iterator

抛开设计模式，我们来看下jdk中是如何实现Iterator的。首先我们可以看到有一个叫Iterator的接口：

image-20210131113119372

他有两个重要的方法，只要实现这两个方法就可以遍历整个集合，而不关心具体集合内部的细节。

  • hasNext(); 是否还有下一个元素。
  • next(); 返回下一个元素。

那么Iterator是怎么被new出来的呢？从下图看所有的Collection都实现了Iterable接口。注意这个是Iterable，而不是Iterator。

Iterable继承图

Iterable有一个重要的方法iterator()，这个方法是用于创建Iterator实例的方法。根据上面的类图，那么意味着所有的Collection都有一个关于如何创建Iterator的具体实现。

Iterable接口

3、ArrayList的Iterator实现

下面代码展示Iterator在ArrayList中具体实现，我们来具体讲解一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 *
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

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

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

    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) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

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

在ArrayList中存在一个私有的内部类，这个内部类就是Iterator的具体实现。实现其实非常简单，有一个cursor的变量，其核心维护的是一个数组下标。如果cursor不大于数组本身的大小，那么hasNext方法就返回true。而next方法就是将cursor加1，然后返回下一个元素。

4、ListIterator

Iterator还有另外一种存在形式ListIterator。因为单纯的Iterator比较简单只能在一个方向上进行遍历。这对于ArrayList或者LinkedList这种有序集合来说完全没法发挥出该有的实力。于是ListIterator孕育而生，不但支持双向的遍历，还能在迭代时修改数组和获取当前迭代的位置。

ListIterator类图

对于LinkedList来说他的iterator方法本质上就是获取到了一个ListIterator的实现，下面我们来详细看下它的next方法，这个实现很好的利用了双向链表的特性，当需要获取下一个资源的时候，直接给这个节点的后驱返回给调用者就好了，异常简单。

1
2
3
4
5
6
7
8
9
public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();
    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

5、LinkedList遍历速度对比

如果拿for或者Iterator来遍历LinkedList，哪个更快呢。如果使用普通的for循环的话，每次获取元素是使用get(index)方法。而LinkedList对于get(index)方法的实现是需要将index之前的元素全部访问一遍才能得到指定的元素。这意味着随着集合存储的数据规模越大，获取一个指定元素的时间会越长。这对使用普通for循环遍历LinkedList来说是一个灾难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* LinkedList获取指定元素
*/
   public E get(int index) {
       checkElementIndex(index);
       return node(index).item;
   }

   /**
    * Returns the (non-null) Node at the specified element index.
    */
   Node<E> node(int index) {
       // assert isElementIndex(index);
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else {
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
   }

结合上面第4小节所说，LinkedList遍历集合的速度Iterator比for要快。

原文链接：https://www.jdkdownload.com/jdk_iterator.html