Java--Iterator迭代器(集合的遍历)

Dear 丶 2024-04-21 19:08 55阅读 0赞

#### 文章目录 ####

*   *  一.Iterator接口API
     *  二.迭代器的实现原理
     *  三.ListIterator
     *  四.ConcurrentModificationException（使用迭代器报这个错可以来看下原因及解决方案）
     *   *  ?modCount与fail-fast机制

### 一.Iterator接口API ###

?在程序开发中，经常需要遍历集合中的所有元素。针对这种需求，JDK专门提供了一个接口`java.util.Iterator`。`Iterator`接口也是Java集合中的一员，但它与`Collection`、`Map`接口有所不同，`Collection`接口与`Map`接口主要用于存储元素，而`Iterator`主要用于迭代访问（即遍历）`Collection`中的元素，因此`Iterator`\*\*对象也被称为迭代器。

?想要遍历Collection集合，那么就要获取该集合迭代器完成迭代操作，下面介绍一下获取迭代器的方法：

>  *  **`public Iterator iterator()`**: 获取集合对应的迭代器，用来遍历集合中的元素的。
> 
> 下面介绍一下迭代的概念：
> 
>  *  **迭代**：即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续在判断，如果还有就再取出出来。一直把集合中的所有元素全部取出。这种取出方式专业术语称为迭代。
> 
> **Iterator接口的常用方法如下：**
> 
>  *  `public E next()`:返回迭代的下一个元素。
>  *  `public boolean hasNext()`:如果仍有元素可以迭代，则返回 true。
>  *  `public void remove()`:通过迭代器删除元素

?接下来我们通过案例学习如何使用Iterator迭代集合中元素：

public class IteratorDemo {
 
 	public static void main(String[] args) {
 
 // 使用多态方式 创建对象
 Collection<String> coll = new ArrayList<String>();
 
 // 添加元素到集合
 coll.add("串串星人");
 coll.add("吐槽星人");
 coll.add("汪星人");
 //遍历
 //使用迭代器 遍历 每个集合对象都有自己的迭代器
 Iterator<String> it = coll.iterator();
 // 泛型指的是 迭代出 元素的数据类型
 while(it.hasNext()){
 //判断是否有迭代元素
 String s = it.next();//获取迭代出的元素
 System.out.println(s);
 }
 	}
 }

❌ *tips:：在进行集合元素取出时，如果集合中已经没有元素了，还继续使用迭代器的next方法，将会发生java.util.NoSuchElementException没有集合元素的错误。*

--------------------

### 二.迭代器的实现原理 ###

?我们在之前案例已经完成了Iterator遍历集合的整个过程。当遍历集合时，首先通过**调用**集合的**iterator()方法获得迭代器对象**，然后使用**hashNext()方法判断集合中是否存在下一个元素**，如果存在，则调用**next()方法将元素取出**，否则说明已到达了集合末尾，停止遍历元素。

?Iterator迭代器对象在遍历集合时，内部采用指针的方式来跟踪集合中的元素，为了让初学者能更好地理解迭代器的工作原理，接下来通过一个图例来演示Iterator对象迭代元素的过程：

![img][]

?**总结**：在调用Iterator的next方法之前，迭代器的索引位于第一个元素之前，指向第一个元素，当第一次调用迭代器的next方法时，返回第一个元素，然后迭代器的索引会向后移动一位，指向第二个元素，当再次调用next方法时，返回第二个元素，然后迭代器的索引会再向后移动一位，指向第三个元素，依此类推，直到hasNext方法返回false，表示到达了集合的末尾，终止对元素的遍历。

--------------------

### 三.ListIterator ###

⭕️**List 集合额外提供了一个 listIterator() 方法**，该方法返回一个 [ListIterator][] 对象， ListIterator 接口继承了 Iterator 接口，提供了专门操作 List 的方法：

>  *  void add()：通过迭代器添加元素到对应集合
>  *  void set(Object obj)：通过迭代器替换正迭代的元素
>  *  void remove()：通过迭代器删除刚迭代的元素
>  *  boolean hasPrevious()：如果以逆向遍历列表，往前是否还有元素。
>  *  Object previous()：返回列表中的前一个元素。
>  *  int previousIndex()：返回列表中的前一个元素的索引
>  *  boolean hasNext()
>  *  Object next()
>  *  int nextIndex()

?**下面代码示例 ， 这里用法和Iterator一致 ， 不做过多的赘述 ，需要注意ListIterator仅针对List集合才可以使用**

public static void main(String[] args) {
 
 		List<Student> c = new ArrayList<>();
 		c.add(new Student(1,"张三"));
 		c.add(new Student(2,"李四"));
 		c.add(new Student(3,"王五"));
 		c.add(new Student(4,"赵六"));
 		c.add(new Student(5,"钱七"));
 		
 		//从指定位置往前遍历
 		ListIterator<Student> listIterator = c.listIterator(c.size());
 		while(listIterator.hasPrevious()){
 
 			Student previous = listIterator.previous();
 			System.out.println(previous);
 		}
 	}

--------------------

### 四.ConcurrentModificationException（使用迭代器报这个错可以来看下原因及解决方案） ###

#### ?modCount与fail-fast机制 ####

⭕️当使用foreach或Iterator迭代器遍历集合时，同时调用迭代器自身以外的方法修改了集合的结构，例如调用集合的add和remove方法时，就会报ConcurrentModificationException。

public class TestForeach {
 
