文章目录
- 一、`iterator`接口介绍
- 二、为什么需要iterator接口
- 三、iterator接口相关接口
- 3.2.1 SpitIterator源码方法解析
- 3.2.2 SpitIterator里面哪些特征常量有什么用呢？
- 3.1 ListIterator
- 3.2 SpitIterator
- 四、 iterator在集合中的实现例子
- 4.1 iterator在ArrayList的实现
- 4.2 iterator在HashMap的实现
- 五、总结
一、
iterator
接口介绍
iterator
接口,也是集合大家庭中的一员。和其他的
Map
和
Collection
接口不同，
iterator
主要是为了方便遍历集合中的所有元素，用于迭代访问集合中的元素，相当于定义了遍历元素的规范，而另外的
Map
Collection
接口主要是定义了存储元素的规范。
还记得么？之前说的
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
的对象。值得注意的是，
iterator
的
remove()
方法，是迭代过程中唯一安全的修改集合的方法，为何这样说？
如果使用for循环索引的方式遍历，删除掉一个元素之后，集合的元素个数已经变化，很容易出错。例如
for(int i=0;i<collection.size();i++){
if(i==2){
collection.remove(i);
}
} 而
iterator
remove()
方法则不会出错，因为通过调用
hasNext()
next()
方法，对指针控制已经处理得比较完善。
首先，我们知道
iterator
接口是为了定义遍历集合的规范，也是一种抽象，把在不同集合的遍历方式抽象出来，这样遍历的时候，就不需要知道不同集合的内部结构。
为什么需要抽象？
假设没有
iterator
接口,我们知道，遍历的时候只能通过索引，比如
for(int i=0;i<array.size();i++){
T item = array[i];} 这样一来，耦合程度比较高，如果使用的数据结构变了，就要换一种写法，不利于维护已有的代码。如果没有
iterator
,那么客户端需要维护指针，相当于下放了权限，会造成一定程度的混乱。抽象则是把遍历功能抽取出来，交给
iterator
处理，客户端处理集合的时候，交给更“专业”的它，it do it well.
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中的元素修改有可能导致数组越界。
准确地来说，
SpitIterator
Iterator
并没有什么关系，只是两个功能上有类似。
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()之后，可以用于多线程遍历。理想的时候，可以平均分成两半，有利于并行计算，但是不是一定平分的。
spliterator
可以将其实现特征表示为同一接口中定义的一组常量。也就是我们见到的
ORDERED
,
DISTINCT
SORTED
SIZED
之类的，这个意思是每一个实现类，都有自己的实现方式，实现方式不同，实现特征也不一样，比如
ArrayList
实现特征是
ORDERED
SIZED
SUBSIZED
,这个我们可以通过
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");
}
} 输出的结果是
16464ORDERED
SIZED
SUBSIZED 输出结果中的16464和其他的怎么挂钩的呢？其实我们发现上面的
hasCharacteristics()
方法中，实现是
return (characteristics() & characteristics) == characteristics;
，不难看出，这些状态是根据与运算来计算出来的。上面的结果也表明
ArrayList
有
ORDERED
SIZED
SUBSIZED
这几个特征。
如果是
HashSet
则特征是
DISTINCT
SIZED
。
iterator
只是一个接口，相当于一个规范，所有的子类或者继承类实现的时候理论上应该遵守，但是不一样的继承类/子类会有不一样的实现。
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() 异常，这是一种安全保护机制。
安全检查，快速失败机制实现主要和变量
modCount
，
expectedModCount
，以及一个
checkForComodification()
方法有关，也就是
expectedModCount
是内部类的修改次数，从字面意思看是指理论上期待的修改次数，
modCount
是外部类的修改次数，创建的时候，会将
modCount
赋值给
expectedModCount
，两者保持一致，如果在迭代的过程中，外部类的
modCount
对不上
expectedModCount
，n那么就会抛出
ConcurrentModificationException
异常。
首先，
HashMap
里面定义了一个
HashIterator
，为什么这样做呢？因为
HashMap
存储结构的特殊性，里面有Entry
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，就是校验这个迭代过程中是否被修改，如果修改了，则会抛出异常。
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~