完整代码:代码
前言
这篇文章主要分析
HashMap1.8中是如何遍历元素的,先会介绍普通遍历Iterator然后再介绍Spliterator.
Iterator接口
public interface Iterator<E> {
//是否有下一个元素
boolean hasNext();
//取出元素
E next();
//删除元素 至于删除什么样的元素需要根据子类的实现而定
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 1.8加入的新方法 其实就是遍历
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
抽象类HashIterator
HashIterator虽然没有继承Iterator接口,但是它实现了除了next方法外的所有抽象方法,相当于是一个辅助类.
另外注意一下
nextNode方法,它其实是整个函数的核心函数,它完成了如何遍历整个table的功能,方法是一个槽一个槽的遍历,指的是不为null的槽.
abstract class HashIterator {
Node<K,V> next; // 下一个要返回的entry
Node<K,V> current; // 当前的 entry
int expectedModCount; // 期望的修改次数
int index; // 当前的槽index
HashIterator() { //构造函数
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // 初始化next,寻找第一个不为null的槽
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; // 把下一个元素赋值给e,在后面e会赋值给current
if (modCount != expectedModCount) //如果修改次数没有变化
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
/**
* 1. if条件里面的意思是检查当前槽是否遍历完,没有遍历完就把链表下一个元素给next
* 请注意不论当前槽是链表(节点类型Node)还是红黑树结构(TreeNode)
* 都保存了链表结构(Node或者TreeNode) 节点类型都是Node或者Node的子类TreeNode
* 所以可以返回Node
* 2. do{}while里面是去找下一个槽并且存在next中
*/
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
/**
* 删除操作,
* 1. 请注意删除的是current元素,而不是next元素
* 2. 调用removeNode删除成功会使得modCount增加1,
* 此时会与expectedModCount不相等,但是又把修改后的modCount赋值给expectedModCount
*/
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;
}
}
接下来看看三个实现
Iterator的类:KeyIterator,ValueIterator,EntryIterator
// 继承HashIterator的方法并且实现next()从而实现了Iterator的所有方法
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
// 继承HashIterator的方法并且实现next()从而实现了Iterator的所有方法
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
// 继承HashIterator的方法并且实现next()从而实现了Iterator的所有方法
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
明白了这些之后,就要进入下面的正题了
entrySet()
entrySet()方法
transient Set<Map.Entry<K, V>> entrySet;
@Override
public Set<Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
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() {
System.out.println("creating Iterator in EntrySet...");
return new EntryIterator();
}
//判断是否存在对象o
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
//删除对象o
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
//分离式迭代器
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) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
看到这里,直接看个小例子
小例子
import java.util.Iterator;
import java.util.Map;
public class TestHashMapIteration {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
String str = "ABCDEFG";
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i) + "", i);
}
System.out.println("modCount->" + map.modCount);
// foreach是调用iterator()方法返回迭代器 用迭代器来遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.print("[" + entry.getKey() + "->" + entry.getValue() + "] ");
}
System.out.println("\nmodCount->" + map.modCount);
System.out.println("-----------------------------------");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<String, Integer> entry = (Map.Entry<String, Integer>)iter.next();
System.out.print("[" + entry.getKey() + "->" + entry.getValue() + "] ");
//map.remove(entry.getKey()); // 会产生java.util.ConcurrentModificationException
//map.put("X", -1); //会产生java.util.ConcurrentModificationException
//map.put("A", 2); //不会有影响,因为是更新节点,不会modCount++
iter.remove(); //没有影响
}
System.out.println("\nmodCount->" + map.modCount);
System.out.println("size:" + map.size);
}
}
结果:可以看到
foreach其实是调用迭代器实现的,还有一点是在迭代器中使用HashMap的成员方法remove(Object key)会使得modCount与迭代器中的expectedCount不相同,会抛出java.util.ConcurrentModificationException异常.但是使用迭代器自身的remove就不会有影响,至于为什么?在上面的代码中有提到.
modCount->7
creating Iterator in EntrySet...
[A->0] [B->1] [C->2] [D->3] [E->4] [F->5] [G->6]
modCount->7
-----------------------------------
creating Iterator in EntrySet...
[A->0] [B->1] [C->2] [D->3] [E->4] [F->5] [G->6]
modCount->14
size:0
相同原理的
KeySet就不多解释了,keySet变量是AbstractMap中继承的,
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
有一点大家可以思考下,即使类
HashMap中没有实现keySet()方法,只需要实现entrySet()方法后,下面的代码也可以运行成功.原因大家可以自己思考一下？
for (String k : map.keySet()) {
System.out.print("[" + k + "->" + map.get(k) + "] ");
}
答案在
AbstractMap中,看一下源码就知道了.
Spliterator
对
Spliterator不了解的人可以参考用例子解析Spliterator,
static class HashMapSpliterator<K,V> {
//存数据的map
final HashMap<K,V> map;
// 当前节点
Node<K,V> current; // current node
// 当前槽
int index; // current index, modified on advance/split
//最后一个槽 有效槽[index, fence-1]
int fence; // one past last index
//预计节点的数量 估计值 不是正确的值没有去统计
int est; // size estimate
int expectedModCount; // for comodification checks
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;
}
//初始化
final int getFence() { // initialize fence and size on first use
int hi;
if ((hi = fence) < 0) {
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;
}
public final long estimateSize() {
getFence(); // force init
return (long) est;
}
}
static final class EntrySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<Map.Entry<K,V>> {
//构造函数
EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
//拆分 二分拆分并且est只是单纯的除以2
public EntrySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
//遍历
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> 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
mc = expectedModCount;
if (tab != null && tab.length >= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Node<K,V> p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p);
p = p.next;
}
} while (p != null || i < hi);
//在遍历期间modCount不能发生变化 在增加一个节点和删除一个节点的时候都会造成modCount发生变化
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> 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) {
if (current == null)
current = tab[index++];
else {
Node<K,V> e = current;
current = current.next;
action.accept(e);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
//我自己加的函数 方便测试
public String toString() {
return "[index=" + super.index + ", fence=" + getFence() + ", est=" + est + "]";
}
}
调用 在
EntrySet类中
//分离式迭代器
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
测试:
public class TestHashMapIteration {
public static void main(String[] args) {
test_spliterator();
}
public static void test_spliterator() {
HashMap<String, Integer> map = new HashMap<>();
String str = "ABCDEFG";
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i) + "", i);
}
System.out.println("capacity:" + map.table.length);
Spliterator<Map.Entry<String,Integer>> ster_1 = map.entrySet().spliterator();
System.out.println("ster_1:" + ster_1);
Spliterator<Map.Entry<String,Integer>> ster_2 = ster_1.trySplit();
System.out.println("----------split------------");
System.out.println("ster_1:" + ster_1);
System.out.println("ster_2:" + ster_2);
Spliterator<Map.Entry<String,Integer>> ster_3 = ster_1.trySplit();
Spliterator<Map.Entry<String,Integer>> ster_4 = ster_2.trySplit();
System.out.println("----------split------------");
System.out.println("ster_1:" + ster_1);
System.out.println("ster_2:" + ster_2);
System.out.println("ster_3:" + ster_3);
System.out.println("ster_4:" + ster_4);
System.out.println("------ster1-------");
printSpliterator(map, ster_1);
System.out.println("------ster2-------");
printSpliterator(map, ster_2);
System.out.println("------ster3-------");
printSpliterator(map, ster_3);
System.out.println("------ster4-------");
printSpliterator(map, ster_4);
}
private static void printSpliterator(HashMap<String, Integer> map, Spliterator<Map.Entry<String,Integer>> ster) {
ster.forEachRemaining(new Consumer<Map.Entry<String,Integer>>(){
@Override
public void accept(Entry<String, Integer> t) {
System.out.println(t.getKey() + "->" + t.getValue());
//map.remove("A"); //java.util.ConcurrentModificationException
//map.put("A", -1); //更新节点 不影响
}
});
}
}
结果:
capacity:16
ster_1:[index=0, fence=16, est=7]
----------split------------
ster_1:[index=8, fence=16, est=3]
ster_2:[index=0, fence=8, est=3]
----------split------------
ster_1:[index=12, fence=16, est=1]
ster_2:[index=4, fence=8, est=1]
ster_3:[index=8, fence=12, est=1]
ster_4:[index=0, fence=4, est=1]
------ster1-------
------ster2-------
[D->3] [E->4] [F->5] [G->6]
------ster3-------
------ster4-------
[A->0] [B->1] [C->2]
KeySpliterator和ValueSpliterator与EntrySpliterator类似
1.HashMap1.8 源码解析(1)--插入元素
2.HashMap1.8 源码解析(2)--删除元素
3.HashMap1.8 源码解析(3)--TreeNode(红黑树)包括每一个方法
4.HashMap1.8 源码解析(4)--遍历元素
