java集合【2】—— iterator接口详解

微信扫一扫,分享到朋友圈

java集合【2】—— iterator接口详解

一、 iterator 接口介绍

iterator 接口,也是集合大家庭中的一员。和其他的 MapCollection 接口不同, iterator 主要是为了方便遍历集合中的所有元素,用于迭代访问集合中的元素,相当于定义了遍历元素的规范,而另外的 MapCollection 接口主要是定义了存储元素的规范。

还记得么?之前说的 iterable 接口,有一个方法就是叫 iterator() ,也是返回 iterator 对象。

迭代:不断访问集合中元素的方式,取元素之前先判断是否有元素,有则取出来,没有则结束,不断循环这个过程,直到遍历完里面所有的元素。

接口定义的方法如下:

boolean hasNext(); // 是否有下一个元素
E next();   // 获取下一个元素
// 移除元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 对剩下的所有元素进行处理,action则为处理的动作,意为要怎么处理
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}

但是值得注意的是,集合类的整体不是继承了 iterator 接口,而是继承了 iterable 接口,通过 iterable 接口的方法返回 iterator 的对象。值得注意的是, iteratorremove() 方法,是迭代过程中 唯一安全 的修改集合的方法,为何这样说?

如果使用for循环索引的方式遍历,删除掉一个元素之后,集合的元素个数已经变化,很容易出错。例如

for(int i=0;i<collection.size();i++){
if(i==2){
collection.remove(i);
}
}

iteratorremove() 方法则不会出错,因为通过调用 hasNext()next() 方法,对指针控制已经处理得比较完善。

二、为什么需要iterator接口

首先,我们知道 iterator 接口是为了定义遍历集合的规范,也是一种抽象,把在不同集合的遍历方式抽象出来,这样遍历的时候,就不需要知道不同集合的内部结构。

为什么需要抽象?

假设没有 iterator 接口,我们知道,遍历的时候只能通过索引,比如

for(int i=0;i<array.size();i++){
T item = array[i];
}

这样一来,耦合程度比较高,如果使用的数据结构变了,就要换一种写法,不利于维护已有的代码。如果没有 iterator ,那么客户端需要维护指针,相当于下放了权限,会造成一定程度的混乱。抽象则是把遍历功能抽取出来,交给 iterator 处理,客户端处理集合的时候,交给更“专业”的它,it do it well.

三、iterator接口相关接口

3.1 ListIterator

ListIterator 继承于 Iterator 接口,功能更强大,只能用于访问各种 List 类型,使用 List 类型的对象 list ,调用 listIterator() 方法可以获取到一个指向 list 开头的 ListIterator

从上面图片接口看,这个接口具有访问下一个元素,判断是否有下一个元素,是否有前面一个元素,判断是否有前一个元素,获取下一个元素的索引,获取上一个元素的索引,移除元素,修改元素,增加元素等功能。和普通的 Iterator 不一样的是, ListIterator 的访问指针可以向前或者向后移动,也就是双向移动。

boolean hasNext();  //是否还有元素
E next();   //获取下一个元素
boolean hasPrevious();  //是否有上一个元素
E previous();   // 获取上一个元素
int nextIndex();    //获取下一个索引
int previousIndex();    //获取上一个索引
void remove();  //移除
void set(E e); //更新
void add(E e); //添加元素

测试代码如下:

List<String> list =
new ArrayList<String>(Arrays.asList("Book","Pen","Desk"));
// 把指针指向第一个元素
ListIterator<String> lit = list.listIterator(1);
while(lit.hasNext()){
System.out.println(lit.next());
}
System.out.println("===================================");
//指针指向最后一个元素列表中的最后一个元素修改ChangeDesk。
lit.set("ChangeDesk");
// 往前面遍历
while(lit.hasPrevious()){
System.out.println(lit.previous());
}

输出如下:

Pen
Desk
===================================
ChangeDesk
Pen
Book

如果点开 ArrayList 的源码,看到与 ListIterator 相关的部分,我们会发现其实 ArrayList 在底层实现了一个内部类 ListItr ,继承了 Itr ,实现了 ListIterator 接口。这个 Itr 其实就是实现了 Iterator ,实现了基本的List迭代器功能,而这个 ListItr 则是增强版的专门为 List 实现的迭代器。里面使用 cursor 作为当前的指针(索引),所有函数功能都是操作这个指针实现。

private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
// 设置当前指针
cursor = index;
}
public boolean hasPrevious() {
// 不是第一个元素就表明有前一个元素
return cursor != 0;
}
// 获取下一个元素索引
public int nextIndex() {
return cursor;
}
// 获取前面一个元素索引
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
//检查是否被修改
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
// 返回前一个元素
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}

