JDK容器学习之HashMap (三) : 迭代器实现
HashMap 迭代器实现方式
java的容器类，实现
Collection接口的都会实现迭代器方式，Map则有点特殊，它不实现Collection接口，它的迭代使用方式则主要借助Collection来实现
1. Map的遍历方式
对于List,Set，我们可以直接用 foreach 来实现遍历，而Map则不能直接这么用，通常Map的遍历方式有三种
- Entry的遍历
for(Map.Entry entry: map.entrySet()) {
// xxx
}
- Key的遍历
for(Object key : map.keySet()) {
// xxx
}
- Value的遍历
for(Object value: map.values()) {
// xxxx
}
上面遍历主要依赖的三个方法，前两个返回的都是Set，那么就有下面几个问题
-
map.entrySet返回的Entry集合元素个数和Map的size是否相同
- 简单来讲就是假设有两个Entry的key的hash值相同
- 那么这两个Entry都会放在这个Set集合中么？
- 或者说等同HashMap的数组链表格式，Set集合中放的是链表头？
-
map.keySet对于key的hashcode相同的场景会出现什么情况 -
map.valuesMap中value没有校验，因此value集合容量应可以小于map.size()
2. 实现方式
entrySet
方法的实现如下：
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
可以看到返回的是内部成员变量 entrySet，问题就集中在这个成员变量是如何维护的
按正常的理解是，在添加删除元素的时候，同步维护entrySet的值算是最简单的方法了，然而前面博文《JDK容器学习之HashMap (二) ： 读写逻辑详解》中，并没有看到有维护这一段的逻辑
扫了一遍代码，愣是没有发现在什么地方维护有显示的向Set中添加or移除元素了
唯一的可能性就是下面这个初始化了，这一行代码到底做了什么呢？
entrySet = new EntrySet();
这里就只是创建了一个对象，接下来则需要研究下这个对象是个什么鬼了
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
// xxx
}
public final boolean remove(Object o) {
// xxx
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
// xxx
}
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
首先 EntrySet 是一个 Set 对象，而Set的遍历采用迭代器模式，迭代器模式主要依赖的 iterator() 方法的实现
返回继承 hashIterator 的 EntryIterator 对象，其中的核心的next()方法就是调用的 hashIterator.nextNode()
到这里，就可以大胆的得出结论，遍历 entrySet 其实就是在依次调用 hashIterator.nextNode() 方法，这个Set本身是不做元素的添加移除操作的，它就是直接封装了的HashMap内部的HashIterator，对外提供服务
HashIterator hash迭代器
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() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) {
// 遍历数组直到找到第一个非空的Node节点
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) {
// 若出现hash碰撞，且当前节点的链尾非空，则next指向链表下一个节点
// 没有hash碰撞，or链表尾为空，即Node节点内部的next指向空
// 继续扫描table数组，找到下一个有效的Node节点，并赋值给next
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;
}
}
遍历的逻辑如下：
-
初始化：扫描table数组，找到第一个有效的Node对象并赋值给next对象
-
依次遍历：
-
将next对象赋值给临时变量e
- 因为最终返回的就是当前的next对象
- 为了保证遍历的可持续性，需要在返回之前，重新获取到下一个next对象
-
重新设置next对象
- 若e的next对象存在（即hash碰撞，且链表的下一个节点存在），则next指向下一个节点
- 若e的next对象为空
- 若e没有后缀（即这个不存在hash碰撞，链表结构只有这个链头）
- 上面两种情况，则继续遍历table数组，找到下一个有效的Node对象
-
所以，针对数组+链表的结构图，扫描的流程应该是
https://static.oschina.net/uploads/img/201709/22221611_Fdo5.jpg
