HashMap 源码解析(二)

上篇文章介绍了hashMap 的基本数据结构和put() get() resize()流程 传送门

现在我们来介绍 hashmap 剩下的一些方法
hashMap 有些情况下会进行遍历操作，hashMap 支持提供了三种遍历方法
1 keySet()
官方注释是@return a set view of the keys contained in this map(返回map的key set)

 public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; }

这个方法反回了一个KeySet类 看看这个KetSet是个什么啥

 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(); } } }

KeySet是hashMap的内部类，没有没有写任何逻辑，如何去遍历这个KeySet的关键在于iterator() 不管是使用迭代器还是使用for加强循环，核心的东西都是这个迭代器
下面继续看KeyIterator.class 是个什么东西

 final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() { return nextNode().key; } }

可以看到 这个迭代器继承于HashIterator ，仅重写了next() 方法，结合HashIterator代码一起分析

abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; } 

首先在迭代器初始化时

 HashIterator() { expectedModCount = modCount; //将hashMap操作次数赋值给expectedModCount, //在其他线程操作该hashMap后 预期值和实际值不同直接抛出异常,类似于cas Node<K,V>[] t = table; //将hashMap的数据集赋值给 t current = next = null; //设置迭代器的当前节点和下一个节点为空 index = 0; //hashMap table 游标设置为0 if (t != null && size > 0) { // advance to first entry 判断是不是空map //获取table数组中第一个不为空的链表头节点 do {} while (index < t.length && (next = t[index++]) == null); } }

ok，现在迭代器初始化完成，迭代器的两大核心方法为hasNext() 判断是否存在下一条数据 和next() 获取下一条数据并将next指向下一条数据
1 hashNext（）,很简单，判断next是不是为空就可以

public final boolean hasNext() { return next != null; }

2 next（）：抽象类HashIterator 没有定义该方法，是因为next() 有返回值，需要子类去自己定义返回值，HashIterator 将公用操作定义为nextNode方法
KeySet的迭代器KeyIterator 定义的方法为

public final K next() { return nextNode().key; }

HashIterator.nextNode（）方法如下,方法很短，但是操作很多

 final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; //获取next if (modCount != expectedModCount) //判断 hashMap是否被其他线程修改过 throw new ConcurrentModificationException(); if (e == null)//判断下一个节点是不是为空 throw new NoSuchElementException(); // 下面的操作比较复杂我们拆成多步操作 /** current = e;// 将current next = current.next; //next赋值为current的下一个节点 t=table; if(next == null&&t != null){//如果next为链表最后一个节点 do {} while (index < t.length && (next = t[index++]) == null); // 数组游标++ 一直找到数组的下一个有数据的节点的头节点，假如是最后一个节点则跳出循环，next =null }**/ if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; }

2 values()
values().iterator() 返回了一个ValueIterator（）

 final class ValueIterator extends HashIterator implements Iterator<V> { public final V next() { return nextNode().value; } }

next（） 方法也是调用HashIterator.nextNode()方法，只不过是去的value；
3 entrySet()
上代码

 final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } }

直接返回了整个node节点
hashMap遍历顺序
从nextNode（）方法可以看出，hashMap在通过上述三种方法遍历时，都是从table数组 从小下标到大下标，如果发生hash冲突导致链表的，优先遍历链表，因此hashMap的遍历和插入顺序是不同的，和hashCode（）有关 ，按照插入顺序遍历hashMap可以使用LinkedHashMap ，具体用法后面会继续写