我们可以看到,在上面方法中,有很多校验,比如 checkForComodification() ,意为检查是否被修改,list中的元素修改有可能导致数组越界。

3.2 SpitIterator

准确地来说, SpitIteratorIterator 并没有什么关系,只是两个功能上有类似。 SpitIterator 主要是定义类将集合分割成多个集合,方便并行计算。

3.2.1 SpitIterator源码方法解析

public interface Spliterator<T> {
// 顺序处理每一个元素,参数是处理的动作,如果还有元素需要处理则返回true,否则返回false
boolean tryAdvance(Consumer<? super T> action);
// 依次处理剩下的元素
default void forEachRemaining(Consumer<? super T> action) {
do { } while (tryAdvance(action));
}
// 最重要的方法,用来分割集合
Spliterator<T> trySplit();
//估算还有多少元素需要遍历处理
long estimateSize();
// 获取准确的元素,如果不能获取准确的,则会返回估算的
default long getExactSizeIfKnown() {
return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
}
// 表示该Spliterator有哪些特性,这个像是个拓展功能,更好控制和优化Spliterator使用
int characteristics();
// 判断是否有哪些特性
default boolean hasCharacteristics(int characteristics) {
return (characteristics() & characteristics) == characteristics;
}
// 如果这个Spliterator的源具有已排序的特征,那么这个方法将返回相应的比较器。如果源按自然顺序排序,则返回     // null。否则,如果源未排序,则抛出IllegalStateException。
default Comparator<? super T> getComparator() {
throw new IllegalStateException();
}
public static final int ORDERED    = 0x00000010;
public static final int DISTINCT   = 0x00000001;
public static final int SORTED     = 0x00000004;
public static final int SIZED      = 0x00000040;
public static final int NONNULL    = 0x00000100;
public static final int IMMUTABLE  = 0x00000400;
public static final int CONCURRENT = 0x00001000;
public static final int SUBSIZED = 0x00004000;
}

使用的方法例子如下:

public static void spliterator(){
List<String> list = Arrays.asList("1", "2", "3","4","5","6","7","8","9","10");
// 获取可迭代器
Spliterator<String> spliterator = list.spliterator();
// 一个一个遍历
System.out.println("tryAdvance: ");
spliterator.tryAdvance(item->System.out.print(item+" "));
spliterator.tryAdvance(item->System.out.print(item+" "));
System.out.println("\n-------------------------------------------");
// 依次遍历剩下的
System.out.println("forEachRemaining: ");
spliterator.forEachRemaining(item->System.out.print(item+" "));
System.out.println("\n------------------------------------------");
// spliterator1:0~10
Spliterator<String> spliterator1 = list.spliterator();
// spliterator1:6~10 spliterator2:0~5
Spliterator<String> spliterator2 = spliterator1.trySplit();
// spliterator1:8~10 spliterator3:6~7
Spliterator<String> spliterator3 = spliterator1.trySplit();
System.out.println("spliterator1: ");
spliterator1.forEachRemaining(item->System.out.print(item+" "));
System.out.println("\n------------------------------------------");
System.out.println("spliterator2: ");
spliterator2.forEachRemaining(item->System.out.print(item+" "));
System.out.println("\n------------------------------------------");
System.out.println("spliterator3: ");
spliterator3.forEachRemaining(item->System.out.print(item+" "));
}
  • tryAdvance() 一个一个元素进行遍历
  • forEachRemaining() 顺序地分块遍历
  • trySplit()进行分区形成另外的 Spliterator,使用在并行操作中,分出来的是前面一半,就是不断把前面一部分分出来

结果如下:

tryAdvance:
1 2
-------------------------------------------
forEachRemaining:
3 4 5 6 7 8 9 10
------------------------------------------
spliterator1:
8 9 10
------------------------------------------
spliterator2:
1 2 3 4 5
------------------------------------------
spliterator3:
6 7

还有一些其他的用法在这里就不列举了,主要是trySplit()之后,可以用于多线程遍历。理想的时候,可以平均分成两半,有利于并行计算,但是不是一定平分的。

3.2.2 SpitIterator里面哪些特征常量有什么用呢?

spliterator 可以将其实现特征表示为同一接口中定义的一组常量。也就是我们见到的 ORDERED , DISTINCT , SORTED , SIZED 之类的,这个意思是每一个实现类,都有自己的实现方式,实现方式不同,实现特征也不一样,比如 ArrayList 实现特征是 ORDERED , SIZEDSUBSIZED ,这个我们可以通过

characteristics() and hasCharacteristics() 来判断。例如:

