前言
Java 集合框架
Iterator 是 Java 数据结构框架的起始，它是一个顶级接口，梦开始的地方。
让这个迭代器作为顶级接口可能是出于功能的考虑，不管怎样的数据结构，都需要遍历不是。那么就需要提供一种可以用来遍历的方式，让开发者使用也让 JVM 认识。
一、前世今生
JDK 1.0 的 Enumeration，因名字太长和方法数量有点少不太好扩展被废弃。
JDK 1.2 推出 Iterator 替代。
Iterator JDK 1.8
public interface Iterator<E> {
// 是否包含下一元素
boolean hasNext();
// 下一元素
E next();
// 移除元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 遍历剩余元素，游标之后的
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
用来遍历元素，且遍历的过程中可以删除。
-
hasNext()是否含有下一个元素； -
next()获取下一元素； -
remove()移除某元素； -
forEachRemaining()遍历当前迭代器尚未遍历的元素。
二、一致性
遍历过程中可以修改原数据的称为弱一致性，不可修改的为强一致性。下面举两个例子：
1. 强一致性
数据修改过程中会记录操作次数 modCount，遍历过程发现该值与期望的不一致，会抛出 ConcurrentModificationException 异常。
常见的有 HashMap、ArrayList。
HashMap.HashIterator # nextNode
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;
}
ArrayList.Itr # next()
public E next() {
if (modCount != expectedModCount) // 此处表现
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
这种强一致性的迭代器官称为 fail-fast 迭代器。
2. 弱一致性
弱一致性相当于创建时做一个数据的拷贝，因为操作的不是原数据，所以不会出现问题也没用抛异常。
但是弱一致性带来一些问题：
- 空间浪费，因为是复制嘛；
- 数据不一致，如果遍历过程中原数据进行了修改，操作的结果可能与想要的发生差异。
弱一致性的有 CopyOnWriteArrayList、ConcurrentHashMap。
CopyOnWriteArrayList.COWIterator # next()
public E next() {
if (! hasNext())
throw new NoSuchElementException();
// snapshot 是创建时用当时数据赋值的，相当于拷贝副本
return (E) snapshot[cursor++];
}
三、迭代器种类
1. 线性迭代器
- 持有一个游标
cursor用来记录当前遍历到的位置； - 可以正序、倒序遍历；
- 可以查找前后元素；
- 可以调用
add() set()添加和修改数据，两者都是往当前迭代器遍历下标处新增和修改。
比如 ArrayList 的 Itr 就是一种线性迭代器。
private class Itr implements Iterator<E> {
// Android 添加 limit 参数，也就是当前数据长度作为临界值
protected int limit = ArrayList.this.size;
int cursor; // 游标
int lastRet = -1; // 最后一个返回的元素，默认 -1
int expectedModCount = modCount;
public boolean hasNext() {
return cursor < limit;
}
// 下一元素
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
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();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
limit--;
} 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;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}
2. 链式迭代器 HashIterator
- 持有一个遍历结点、当前遍历下标；
HashMap 的迭代器就是一种实现 HashIterator。
abstract class HashIterator {
Node<K,V> next; // 下一个要返回的结点
Node<K,V> current; // 当前结点
int expectedModCount; // for fast-fail 强一致性
int index; // current slot 当前下标
HashIterator() {
expectedModCount = modCount; // 创建时赋值
Node<K,V>[] t = table; // table 是 HashMap 的数据
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
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();
// 遍历查找，直到下面结点为 null 或 表为空
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;
}
}
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
四、总结和其它
Iterable 接口
如果想让某个 Object 可以使用 "for-each loop" 也就是增强 for 循环，需要实现 Iterable 接口。
public interface Iterable<T> {
/**
* Returns an iterator over elements of type {@code T}.
* @return an Iterator.
*/
Iterator<T> iterator();
}
也就是说，想要使用增强 for 循环，必须实现该接口并提供迭代器。如果使用没有实现该接口的类进行循环，编译器会报错。
实例
List<Integer> list = new ArrayList<>();
list.add(1);
for (Integer i : list) {
System.out.print(i);
}
ArrayList 最终继承了 Iterable 所以可以遍历，那么这个增强 for 循环反编译之后：
Integer i;
for(Iterator iterator = list.iterator(); iterator.hasNext(); System.out.println(i)){
i = (Integer)iterator.next();
}
可以看到其实是使用迭代器进行遍历的操作，不断给变量 i 赋值并打印。
注意
因为 Java 有 fail-fast 机制，使用增强 for 循环时要考虑所遍历对象的一致性。使用某些强一致性的结构如 ArrayList，如果要操作数据应使用迭代器：
List<Student> students = new ArrayList<>();
...
Iterator<Student> stuIter = students.iterator();
while (stuIter.hasNext()) {
Student student = stuIter.next();
if (student.getId() == 2) {
// 这里要使用Iterator的remove方法移除当前对象
// 如果使用List的remove方法，则会出现ConcurrentModificationException
stuIter.remove();
}
}
总结
- 实现 Iterable 以提供迭代器，实现循环功能；
- 迭代器可以用来遍历、指定位置插入、移除数据；
- 使用可迭代数据结构，要注意其一致性；
- 无论是线性还是链式迭代器，主要是依靠内部维护的游标（下标）来标记当前遍历位置。
网友评论