对于迭代器模式，相信大家都不是很陌生，在HashMap中也很好的实现了迭代器模式。同时，HashMap还有一个更具特色的Spliterator。本文对着两者的源码进行分析。
1.Iterator
HashMap中全部的迭代器都继承了抽象类HashIterator.
1.1 HashIterator
HashIterator是HashMap种所有迭代器的基类。通过抽象类的方式实现了大多数方法，如hashnext、nextNode、remove等。但是需要注意的是，HashIterator并没用实现Iterator接口。而是各自的迭代器在各自实现这个接口。这样一来通过抽象类的方式将公共的功能呢进行了提取。这也是我们在写代码的过程中值得借鉴的地方。
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
//空构造方法
HashIterator() {
//modcout的次数
expectedModCount = modCount;
Node<K,V>[] t = table;
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();
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;
}
}
1.2 Iterator实现类
我们再来看看Interator的实现类：
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(); }
}
可以看到这样一来代码相当简洁。此时对于key、value和entry,之后具体迭代的时候iterator方法不一样。而在调用next的时候Node为TreeNode的父类，在此也可以通用。
另外由于抽象类中增加了forEach方法，那么可以配合lambda表达式使用。
System.out.println(map.keySet().iterator().next());
map.entrySet().forEach(e -> {
System.out.println(e);
});
2.Spliterator
Spliterator是java1.8新增的接口，即为splitable iterator的意思，接口是java为了并行遍历数据源中的元素而设计的。与iterator相比，一个是顺序遍历，一个是将数据拆分为若干部分之后进行并行遍历。以配合Stream的并行流。
Spliterator的一个特点是每次将元素拆分出去一半。对于HashMap，由于hashMap底层是链表，如果要完全精确到元素，势必会造成算法的复杂和性能的低下。因此，Spliterator在HashMap的实现过程中，直接是按bucket进行处理，这样会导致每次拆分的数据并不均匀。HashMap中实际上是按照bucket的数量平均拆分，只是可能每个bucket上面Node的数量可能不一致，另外有的bucket可能为空。我们来通过源码查看这个过程。
2.1 Spliterator的使用
我们以keySpliterator为例子进行验证。
private static void testMap() {
Map<Integer,Integer> map = new HashMap<>();
IntStream.range(0,20).forEach(i -> map.put(i,i));
System.out.println(map.size());
Spliterator<Integer> s1 = map.keySet().spliterator();
Spliterator<Integer> s2 = s1.trySplit();
s1.forEachRemaining(i -> System.out.println("s1:"+i));
System.out.println("===============");
s2.forEachRemaining(i -> System.out.println("s2:"+i));
System.out.println("===============");
}
上述代码执行结果如下：
20
s1:16
s1:17
s1:18
s1:19
===============
s2:0
s2:1
s2:2
s2:3
s2:4
s2:5
s2:6
s2:7
s2:8
s2:9
s2:10
s2:11
s2:12
s2:13
s2:14
s2:15
===============
我们可以看到，在KeySpliterator过程中，将KeySet分为了两部分，其中一部分有16个值，另外一部分为4个。前面说过Spliterator是按bucket进行区分，当有20个元素的时候，bucket的数量为32，那么Spliterator实际上一次分除来的是16个bucket，但是由于hashMap中数据分布的原因，这样就造成了上述情况。
2.2 HashMapSpliterator
HashMapSpliterator是一个基类，keySpliterator和ValueSpiterator、EntrySpliterator都继承了这个类，不过这里有一点我还不太明白的就是，与HashIterator相比，为什么HashIterator是abstrat的抽象类，HashIterator里面也没有定义抽象方法。
2.2.1 成员变量
//需要拆分的hashMap
final HashMap<K,V> map;
//当前节点
Node<K,V> current; // current node
//bucket的index
int index; // current index, modified on advance/split
//计算出的fence
int fence; // one past last index
//
int est; // size estimate
//期望的modCount
int expectedModCount; // for comodification checks
2.2.2 getFence
这是一个初始化方法，在每次调用Spliterator的时候，都会调用这个方法。
final int getFence() { // initialize fence and size on first use
int hi;
//如果完成了初始化，则fence不为-1 只有new的时候传入的fence为-1
if ((hi = fence) < 0) {
//下面的值都是在new中传入赋值
HashMap<K,V> m = map;
est = m.size;
expectedModCount = m.modCount;
Node<K,V>[] tab = m.table;
hi = fence = (tab == null) ? 0 : tab.length;
}
return hi;
}
2.2.3 estimateSize
这个方法的目的是再次调用初始化方法并返回est的结果，确保初始化方法被调用。
public final long estimateSize() {
getFence(); // force init
return (long) est;
}
2.2.4 构造函数
HashMapSpliterator(HashMap<K,V> m, int origin,
int fence, int est,
int expectedModCount) {
this.map = m;
this.index = origin;
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
}
通过构造函数完成了赋值，实际上各个子类都是调用的super的方法，就是这个方法。另外我们可以看看再KeySet中的调用：
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
其他构造函数也类似，都是在各自对应的Set的内部类中持有。
此时默认传入的index为0，fence为-1，est为0，expectModCount为0。
2.3 KeySpliterator
我们来看看KeySpliterator的源码：
2.3.1 类结构及构造函数
static final class KeySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<K> {
KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
}
可以看到这里继承了HashMapSpliterator并实现了Spliterator接口，这是一个非常值得借鉴的地方，可以消除很多冗余代码。
构造函数中直接调用了super方法。
2.3.2 trySplit
这个方法主要是来对Spliterator进行分割。如果Spliterator可以被分割，那么会返回一个新的Spliterator，在传统的情况下，比如list，如果为偶数，则拆分一半，如果为奇数，则会少一个。反正是基本做了对等的拆分。也就是我们在大数据中常用的分治法。
那么对于HashMap，实际上bucket是2的幂，那么直接位移就能实现，我们来看源码；
public KeySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
通过getFence方法的调用，完成初始化赋值，如果已经被赋值过了，那么返回est的值，我们在前面看过构造函数中第一次传入的est为0，hi的值为tab的size，那么回到前面部分的测试代码中，这里est第一次值为tab的size，而lo初始化为index=0，因此mid=size>>>1，我们上面的例子，size为32，那么第一次得到的mid为16。所以每次拆分的都是16个bucket。
之后再new了一个新的keySpliterator。我们可以通过debug观察这个过程：
执行到new的时候：
下一次再进行拆分的时候，hi就变成了16而index则记录了索引，这样配合找到下一次需要拆分的结果。
2.3.3 forEachRemaining
对Spliterator执行遍历：
public void forEachRemaining(Consumer<? super K> action) {
int i, hi, mc;
//如果没有元素，则抛出异常
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
Node<K,V>[] tab = m.table;
//如果没有初始化则返回正确的长度
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
//常规的逻辑都在else部分
mc = expectedModCount;
//如果table不为空切length>hi,则开始遍历
if (tab != null && tab.length >= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Node<K,V> p = current;
current = null;
//遍历hashMap
do {
//如果p为空则移动到下一个bucket
if (p == null)
p = tab[i++];
else {
//遍历链表 调用accept
action.accept(p.key);
p = p.next;
}
//注意，通过hi进行控制
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
通过这个代码我们可以看出，实际上，拆分的方法主要通过index和hi进行控制，index为下标，hi为上表，将index和hi之间的部分遍历出来，这就是forEarch函数的主要工作。
由于Hashmap结构的复杂性，并没有采用直接循环tryAdvance来实现，而是自行实现了遍历方法。
2.3.4 tryAdvance
对单个元素进行遍历，前进一次。
public boolean tryAdvance(Consumer<? super K> action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<K,V>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
//此处一定会取到一个元素，防止由于index<hi的时候取值为null
if (current == null)
current = tab[index++];
else {
K k = current.key;
current = current.next;
action.accept(k);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
这个方法需要注意的就是，由于Hashmap的特殊结构，可能某个bucket没有Node，那么这个算法会保证只要Hashmap中有元素，那么一定会 取出一个。此时current指向了这个取出的node。后续如果继续执行，则由于current不为空，则直接链表遍历。
这个算法的设计也是非常巧妙的。
2.3.4 characteristics
characteristics用于表示实现类的特征，这样再操作的时候就会根据这个特征而影响之前的tryAdvance等方法。但是并不能自行指定这个值。
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
返回值是65，Spliterator.SIZED 与Spliterator.DISTINCT之和。
常用的返回值解释：
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;//表示没有null元素
public static final int IMMUTABLE = 0x00000400;//表示元素不可变
public static final int CONCURRENT = 0x00001000;//表示支持多线程可并发操作
public static final int SUBSIZED = 0x00004000;//表示子Spliterator具有sized属性
这个值的特性由这个容器的实现者根据容器的特性来定义。而不是我们再使用过程中可以来设置的。
3.总结
以上即使对Hashmap中的Interator和Spliterator的说明。是对于前面两部分关于HashMap源码的补充。其中代码的设计模式通过抽象类来消除冗余代码。另外，Spliterator是java8中配合Stream的并行流而引入的接口。我们需要掌握这个接口的使用场景和作用。