public static void main(String[] args) throws Exception{
List<String> list = new ArrayList<>();
Spliterator<String> s = list.spliterator();
System.out.println(s.characteristics());
if(s.hasCharacteristics(Spliterator.ORDERED)){
System.out.println("ORDERED");
}
if(s.hasCharacteristics(Spliterator.DISTINCT)){
System.out.println("DISTINCT");
}
if(s.hasCharacteristics(Spliterator.SORTED)){
System.out.println("SORTED");
}
if(s.hasCharacteristics(Spliterator.SIZED)){
System.out.println("SIZED");
}
if(s.hasCharacteristics(Spliterator.CONCURRENT)){
System.out.println("CONCURRENT");
}
if(s.hasCharacteristics(Spliterator.IMMUTABLE)){
System.out.println("IMMUTABLE");
}
if(s.hasCharacteristics(Spliterator.NONNULL)){
System.out.println("NONNULL");
}
if(s.hasCharacteristics(Spliterator.SUBSIZED)){
System.out.println("SUBSIZED");
}
}

输出的结果是

16464
ORDERED
SIZED
SUBSIZED

输出结果中的16464和其他的怎么挂钩的呢?其实我们发现上面的 hasCharacteristics() 方法中,实现是 return (characteristics() & characteristics) == characteristics; ,不难看出,这些状态是根据与运算来计算出来的。上面的结果也表明 ArrayListORDERED , SIZEDSUBSIZED 这几个特征。

如果是 HashSet 则特征是 DISTINCTSIZED

四、 iterator在集合中的实现例子

iterator 只是一个接口,相当于一个规范,所有的子类或者继承类实现的时候理论上应该遵守,但是不一样的继承类/子类会有不一样的实现。

4.1 iterator在ArrayList的实现

iterator 只是一个接口,一个规范,虽然里面有个别方法有默认实现,但是最重要也最丰富的的,是它在子类中的实现与拓展,现在来看在 ArrayList 中的实现。 ArrayList 并没有直接去实现 iterator 接口,而是通过内部类的方式来操作,内部类为 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;
Itr() {}
// 是否有下一个元素
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();
}
}

从上面的源码可以看到,很多关于被修改的检查,集合会追踪修改(增删改)的次数(modCount 又称版本号),每一个迭代器会单独立维护一个计数器,在每次操作(增删改),检查版本号是否发生改变,如果改变,就会抛出ConcurrentModificationException() 异常,这是一种安全保护机制。

安全检查,快速失败机制实现主要和变量 modCountexpectedModCount ,以及一个 checkForComodification() 方法有关,也就是 expectedModCount 是内部类的修改次数,从字面意思看是指理论上期待的修改次数, modCount 是外部类的修改次数,创建的时候,会将 modCount 赋值给 expectedModCount ,两者保持一致,如果在迭代的过程中,外部类的 modCount 对不上 expectedModCount ,n那么就会抛出 ConcurrentModificationException 异常。

4.2 iterator在HashMap的实现

首先, HashMap 里面定义了一个 HashIterator ,为什么这样做呢?因为 HashMap 存储结构的特殊性,里面有Entry<key,value>,所以遍历就有三种情况,一个是Key,一个是Value,另一个就是Entry,这三个的迭代遍历都有相似性,所以这里根据抽象原则,定义了一个Hash迭代器。

abstract class HashIterator {
// 下一个节点
Node<K,V> next;
// 当前节点
Node<K,V> current;     // current entry
// 期望修改次数
int expectedModCount;  // for fast-fail
// 索引
int index;             // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) {
// 指向第一个不为空的元素
do {} while (index < t.length && (next = t[index++]) == null);
}
}
// 是否有下一个节点
public final boolean hasNext() {
return next != null;
}
// 获取下一个节点
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
// 移除
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}

之后分别定义 KeyIterator , ValueIterator , EntryIterator ,继承于 HashIterator

// 遍历key
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
// 遍历value
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
//遍历entry
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}

五、总结

以上的种种,关于 Iterator ,其实就是一个迭代器,可简单地理解为遍历使用,主要功能是指向一个节点,向前或者向后移动,如果数据结构复杂就需要多个迭代器,比如 HashMap ,可以避免多个迭代器之间相互影响。每一个迭代器都会有

expectedModCount 和modCount,就是校验这个迭代过程中是否被修改,如果修改了,则会抛出异常。

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

微信扫一扫,分享到朋友圈

java集合【2】—— iterator接口详解

中国电信举办2020天翼智能生态博览会 暨第十二届天翼智能生态产业高峰论坛

上一篇

Java如何正确比较浮点数

下一篇

你也可能喜欢

java集合【2】—— iterator接口详解

长按储存图像,分享给朋友