HashMap 定义
下面是 HashMap 的一个类图：
::: hljs-center
HashMap 类图
:::
从类图可知，除了两个象征性的接口 Cloneable 和 Serializable, HashMap 顾名思义其实就是 Map 的一种哈希实现方式。哈希算法在设计良好的情况下，大部分查找能在 O(1) 时间内完成。而键值对映射作为时下开发必需的数据类型，一般开发语言都会内部提供其实现方式，例如 python 的 dictionary 和 golang 的 map。值得注意的是， HashMap 并不是线程安全的， 当开发需要 HashMap 对象作为一个多线程共享变量的时候，可以使用 JUC 包下的 ConcurrentHashMap， 它使用的分段加锁技术能保证其在多线程环境下的安全和高性能，对比使用 synchronized 来保证线程安全的 Hashtable，使用 ConcurrentHashMap 无疑是更加明智的举动。
内部类
HashMap 定义了许多的内部类，作为实现 HashMap 必需的结构类型。能够清晰地掌握这些内部类的实现方式和实现目的，是了解 HashMap 的必要前提。
Node，TreeNode
这两个类都是作为 HashMap 的基础节点存在的， 用于储存键值对信息。 一般情况下， HashMap 的节点是 Node 类型的， 而 TreeNode 则是为了服务红黑树而存在的。
从源码可知，Node 类是 Map.Entry 接口的一种实现， 而 TreeNode 则是 Node 的一个派生类。
下面是 Map.Entry 的官方文档部分说明：
A map entry (key-value pair). The Map.entrySet method returns a collection-view of the map, whose elements are of this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view.
由此可见，除了储存键值对信息外，这个接口的实现还作为 Map 的集合视图的基础元素，提供给迭代器访问。
值得注意的是， TreeNode 并不直接继承于Node， 而是继承自 LinkedHashMap 的内部类 Entry， 而 LinkedHashMap.Entry 才是继承自 HashMap.Node。LinkedHashMap.Entry 相比与 HashMap.Node, 只是扩展了两个引用，用于连接 HashMap 的所有节点，使得 HashMap 中的数据同时也能以双向链表的形式提供服务。而令人费解的是， HashMap 作为 LinkedHashMap 的父类， 会依赖子类的内部类实现。
KeySet, Values, EntrySet
这三个内部类则与 Map 接口定义的三个方法 keySet(), values(), entrySet() 是息息相关的。Map 接口要求其实现类会提供其键，值与及键值对一个集合形式的访问方法。而这三个类， 则是 HashMap 分别用于实现这三个方法的返回。这三个内部类实际不会保存任何信息，对他们的查询和操作会直接作用与 HashMap 的变量。而它门的遍历实现，则是直接对 HashMap 的数据数组进行遍历。
下面是 EntrySet 的一个遍历实现：
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
// 将 table(HashMap 的实际数据储存) 引用赋值给 tab
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// 遍历tab，并检查元素下是否存在由于哈希碰撞形成的链表
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
HashIterator, KeyIterator, ValueIterator, EntryIterator
众所周知，集合 Collection 是会要求其实现提供一个迭代器返回，用户获取和操作集合中的数据。而这四个内部类就是为此而生的。HashIterator 是其余三个类的一个父类， 它是一个抽象类，提供了 Iterator 的主要方法 hasNext(), nextNode() 等的实现。其迭代方式和上面提及的集合遍历方式其实是一样的，这里就不赘述了。
HashMapSpliterator, KeySpliterator, ValueSpliterator, EntrySpliterator
Spliterator 是 Java8 新加入的一个接口，Collection 接口新增了默认方法 spliterator() 要求返回这个东西。这个单词初看之下容易让人产生疑惑， 其实它是 split + iterator 的拼写，翻译过来应该是可分的迭代器。它是为了并行执行而设计的迭代器。这个东西我了解的也不多，暂且略过吧。
变量
HashMap 中定义的变量并不多，大部分顾名思义能清楚其定义的作用。了解这些变量能更好地理解 HashMap 的运作细节。
静态变量
// HashMap 缺省的初始化大小， 2的四次方，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap 的最大容量，整型的最大值为2的31次方减一，而HashMap的容量必须为2的次方，所以最大值为这个
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子，用于计算触发HashMap扩容的阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 哈希碰撞时链表树化的阈值
static final int TREEIFY_THRESHOLD = 8;
// 树变回链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 树化时HashMap的最小容量，容量不够则会触发扩容
static final int MIN_TREEIFY_CAPACITY = 64;
实例变量
// 实际保存数据的数组
transient Node<K,V>[] table;
// 键值对的集合视图
transient Set<Map.Entry<K,V>> entrySet;
// 这里是指键值对的个数，并不是HashMap的容量
transient int size;
// 当HashMap数据产生变化是，这个值会加一，当迭代过程中这个值产生变化，会导致迭代抛出异常(fail-fast)
transient int modCount;
// 触发扩容的阈值
int threshold;
// 构造函数的负载因子会赋值给这个变量，没有则将默认的DEFAULT_LOAD_FACTOR赋值给这个变量
final float loadFactor;
方法
HashMap 的方法有很多，将每个方法都加以记录和说明有点没必要，因此我只会选择几个我认为关键的方法进行分析。
hash()
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash() 方法用于计算 key 的哈希值。
从以上代码可知，当 key 为 null 是，哈希值是0，HashMap 可以保存 key 值为 null 的键值对。而计算出来的 hash 值，是不能对值进行直接定位的。从概念上来说，完整的散列函数应该是 hash(key) & (n - 1), 其中 n 为散列表当前的长度，这样计算出来的值，才是键值对在散列表中的索引。之所以这样做， 是因为 HashMap 使用的散列方法是取模法， 而当 n 值为 2 的次方时，a & (n - 1) 的值和 a % n 的值是相等的，而与运算则会比取模运算获得更好的性能，这也是 HashMap 规定散列表的长度必须为 2 的次方的原因。也是因为这种做法，对于比 n 的位数更高的bit，是无法对散列函数产生影响的。所以注意到上面 hash 函数中， 它并不直接取 key 的 hashCode 作为运算值，而还和它的本身右移16位后做了个异或操作，从而提高高位bit对散列函数的影响。
putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 散列表为空或长度为0， 初始化散列表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算散列值 (n - 1) & hash， 如果该位置没有值，将当前键值对插入到该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 该位置key值相同， 记录后根据参数来选择是否替换值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果该位置节点已经树化， 则把这些值传入TreeNode 的方法，交给它处理
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 该位置没有树化，则已链表的形式解决哈希冲突，插入相应的值
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度达到树化的阈值，treeifyBin 其实不一定会将节点树化， 如果容量不足，则会扩容
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 根据一些传参，当key 相同是，是否提换值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 键值对达到扩容阈值， 进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal() 方法主要用于往散列表添加键值对。
其中整体的逻辑是非常清晰明了的，整个流程我都添加了注释，理解起来也不难。值得注意的是，其中 afterNodeAccess(e) 和 afterNodeInsertion(evict) 在 HashMap 中是空函数，这些定义主要是作为回调服务于 LinkedHashMap 的。在我看来，这个 HashMap 作为父类属实也太为子类着想了吧。前面有 TreeNode 继承自 LinkedHashMap.Entry 的强依赖， 后面又搞这些东西给它开后门，我觉得称它们是夫妻也不为过。
此外，插入键值对涉及到红黑树的一些内容，而红黑树要讲的话则涉及太多了，限于篇幅这里暂且略过（其实就是不懂）。
resize()
// 省去了一些边界计算逻辑
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 纯节点， 没有链表
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 树化节点
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 链表节点
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
resize 主要用于 HashMap 扩容。
上面那段代码取自 resize 函数的部分, 该部分主要负责将结点放进新的散列表里。除了红黑树暂且不提，值得注意的就只有关于链表在扩容时的逻辑了。主要逻辑是，将该链表拆分为两个链表，再插入新的散列表对应的散列位置即可。为什么会拆分为两个链表呢，举个例子就较为容易明白了。当 HashMap 从 16 扩容为 32 时，同一链表中的节点的散列位置只可能有两种情况：
- 当 16 <= hash <= 31时，散列位置发生了变化。 例如 17 % 32 = 17， 17 % 16 = 1。因此，key的哈希值在这个范围时会发生变化。
- 当 hash < 16 || hash > 31 时，散列位置是没有发生变化的。 例如 32 % 16 = 32 % 32 = 0。 因此， key的哈希值是不会发生变化的。
综上所述呢，只需将原链表拆分为两个链表，插入对应的散列位置即可。同时，也是因为这个原因，扩容过程中并不会产生额外的哈希碰撞，这也是将散列表的容量固定为2的次方的好处。
更多好看的博客请关注狗带博客， 比心
网友评论