JDK 源码阅读004：HashMap
1 引言
尽管哈希表是一种非常常见的数据结构，但是具体的代码实现依旧有很多可以优化的地方，我们可以通过阅读 JDK1.8 的HashMap 源码实现来学习这些优秀的设计。
我们重点关注一些核心的问题：
- HashMap 底层数据结构是怎样的？
- hash 算法为什么要高位与低位做异或运算？
- hash 冲突的处理机制：链表、红黑树
- 扩容机制：两倍扩容、rehash、rehash 的算法优化
- put、get 过程
2 数据结构
2.1 数据结构总览
HashMap(1.8) 底层数据结构是由数组、链表和红黑树组成的。
2.2 Node
static class Node<K,V> implements Map.Entry<K,V> {
// 用来定位数组索引位置
final int hash;
final K key;
V value;
// 链表的下一个node
Node<K,V> next;
}
2.3 table
table，即哈希桶数组是一个 Node 数组
transient Node<K,V>[] table;
3 核心字段
// threshold = capacity * loadFactor，扩容大小的阈值
int threshold;
// 负载因子
final float loadFactor;
// 当前 HashMap 中 <key, value> 的对数
transient int size;
4 hash 算法优化 与 hash 寻址优化
4.1 hash 算法优化
来看看 hash 方法的源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 如果 key 为 null，则会返回 0，否则计算出 key 的 hash 值和 hash 值无符号右移 16 位，并将两者进行异或操作，返回结果值。
我们模拟一下，假设 key.hashCode(）为 ：1111 1111 1111 1111 1100 1100 1100 1100，
将其无符号右移 16 位，得到：0000 0000 0000 0000 1111 1111 1111 1111，
两者异或，得到：1111 1111 1111 1111 0011 0011 0011 0011。
为什么要进行异或操作呢？其实在后续进行 hash 寻址的过程中，一般都是用低 16 位进行运算。进行异或操作，可以让高 16 位也参与运算，在低 16 位同时保留原先高 16 位和低 16 位的特征，从而降低 hash 冲突的概率。
4.2 hash 寻址优化
在 putVal() 方法中，有这么一段代码：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
这里的 (n - 1) & hash 其实就是寻址，相当于 hash / n，但是位运算又比取模运算速度快。
5 put 方法
5.1 put 方法的源码解析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 数组容量初始化：如果数组为 null 或者数组的长度为 0，会进行初次扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. Node 初始化：使用优化后的寻址算法，如果定位到的 Node 元素为 null
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 定位到元素不为空，有3 个分支
Node<K,V> e; K k;
// 如果桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改value值
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))
e = p;
// 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历这个桶对应的链表，binCount用于存储链表中元素的个数
for (int binCount = 0; ; ++binCount) {
// 如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最后插入一个新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果插入新节点后链表长度大于8，则判断是否需要树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 先判断table的长度是否大于64，如果小于64，就通过扩容的方式来解决，避免红黑树结构化
treeifyBin(tab, hash);
break;
}
// 如果待插入的key在链表中找到了，则退出循环
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;
// 在节点被访问后做点什么事，在LinkedHashMap中用到
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 到这里了说明没有找到元素，修改次数加1
++modCount;
// 元素数量加1，判断是否需要扩容
if (++size > threshold)
resize();
// 在节点插入后做点什么事，在LinkedHashMap中用到
afterNodeInsertion(evict);
// 没找到元素返回null
return null;
}
5.2 什么时候会出现 hash 冲突
- key 不一样，但是 hashcode() 方法乱写，导致 hash 值一样；
- hash 值不一样，但是寻址之后在数组中的位置是一样的，出现了 hash 冲突。
5.3 put 流程总结
- 计算key的hash值；
- 如果桶（数组）数量为0，则初始化桶；
- 如果key所在的桶没有元素，则直接插入；
- 如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程 9 处理；
- 如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点；
- 如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中；
- 如果找到了对应key的元素，则转后续流程 9 处理；
- 如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化；
- 如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值；
- 如果插入了元素，则数量加1并判断是否需要扩容；
6 resize 扩容
6.1 扩容算法优化
上文已经讲过寻址的 hash 算法，将 hash & n -1，可以保证扩容之后，根据 hash 值寻址到的地方要么还是原来的 index，要么就是 index + oldCap。
hash & n -1：判断二进制结果中是否多出一个 bit 的 1，如果没多，那么就是原来的 index，否则就是 index + oldCap。通过这种方式，就避免了 rehash 的时候，用每个 hash 对新数组的 length 取模（位运算比取模效率高一些）。
6.2 resize 方法
简而言之就是：两倍扩容 + rehash。
每次 put 了一个新的key-value对之后，size++，比较一下 size 和 threshold（数组的长度 * 负载因子），看是否需要扩容。
if (++size > threshold)
resize();
final Node<K,V>[] resize() {
// 旧数组
Node<K,V>[] oldTab = table;
// 旧容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧阈值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果旧容量达到了最大容量，则不再进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两倍，扩容阈值也扩大为两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 使用非默认构造方法创建的map，第一次插入元素会走到这里
// 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 调用默认构造方法创建的map，第一次插入元素会走到这里
// 如果旧容量旧扩容阈值都是0，说明还未初始化过，则初始化容量为默认容量，扩容阈值为默认容量*默认装载因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 如果新扩容为0，则计算为容量*装载因子，但不能超过最大容量
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 赋值扩容门槛为新门槛
threshold = newThr;
// 新建一个新容量的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果旧数组不为空，则搬移元素
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 如果桶中第一个元素不为空，赋值给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
// 如果这个链表不止一个元素且不是一颗树
// 则分化成两个链表插入到新的桶中去
// 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中
// 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
// 也就是分化成了两个链表
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;
}
}
}
}
}
return newTab;
}
6.3 resize 流程总结
-
如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12；
-
如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方；
-
如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍；
-
创建一个新容量的桶；
-
搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置；
7 get 方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 检查第一个元素是不是要查的元素，如果是直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 如果第一个元素是树节点，则按树的方式查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 否则就遍历整个链表查找该元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
-
计算key的hash值；
-
找到key所在的桶及其第一个元素；
-
如果第一个元素的key等于待查找的key，直接返回；
-
如果第一个元素是树节点就按树的方式来查找，否则按链表方式查找；
参考：
- Java中的移位运算符：https://zhuanlan.zhihu.com/p/30108890
- 红黑树：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md
- HashMap & ConcurrentHashMap: https://crossoverjie.top/%2F2018%2F07%2F23%2Fjava-senior%2FConcurrentHashMap%2F
- 死磕 java集合之HashMap源码分析：https://mp.weixin.qq.com/s/UFeLHR4qtGYPODTiNJDmHQ
- https://tech.meituan.com/2016/06/24/java-hashmap.html
- 深入浅出ConcurrentHashMap1.8：https://www.jianshu.com/p/c0642afe03e0
- 老生常谈，HashMap的死循环：https://www.jianshu.com/p/1e9cf0ac07f4
- 深入分析ConcurrentHashMap1.8的扩容实现：https://www.jianshu.com/p/f6730d5784ad
- ConcurrentHashMap的红黑树实现分析：https://www.jianshu.com/p/23b84ba9a498
- 谈谈ConcurrentHashMap1.7和1.8的不同实现：https://www.jianshu.com/p/e694f1e868ec