HashMap 的底层原理和扩容机制一直都是面试的时候经常被问到的问题，同时也是集合源码中最难阅读的一部分😢，之前更新的 ArrayList 源码阅读收获了很多朋友的喜欢，也给了我很多自信；本次我准备完成一个关于 HashMap 源码阅读和解析的专栏，共分为四部分内容：
- 概念辨析、属性和构造方法的源码阅读
- putVal() 和 resize() 方法的源码分析
- 详细讲解红黑树
- HashMap 中与树有关的方法
通过阅读这些内容相信大家一定可以彻底的搞懂 HashMap，如果喜欢文章的话不要忘记订阅专栏和关注。😊
前言：
本篇是专栏的第二部分：putVal 方法和 resize 方法，这是 HashMap 源码中最重要的两个方法，涉及到初始化和扩容机制等重点的知识，大家在阅读之前需要对 Java 中的位运算有一定的了解，同时需要首先阅读上一篇博客，对基本的常量和构造方法有基本的理解和把握。
上篇博客导航：
万字源码解析！彻底搞懂 HashMap【一】：概念辨析与构造方法源码解析文章目录
- 3.源码阅读第二部分- putVal()与 resize() 方法
- 3.1 put() 方法
- 3.2 resize() 方法
3.源码阅读第二部分- putVal()与 resize() 方法
3.1 put() 方法
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
put() 方法就是向 HashMap 中插入数据的方法 put() 方法中实际调用的是 putVal() 方法，在参数中还调用了 hash(key) 方法，先来阅读一下这个方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
将语句拆分一下可以得到如下的代码
int h;
if (key == null) {
return 0;
} else {
h = key.hashCode();
return h ^ (h >>> 16);
}
如果 key 是 null，那就直接映射为 0，否则就执行 hashCode() 方法获得哈希值（有可能是 native 也有可能是重写的方法），存入 h 中。
然后将 h 和 h 右移 16 位获得的数做 按位异或 操作，这一步的作用在哪里呢？
首先来回顾一下上面提到果的路由算法
(table.length - 1) & node.hash
当数组长度很小的时候，使用到的 h 的位数就越少，此时就会导致重复的概率大大增大；此时将 h 与 h >>> 16 进行按位异或操作，可以将 高位的数字参与到运算当中，来降低哈希冲突的概率，这其实就是扰动函数，然后将这个值返回作为实际被使用的哈希值。
接下来让我们进入 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;
if ((tab = table) == null || (n = tab.length) == 0) // 说明此时还未进行过初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 这个索引上没有元素（未出现哈希冲突）
tab[i] = newNode(hash, key, value, null);
else { // 有数据的情况
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 本节点的 key 和本次插入的 key 相同（替换操作）
e = p;
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) { // 遍历过程中没有找到与插入节点 key 相同的情况
p.next = newNode(hash, key, value, null);
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)))) // 遍历节点的时候找到了与插入节点 key 相同的节点
break;
p = e;
}
}
if (e != null) { // 针对与 替换 操作的逻辑
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 针对非替换操作的逻辑
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
对于这种长方法，首先要理清楚整个方法的脉络，这里给出一个大致的流程图，通过流程图和上面的注释大致熟悉一下每一块代码的作用，下面正式进入源码的解析。
Node<K,V>[] tab; // 指向当前 HashMap 中的 table 的指针
Node<K,V> p; // 当前散列表中的元素
int n, i; // n 表示散列表数组的长度，i 表示路由寻址的结果
参考上面给出的注释，首先先来了解一下方法中使用到了哪些变量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
然后来看第一个 if 语句，首先将 tab 指向了本 HashMap 的 table，然后判断它是否为 null，同时将 table 的长度赋值给 n；if 中判断的是 table 是否被初始化，如果没有被初始化就执行 if 代码块中的部分，进行table的初始化，其中的 resize() 也是很重要的方法，这个放到后面详细讲解。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
然后继续看下一个 if 语句，i = (n - 1) & hash 这个式子大家一定不陌生了，这就是上面提到的路由寻址，找到对应的地址后将该索引位置的元素赋值给 p。
此时 p 有两种可能：null 和 非 null，如果是 null 说明这个索引是第一次使用，执行代码快中的逻辑，直接给tab[i] 赋值即可，这是最简单的情况；如果不是 null 则说明该位置上有数据，有数据同样也有两种可能
- 出现了哈希冲突，需要往后延申链表
- 就是完全相同的 key，执行的是替换的操作
下面的代码就是针对这些情况进行的处理。
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
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);
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;
}
}
if (e != null) { // 针对与 替换 操作的逻辑
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
仍然是一个很长的部分，让我们来逐步拆解一下：
Node<K,V> e; K k; // e:如果执行的是替换的操作，e 中存储的就是要替换的节点的地址，k：临时变量
先参考上面的注释了解一下使用到的变量，然后正式进入这一部分的阅读：
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
回顾一下此时的境况，我们要插入节点的索引上有内容，p 为当前索引上的节点，首先来判断它是否和传入的 key 是相同的，如果是相同的，那进行的其实就是替换的操作。
e 就是来存储要替换的节点的索引的，如果它不为空就说明要执行替换的操作。
注意来看一下 HashMap 中判断两个元素是否相同的逻辑：
- 判断两个元素的哈希值是否相同
- 调用 equals 方法来判断两个元素是否相同
这其实就牵扯出来一个非常经典的面试题，为什么重写 equals 方法的同时也要重写 hashCode 方法：
在 Object 类中提供的默认的 equals 方法是比较的内存，而 hashCode 方法通过哈希函数映射内存来得到哈希值的，所以如果使用默认的方法，那比较的就都是内存，判断两个元素是否相同的依据就是它们处于同一块内存之中
但是这样的判断方法太过于绝对了，比如我有一个 Staff 类，有两个属性，IdentityCard（id号）、name（姓名），我希望 id 号 和 姓名均相等的两个员工被视作同一名员工，此时通过内存的比较肯定就无法实现了，此时就需要重写 equals 方法，但是在 HashMap 中，首先去比较的还是哈希值，所以我们同时要保证拥有相同 id 号和相同姓名的两个实例要被映射为同一个哈希值，此时就需要去重写 hashCode 方法，将这两个方法都按照我们的逻辑进行重写就能保证它们会被识别为相同的对象。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
这里是为了判断 p 是不是树节点（红黑树），关于树的方法都放在红黑树讲解之后在进行解析。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
如果前两个条件都不符合的话，就尝试去遍历这个节点上的链表：
如果 p.next() 为 null 的时候，就说明已经遍历到了链表的最后一个节点，此时还没有找到，说明这是一个新的需要插入的节点，就将其插入到 p.next() 的位置。
但是如果发现 e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))) 就说明在链表中查找到了相同的 key，此时执行的是 替换操作，此时就用 e 记录下来需要进行替换的节点。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
执行完上面的逻辑之后，去判断 e 是否为空，如果不为空，就说明需要执行替换的操作，直接执行 if 代码块中的方法来进行替换，替换完成后是直接 return 将方法结束，不会执行后面的流程，返回的是节点原本的 value。
但如果执行的不是替换操作的话，就执行如下的逻辑：
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
首先对 modCount 进行自增（替换操作就不需要自增，因为不改变结构）；然后判断当前长度是否需要进行扩容，如果需要就执行扩容的操作。
3.2 resize() 方法
final Node<K,V>[] resize() {
// 第一部分：确定 newCap 和 newThr 的值
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 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;
if ((e = oldTab[j]) != null) { // 如果不为 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 { // 有多个节点的情况（处理哈希冲突）
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;
}
resize() 代码看起来很长，但是其执行的流程相比于 putVal() 方法要简单很多，代码总体分为两个部分：
- 确定新的容量（newCap）和新的扩展阈值（newThr）
- 如果需要的话，将旧数组中的内容转移到拓展后的数组中
首先还是来分析一下方法中用到的变量：
Node<K,V>[] oldTab = table; // 指向当前数组的指针
int oldCap = (oldTab == null) ? 0 : oldTab.length; // resize 之前 table 的长度
int oldThr = threshold; // resize 之前扩容阈值的大小
int newCap, newThr = 0; // 新的 table 长度和新的阈值大小
可以看出上面的 newCap 和 newThr 都是没有赋值的，紧接着后面一段代码就是给这两个值赋值：
if (oldCap > 0) {
// 普通的扩容机制
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果旧的容量已经大于等于最大容量
threshold = Integer.MAX_VALUE; // 将扩容阈值设定为 Integer.MAX_VALUE
return oldTab; // 结束扩容
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 二倍扩容
newThr = oldThr << 1; // double threshold
}
首先去判断原本的数组中是否有内容，如果没有就不需要执行转移的操作
然后判断旧的容量是否已达到最大容量 MAXIMUM_CAPACITY，如果已经达到这个容量 2 的 31 次方 - 1 就将下一次的扩容阈值设定为 Integer.MAX_VALUE，此时不会去拓展原数组，直接结束本次的扩容操作。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 二倍扩容
newThr = oldThr << 1; // double threshold
这里的 else-if 语句是为了排除 容量极大 和 容量极小 的情况，其中的语句是针对容量适中的情况做处理：
- 如果 (newCap = oldCap << 1) >= MAXIMUM_CAPACITY 就说明扩容之后容量大于最大容量限制 MAXIMUM_CAPACITY
- 如果 oldCap < DEFAULT_INITIAL_CAPACITY 就说明容量没有达到默认的初始容量（16）说明此时 oldThr 还是 0
对于如上的两种情况，要在后面进行特殊的处理；如果不在这两种情况之中就执行代码块中的语句，直接扩容二倍。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
此时 oldCap > 0 的情况已经处理完成了，现在要处理的是 oldCap == 0 的情况，也就是第一次扩容的情况
首先处理的是 oldThr > 0 的情况，在未初始化的情况下，通过上面阅读过的源码可以知道，如果此时 oldThr 有值，那这个值一定是在前面的构造方法中 指定的容量，这个容量被暂存在 oldThr ****中，在第一次扩容的时候发挥作用
如果 oldThr 没有被赋值，就使用默认的容量（DEFAULT_INITIAL_CAPACITY）和默认的扩容阈值（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY）。
此时就已经给 newCap 和 newThr 赋值了，但是有一种情况是未被对 newThr 赋值的，就是容量过大或者oldThr为0的情况 (newCap = oldCap << 1) >= MAXIMUM_CAPACITY || oldCap < DEFAULT_INITIAL_CAPACITY 上面我们提到会在后面进行处理，下面就是对这两种情况进行处理的逻辑：
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
首先将 newCap * loadFactor 容量乘上负载因子
- 如果oldThr为0的时候（newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY）就将 ft 赋值给 newThr
- 否则，就是容量过高的情况，newThr 就设定为 Integer.MAX_VALUE
此时 newCap 和 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;
if ((e = oldTab[j]) != null) { // 如果不为 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 { // 有多个节点的情况（处理哈希冲突）
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;
}
}
}
}
}
下面开始对这一大段代码进行详细的讲解：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
首先根据上面计算出来的 newCap 构造了一个新的更大的数组；然后去判断是否需要进行数据的转移，如果 oldTable 不为空的话就需要遍历数组来进行转移，如果遍历到非空的节点就进行转移的逻辑
对于一个节点有三种情况，分别对应着代码中的 if、if-else 和 else 语句段：
if (e.next == null)
// 那在更高位的路由中也不会出现哈希冲突，计算路由直接插入
newTab[e.hash & (newCap - 1)] = e;
如果 e.next == null 的话就说明此时这个索引下面仅有一个元素，此时就计算它在新数组中的索引然后直接插入即可；这是第一种情况。
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;
}
}
然后就是最后一种情况，处理链表，这一块理解起来可能有些困难，我们先来了解一下其中用到的临时节点：
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
其中的 lo 是 low 的简写，hi 是 high 的简写，分别代表着高位和低位，比如说原本数组的长度为 16，此时拓展就会将长度拓展为 32，那原本的那一段长度 1 到 16 就是低位，17 到 32 这部分就是高位；上面 loHead 就是处于低位节点的头部，loTail 就是处于低位的节点的尾部，hiHead 和 hiTail 就是高位的头部和尾部。
那为什么要有高位和低位的区分呢？注意我们此时遍历的是一个链表，它在数组的相同位置上，也就说明 它们的哈希值与 （数组长度 - 1） 异或 之后得到的值是 相同 的。
比如说还是 16 拓展到 32 的情况，一个节点在新的数组中位与高位还是低位取决于上图中这个新的被使用到的部分是 0 还是 1，如果是 0 的话，与新的全 1 执行按位与的操作，得到的结果与其在原数组时的下标相同，反之则会处于一个新的下标（原下标 + 16）。
源码中通过这个方式判断新的一位是 1 还是 0：(e.hash & oldCap) == 0 它将 oldCap（一定是 2 的幂次 0B100000…）和哈希做了一个按位与的操作，如果这个新的部分是 0 的话，经过与的操作得到的结果就是 0，此时其位于低位，反之则位于高位，当 while 循环结束后会得到两个链表，然后将它们插入新的数组中：
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
下标也与上面推导的结果相同，最终返回生成的 table。
