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

秦怀杂货店 2020-11-08 23:46:32
java 集合 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,就是校验这个迭代过程中是否被修改,如果修改了,则会抛出异常。

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

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

公众号:秦怀杂货店

版权声明
本文为[秦怀杂货店]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000037765317

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云