5.1.2 Iterator迭代器

1、Iterator

• 所谓迭代器：就是用于挨个访问集合元素的工具/对象

方法：

1. boolean hasNext():判断当前遍历集合后面是否还有元素可以迭代
2. Object next():取出当前元素，并往后移→noSuchelementException
3. void remove():删除刚刚迭代的对象

while(iterator.hasNext()){String s = (String) iterator.next();if(s.contain("a))iterator.remove();
}

Collection集合：Iterator iterator()方法

• 返回当前遍历集合对象的一个迭代器对象，Iterator是一个接口，即返回Iterator接口的一个实现类对象，具体是哪个实现类对象，需要看集合类型。eg：Arrayist集合→返回ArrayList类中的Itr内部类，实现Iterator接口。

ArrayList arr = new ArrayList();
Iterator iterator = arr.iterator();
while(iterator.hasNext){System.out.println(iterator.next());
}

2、Iterator与Iterable

【java.lang.Iterable接口】：

• 实现Iterable接口允许对象使用”foreach“语句进行遍历，其中数组和集合类都默认实现了Iterable接口（1.5增加）。
• 内含的抽象方法：Iterator iterator()：即实现Iterable接口本质上就是实现Iterator接口，Iterable需要依赖于Iterator。

【java.util.Iterator接口】

3、Iterator原理

• 删除集合元素：iterator.remove()、Collection里的removeIf()、remove(o)

//jdk1.8以后removeIf()
coll.removeIf(new Predicate(){@Overridepublic bollean test(Object o) {return (String(o)).contains("o");}
});

• coll.remove(s)：并发修改异常ConcurrentModifacationException

//2、Iterator迭代时remove()方法：
Collection coll = new ArrayList();
coll.add("hihi");
coll.add("hello");
coll.add("world");
coll.add("zhang");
coll.add("san");Iterator iterator = coll.iterator();
while (iterator.hasNext()){String s = (String) iterator.next();if(s.contains("o")){iterator.remove();//coll.remove(s);//.ConcurrentModificationException}
}
System.out.println(coll);

• 出现漏删情况

//在foreach循环时删除
for (Object o : coll) {if(((String) o).contains("a")){coll.remove(o);//ConcurrentModificationException}
}
System.out.println(coll);

【Iterator原理】

Iterator对象迭代元素的过程：

1. 调用Iterator的next()之前，迭代器指向第一个元素，当第一次调用迭代器的next方法时，返回第一个元素，迭代器的索引向后移动一位，指向第二个元素；
2. 再次调用next方法，返回第二个元素，迭代器的索引再向后移动一位，指向第三个元素；
3. 依此类推，直到hasNext方法返回false，即全部迭代完成，结束对元素的遍历。

【ArrayList里面源码分析】：

public Iterator<E> iterator() {return new Itr();}

创建了一个Iterator迭代器对象，返回ArrayList类中的Itr内部类，Itr内部类实现了Iterator接口。

• modCount：用于记录集合结构被修改的次数。
• 对集合进行增添、删除→modCount++
• 在用Iterator迭代器遍历集合时，创建集合迭代器的对象，会使用变量exceptionModCount记录当前集合的modCount。当进入next()方法时，会先判断exceptionModCount != modCount，如果不等于（集合结构发生了改变，modCount++）将抛出ConcurrentModificationException异常；如果相等则进行下一次迭代

private class Itr implements Iterator<E> {int cursor;       // 游标，指定当前集合索引int lastRet = -1; // 返回上一次遍历元素的索引，如果不存在为-1int expectedModCount = modCount;//迭代器创建时的modCount值Itr() {}

在ArrayList里，发现modCount变量定义在ArrayList的父类AbstractList里。在涉及add新增、remove删除、fastRemove、clear等会改变集合结构的操作，都会通过modCount++形式，增加列表在结构上被修改的次数。

//AbstractList.java
protected transient int modCount = 0;

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

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

• 如果当前索引不等于集合大小，说明还有元素没有遍历完，返回ture将进行下一次迭代。

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

• 检查exceptionModCount != modCount；如果相等，进入下一次迭代，不等，抛出异常。

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

康康remove(o)

public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
}

private void fastRemove(int index) {modCount++;......}

【总结】：Iterator如何实现fail-fast机制的？

fail-fast产生的原因：在于程序在遍历过程中，某个线程对该 collection 在结构上对其做了修改，此时迭代器抛出 ConcurrentModificationException 异常信息，导致遍历失败，从而产生 fail-fast。由此可以看出fail-fast不允许在遍历的过程中对容器中的数据进行修改。

但是该异常不会始终指出对象已经由不同线程并发修改，如果单线程违反了规则，同样也有可能会抛出改异常。不能保证一定会出现该错误，但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常，所以因此，为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法，正确做法是：ConcurrentModificationException 应该仅用于检测 bug。