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实现

下面代码展示IteratorArrayList中具体实现,我们来具体讲解一下。

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遍历集合的速度Iteratorfor要快。

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