 public static void main(String[] args) {
 
 Collection<String> list = new ArrayList<>();
 list.add("hello");
 list.add("java");
 list.add("atguigu");
 list.add("world");
 
 Iterator<String> iterator = list.iterator();
 while(iterator.hasNext()){
 
 list.remove(iterator.next());//指的就是这里，遍历时，使用了集合的remove方法
 //iterator.remove(); 使用迭代器的删除方法，删除元素问题就解决了
 }
 }
 }

✍️报错的原因想必到现在你已经知道为什么了 ， 下面的内容会展开说下modCount与fail-fast机制 ， 感兴趣的话可以看下

?如果在Iterator、ListIterator迭代器创建后的任意时间从结构上修改了集合（通过迭代器自身的 remove 或 add 方法之外的任何其他方式），则迭代器将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。

?这样设计是因为，迭代器代表集合中某个元素的位置，内部会存储某些能够代表该位置的信息。当集合发生改变时，该信息的含义可能会发生变化，这时操作迭代器就可能会造成不可预料的事情。因此，果断抛异常阻止，是最好的方法。**这就是Iterator迭代器的快速失败（fail-fast）机制**。

?注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 `ConcurrentModificationException`。因此，编写依赖于此异常的程序的方式是错误的，正确做法是：**迭代器的快速失败行为应该仅用于检测 bug**。例如：

@Test
 	public void test02() {
 
 		ArrayList<String> list = new ArrayList<>();
 		list.add("hello");
 		list.add("java");
 		list.add("atguigu");
 		list.add("world");
 		
 //以下代码没有发生ConcurrentModificationException异常
 		Iterator<String> iterator = list.iterator();
 		while(iterator.hasNext()){
 
 			String str = iterator.next();
 			
 			if("atguigu".equals(str)){
 
 				list.remove(str);
 			}
 		}
 	}

**那么如何实现快速失败（fail-fast）机制的呢？**

>  *  在ArrayList等集合类中都有一个modCount变量。它用来记录集合的结构被修改的次数。
>  *  当我们给集合添加和删除操作时，会导致modCount++。
>  *  然后当我们用Iterator迭代器遍历集合时，创建集合迭代器的对象时，用一个变量记录当前集合的modCount。例如：`int expectedModCount = modCount;`，并且在迭代器每次next()迭代元素时，都要检查 `expectedModCount != modCount`，如果不相等了，那么说明你调用了Iterator迭代器以外的Collection的add,remove等方法，修改了集合的结构，使得modCount++，值变了，就会抛出ConcurrentModificationException。

?下面以AbstractList和ArrayList.Itr迭代器为例进行源码分析：

?AbstractList类中声明了modCount变量：

/**
 * The number of times this list has been structurally modified.
 * Structural modifications are those that change the size of the
 * list, or otherwise perturb it in such a fashion that iterations in
 * progress may yield incorrect results.
 *
 * This field is used by the iterator and list iterator implementation
 * returned by the {@code iterator} and {@code listIterator} methods.
 * If the value of this field changes unexpectedly, the iterator (or list
 * iterator) will throw a {@code ConcurrentModificationException} in
 * response to the {@code next}, {@code remove}, {@code previous},
 * {@code set} or {@code add} operations. This provides
 * fail-fast behavior, rather than non-deterministic behavior in
 * the face of concurrent modification during iteration.
 *
 * Use of this field by subclasses is optional. If a subclass
 * wishes to provide fail-fast iterators (and list iterators), then it
 * merely has to increment this field in its {@code add(int, E)} and
 * {@code remove(int)} methods (and any other methods that it overrides
 * that result in structural modifications to the list). A single call to
 * {@code add(int, E)} or {@code remove(int)} must add no more than
 * one to this field, or the iterators (and list iterators) will throw
 * bogus {@code ConcurrentModificationExceptions}. If an implementation
 * does not wish to provide fail-fast iterators, this field may be
 * ignored.
 */
 protected transient int modCount = 0;

?modCount是这个list被结构性修改的次数。结构性修改是指：改变list的size大小，或者，以其他方式改变他导致正在进行迭代时出现错误的结果。

?这个字段用于迭代器和列表迭代器的实现类中，由迭代器和列表迭代器方法返回。如果这个值被意外改变，这个迭代器将会抛出 ConcurrentModificationException的异常来响应：next,remove,previous,set,add 这些操作。在迭代过程中，他提供了fail-fast行为而不是不确定行为来处理并发修改。

?子类使用这个字段是可选的，如果子类希望提供fail-fast迭代器，它仅仅需要在add(int, E),remove(int)方法（或者它重写的其他任何会结构性修改这个列表的方法）中添加这个字段。调用一次add(int,E)或者remove(int)方法时必须且仅仅给这个字段加1，否则迭代器会抛出伪装的ConcurrentModificationExceptions错误。如果一个实现类不希望提供fail-fast迭代器，则可以忽略这个字段。

Arraylist的Itr迭代器：

private class Itr implements Iterator<E> {
 
 int cursor; 
 int lastRet = -1; 
 int expectedModCount = modCount;//在创建迭代器时，expectedModCount初始化为当前集合的modCount的值
 
 public boolean hasNext() {
 
 return cursor != size;
 }
 
 @SuppressWarnings("unchecked")
 public E next() {
 
 checkForComodification();//校验expectedModCount与modCount是否相等
 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];
 }
 final void checkForComodification() {
 
 if (modCount != expectedModCount)//校验expectedModCount与modCount是否相等
 throw new ConcurrentModificationException();//不相等，抛异常
 }
 }

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/c8dd77b3660e4754a6fba752cf80ca13.png
[ListIterator]: https://so.csdn.net/so/search?q=ListIterator&spm=1001.2101.3001.7020