Map之HashMap源码
<h1>HashMap 简介</h1>
<pre><code>JDK 1.8 对 HashMap 进行了比较大的优化，底层实现由之前的 “数组+链表” 改为 “数组+链表+红黑树”。
JDK 1.8 的 HashMap 的数据结构，当链表节点较少时仍然是以链表存在，当链表节点较多时（大于8）会转为红黑树。</code></pre>
<h2>HashMap 的一些基本属性</h2>
<pre><code class="language-java">
// 默认容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表节点转换红黑树节点的阈值, 9个节点转
static final int TREEIFY_THRESHOLD = 8;
// 红黑树节点转换链表节点的阈值, 6个节点转
static final int UNTREEIFY_THRESHOLD = 6;
// 转红黑树时, table的最小长度
static final int MIN_TREEIFY_CAPACITY = 64;
// 链表节点, 继承自Entry
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ... ...
}
// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
// ...
}
</code></pre>
<pre><code>定位哈希桶数组索引位置</code></pre>
<p><strong>不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过 HashMap 的数据结构是“数组+链表+红黑树”的结合，所以我们当然希望这个 HashMap 里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表/红黑树，大大优化了查询的效率。HashMap 定位数组索引位置，直接决定了 hash 方法的离散性能。下面是定位哈希桶数组的源码：</strong></p>
<pre><code class="language-java">// 代码1
static final int hash(Object key) { // 计算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;</code></pre>
<pre><code>从过程来讲基本分为三步：</code></pre>
<ul>
<li>拿到key的hashCode值</li>
<li>将hashCode的高位参与运算，重新计算hash值</li>
<li>将计算出来的 hash 值与（table.length-1）进行 & 运算</li>
</ul>
<hr />
<pre><code>对于这个方法的详细解读:</code></pre>
<p><strong>对于任意给定的对象，只要它的 hashCode() 返回值相同，那么计算得到的 hash 值总是相同的。我们首先想到的就是把 hash 值对 table 长度取模运算，这样一来，元素的分布相对来说是比较均匀的。</strong></p>
<p><strong>但是模运算消耗还是比较大的，我们知道计算机比较快的运算为位运算，因此 JDK 团队对取模运算进行了优化，使用上面代码2的位与运算来代替模运算。这个方法非常巧妙，它通过 “(table.length -1) & h” 来得到该对象的索引位置，这个优化是基于以下公式：x mod 2^n = x & (2^n - 1)。我们知道 HashMap 底层数组的长度总是 2 的 n 次方，并且取模运算为 “h mod table.length”，对应上面的公式，可以得到该运算等同于“h & (table.length - 1)”。这是 HashMap 在速度上的优化，因为 & 比 % 具有更高的效率。</strong></p>
<p><strong>在 JDK1.8 的实现中，还优化了高位运算的算法，将 hashCode 的高 16 位与 hashCode 进行异或运算，主要是为了在 table 的 length 较小的时候，让高位也参与运算，并且不会有太大的开销。</strong></p>
<p><strong>图是一个简单的例子：</strong></p>
<p><strong>当 table 长度为 16 时，table.length - 1 = 15 ，用二进制来看，此时低 4 位全是 1，高 28 位全是 0，与 0 进行 & 运算必然为 0，因此此时 hashCode 与 “table.length - 1” 的 & 运算结果只取决于 hashCode 的低 4 位，在这种情况下，hashCode 的高 28 位就没有任何作用，并且由于 hash 结果只取决于 hashCode 的低 4 位，hash 冲突的概率也会增加。因此，在 JDK 1.8 中，将高位也参与计算，目的是为了降低 hash 冲突的概率。</strong>
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/c95a8426a67d4ea05f2a0a69d7b07777" alt="" /></p>
<h2>HashMap 的get方法</h2>
<pre><code class="language-java">
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;
// 1.对table进行校验：table不为空 && table长度大于0 &&
// table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2.检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 3.如果first不是目标节点，并且first的next节点不为空则继续遍历
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 4.如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 5.执行链表节点的查找，向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 6.找不到符合的返回空
return null;
}</code></pre>
<p><strong>如果是红黑树节点，则调用红黑树的查找目标节点方法 getTreeNode。</strong></p>
<pre><code class="language-java">final TreeNode<K,V> getTreeNode(int h, Object k) {
// 1.首先找到红黑树的根节点；2.使用根节点调用find方法
return ((parent != null) ? root() : this).find(h, k, null);
}</code></pre>
<h3>红黑树使用根节点调用的find方法</h3>
<pre><code class="language-java">/**
* 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点
* 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树
* 平衡二叉查找树的特点：左节点<根节点<右节点
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
// 1.将p节点赋值为调用此方法的节点，即为红黑树根节点
TreeNode<K,V> p = this;
// 2.从p节点开始向下遍历
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历
if ((ph = p.hash) > h)
p = pl;
else if (ph < h) // 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历
p = pr;
// 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null) // 6.p节点的左节点为空则将向右遍历
p = pr;
else if (pr == null) // 7.p节点的右节点为空则向左遍历
p = pl;
// 8.将p节点与k进行比较
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) && // 8.1 kc不为空代表k实现了Comparable
(dir = compareComparables(kc, k, pk)) != 0)// 8.2 k<pk则dir<0, k>pk则dir>0
// 8.3 k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历
p = (dir < 0) ? pl : pr;
// 9.代码走到此处, 代表key所属类没有实现Comparable, 直接指定向p的右边遍历
else if ((q = pr.find(h, k, kc)) != null)
return q;
// 10.代码走到此处代表“pr.find(h, k, kc)”为空, 因此直接向左遍历
else
p = pl;
} while (p != null);
return null;
}</code></pre>
<p><strong> 将 p 节点与 k 进行比较。如果传入的 key（即代码中的参数 k）所属的类实现了 Comparable 接口（kc 不为空，comparableClassFor 方法），则将 k 跟 p 节点的 key 进行比较（kc 实现了 Comparable 接口，因此通过 kc 的比较方法进行比较），并将比较结果赋值给 dir，如果 dir<0 则代表 k<pk，则向 p 节点的左边遍历（pl）；否则，向 p 节点的右边遍历（pr）。</strong></p>
<h3>comparableClassFor方法</h3>
<pre><code class="language-java">
static Class<?> comparableClassFor(Object x) {
// 1.判断x是否实现了Comparable接口
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
// 2.校验x是否为String类型
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
// 3.遍历x实现的所有接口
for (int i = 0; i < ts.length; ++i) {
// 4.如果x实现了Comparable接口，则返回x的Class
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}</code></pre>
<h2>HashMap的put方法</h2>
<pre><code>put 方法:</code></pre>
<pre><code class="language-java">
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.校验table是否为空或者length等于0，如果是则调用resize方法进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.通过hash值计算索引位置，将该索引位置的头节点赋值给p，如果p为空则直接在该索引位置新增一个节点即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// table表该索引位置不为空，则进行查找
Node<K,V> e; K k;
// 3.判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4.判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 5.走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，使用binCount统计链表的节点数
for (int binCount = 0; ; ++binCount) {
// 6.如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 7.校验节点数是否超过8个，如果超过则调用treeifyBin方法将链表节点转为红黑树节点，
// 减一是因为循环是从p节点的下一个节点开始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 8.如果e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一个节点
}
}
// 9.如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
// 10.如果插入节点后节点数超过阈值，则调用resize方法进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}</code></pre>
<ul>
<li>校验 table 是否为空或者 length 等于0，如果是则调用 resize 方法进行初始化</li>
<li>如果 p 节点不是目标节点，则判断 p 节点是否为 TreeNode，如果是则调用红黑树的 putTreeVal 方法查找目标节点</li>
<li>校验节点数是否超过 8 个，如果超过则调用 treeifyBin方法 将链表节点转为红黑树节点</li>
</ul>
<h3>putTreeVal</h3>
<pre><code class="language-java">
/**
* 红黑树的put操作，红黑树插入会同时维护原来的链表属性, 即原来的next属性
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 1.查找根节点, 索引位置的头节点并不一定为红黑树的根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
// 2.将根节点赋值给p节点，开始进行查找
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 3.如果传入的hash值小于p节点的hash值，将dir赋值为-1，代表向p的左边查找树
if ((ph = p.hash) > h)
dir = -1;
// 4.如果传入的hash值大于p节点的hash值， 将dir赋值为1，代表向p的右边查找树
else if (ph < h)
dir = 1;
// 5.如果传入的hash值和key值等于p节点的hash值和key值, 则p节点即为目标节点, 返回p节点
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 6.如果k所属的类没有实现Comparable接口 或者 k和p节点的key相等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
// 6.1 第一次符合条件, 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则返回
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
// 6.2 否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找
dir = tieBreakOrder(k, pk); // dir<0则代表k<pk，则向p左边查找；反之亦然
}
TreeNode<K,V> xp = p; // xp赋值为x的父节点,中间变量,用于下面给x的父节点赋值
// 7.dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 走进来代表已经找到x的位置，只需将x放到该位置即可
Node<K,V> xpn = xp.next; // xp的next节点
// 8.创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 9.调整x、xp、xpn之间的属性关系
if (dir <= 0) // 如果时dir <= 0, 则代表x节点为xp的左节点
xp.left = x;
else // 如果时dir> 0, 则代表x节点为xp的右节点
xp.right = x;
xp.next = x; // 将xp的next节点设置为x
x.parent = x.prev = xp; // 将x的parent和prev节点设置为xp
// 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 10.进行红黑树的插入平衡调整
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}</code></pre>
<ul>
<li>第一次符合条件，从 p 节点的左节点和右节点分别调用 find 方法进行查找，如果查找到目标节点则返回</li>
<li>否则使用定义的一套规则来比较 k 和 p 节点的 key 的大小，用来决定向左还是向右查找</li>
<li>进行红黑树的插入平衡调整</li>
</ul>
<h3>tieBreakOrder</h3>
<pre><code class="language-java">
// 用于不可比较或者hashCode相同时进行比较的方法, 只是一个一致的插入规则，用来维护重定位的等价性。
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
**定义一套规则用于极端情况下比较两个参数的大小。**</code></pre>
<h3>treeifyBin</h3>
<pre><code class="language-java">/**
* 将链表节点转为红黑树节点
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 1.如果table为空或者table的长度小于64, 调用resize方法进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 2.根据hash值计算索引值，将该索引位置的节点赋值给e，从e开始遍历该索引位置的链表
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 3.将链表节点转红黑树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
// 4.如果是第一次遍历，将头节点赋值给hd
if (tl == null) // tl为空代表为第一次循环
hd = p;
else {
// 5.如果不是第一次遍历，则处理当前节点的prev属性和上一个节点的next属性
p.prev = tl; // 当前节点的prev属性设为上一个节点
tl.next = p; // 上一个节点的next属性设置为当前节点
}
// 6.将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p）
tl = p;
} while ((e = e.next) != null);
// 7.将table该索引位置赋值为新转的TreeNode的头节点，如果该节点不为空，则以以头节点(hd)为根节点, 构建红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
将 table 该索引位置赋值为新转的 TreeNode 的头节点 hd，如果该节点不为空，则以 hd 为根节点，构建红黑树</code></pre>
<h3>treeify</h3>
<pre><code class="language-java">/**
* 构建红黑树
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 1.将调用此方法的节点赋值给x，以x作为起点，开始进行遍历
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next; // next赋值为x的下个节点
x.left = x.right = null; // 将x的左右节点设置为空
// 2.如果还没有根节点, 则将x设置为根节点
if (root == null) {
x.parent = null; // 根节点没有父节点
x.red = false; // 根节点必须为黑色
root = x; // 将x设置为根节点
}
else {
K k = x.key; // k赋值为x的key
int h = x.hash; // h赋值为x的hash值
Class<?> kc = null;
// 3.如果当前节点x不是根节点, 则从根节点开始查找属于该节点的位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 4.如果x节点的hash值小于p节点的hash值，则将dir赋值为-1, 代表向p的左边查找
if ((ph = p.hash) > h)
dir = -1;
// 5.如果x节点的hash值大于p节点的hash值，则将dir赋值为1, 代表向p的右边查找
else if (ph < h)
dir = 1;
// 6.走到这代表x的hash值和p的hash值相等，则比较key值
else if ((kc == null && // 6.1 如果k没有实现Comparable接口 或者 x节点的key和p节点的key相等
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 6.2 使用定义的一套规则来比较x节点和p节点的大小，用来决定向左还是向右查找
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p; // xp赋值为x的父节点,中间变量用于下面给x的父节点赋值
// 7.dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 8.x和xp节点的属性设置
x.parent = xp; // x的父节点即为最后一次遍历的p节点
if (dir <= 0) // 如果时dir <= 0, 则代表x节点为父节点的左节点
xp.left = x;
else // 如果时dir > 0, 则代表x节点为父节点的右节点
xp.right = x;
// 9.进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求)
root = balanceInsertion(root, x);
break;
}
}
}
}
// 10.如果root节点不在table索引位置的头节点, 则将其调整为头节点
moveRootToFront(tab, root);
}</code></pre>
<ul>
<li>如果当前节点 x 不是根节点, 则从根节点开始查找属于该节点的位置</li>
<li>如果 root 节点不在 table 索引位置的头节点, 则将其调整为头节点</li>
</ul>
<h3>moveRootToFront</h3>
<pre><code class="language-java">/**
* 红黑树的节点移除
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// --- 链表的处理start ---
int n;
// 1.table为空或者length为0直接返回
if (tab == null || (n = tab.length) == 0)
return;
// 2.根据hash计算出索引的位置
int index = (n - 1) & hash;
// 3.将索引位置的头节点赋值给first和root
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// 4.该方法被将要被移除的node(TreeNode)调用, 因此此方法的this为要被移除node节点,
// 将node的next节点赋值给succ节点，prev节点赋值给pred节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
// 5.如果pred节点为空，则代表要被移除的node节点为头节点，
// 则将table索引位置的值和first节点的值赋值为succ节点(node的next节点)即可
if (pred == null)
tab[index] = first = succ;
else
// 6.否则将pred节点的next属性设置为succ节点(node的next节点)
pred.next = succ;
// 7.如果succ节点不为空，则将succ的prev节点设置为pred, 与前面对应
if (succ != null)
succ.prev = pred;
// 8.如果进行到此first节点为空，则代表该索引位置已经没有节点则直接返回
if (first == null)
return;
// 9.如果root的父节点不为空, 则将root赋值为根节点
if (root.parent != null)
root = root.root();
// 10.通过root节点来判断此红黑树是否太小, 如果是则调用untreeify方法转为链表节点并返回
// (转链表后就无需再进行下面的红黑树处理)
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// --- 链表的处理end ---
// --- 以下代码为红黑树的处理 ---
// 11.将p赋值为要被移除的node节点，pl赋值为p的左节点，pr赋值为p 的右节点
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// 12.如果p的左节点和右节点都不为空时
if (pl != null && pr != null) {
// 12.1 将s节点赋值为p的右节点
TreeNode<K,V> s = pr, sl;
// 12.2 向左一直查找，跳出循环时,s为没有左节点的节点
while ((sl = s.left) != null)
s = sl;
// 12.3 交换p节点和s节点的颜色
boolean c = s.red; s.red = p.red; p.red = c;
TreeNode<K,V> sr = s.right; // s的右节点
TreeNode<K,V> pp = p.parent; // p的父节点
// --- 第一次调整和第二次调整：将p节点和s节点进行了位置调换 ---
// 12.4 第一次调整
// 如果p节点的右节点即为s节点，则将p的父节点赋值为s，将s的右节点赋值为p
if (s == pr) {
p.parent = s;
s.right = p;
}
else {
// 将sp赋值为s的父节点
TreeNode<K,V> sp = s.parent;
// 将p的父节点赋值为sp
if ((p.parent = sp) != null) {
// 如果s节点为sp的左节点，则将sp的左节点赋值为p节点
if (s == sp.left)
sp.left = p;
// 否则s节点为sp的右节点，则将sp的右节点赋值为p节点
else
sp.right = p;
}
// s的右节点赋值为p节点的右节点
if ((s.right = pr) != null)
// 如果pr不为空，则将pr的父节点赋值为s
pr.parent = s;
}
// 12.5 第二次调整
// 将p的左节点赋值为空，pl已经保存了该节点
p.left = null;
// 将p节点的右节点赋值为sr，如果sr不为空，则将sr的父节点赋值为p节点
if ((p.right = sr) != null)
sr.parent = p;
// 将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点赋值为s节点
if ((s.left = pl) != null)
pl.parent = s;
// 将s的父节点赋值为p的父节点pp
// 如果pp为空，则p节点为root节点, 交换后s成为新的root节点
if ((s.parent = pp) == null)
root = s;
// 如果p不为root节点, 并且p是pp的左节点，则将pp的左节点赋值为s节点
else if (p == pp.left)
pp.left = s;
// 如果p不为root节点, 并且p是pp的右节点，则将pp的右节点赋值为s节点
else
pp.right = s;
// 12.6 寻找replacement节点，用来替换掉p节点
// 12.6.1 如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换p的位置
if (sr != null)
replacement = sr;
// 12.6.1 如果sr为空，则s为叶子节点，replacement为p本身，只需要将p节点直接去除即可
else
replacement = p;
}
// 13.承接12点的判断，如果p的左节点不为空，右节点为空，replacement节点为p的左节点
else if (pl != null)
replacement = pl;
// 14.如果p的右节点不为空,左节点为空，replacement节点为p的右节点
else if (pr != null)
replacement = pr;
// 15.如果p的左右节点都为空, 即p为叶子节点, replacement节点为p节点本身
else
replacement = p;
// 16.第三次调整：使用replacement节点替换掉p节点的位置，将p节点移除
if (replacement != p) { // 如果p节点不是叶子节点
// 16.1 将p节点的父节点赋值给replacement节点的父节点, 同时赋值给pp节点
TreeNode<K,V> pp = replacement.parent = p.parent;
// 16.2 如果p没有父节点, 即p为root节点，则将root节点赋值为replacement节点即可
if (pp == null)
root = replacement;
// 16.3 如果p不是root节点, 并且p为pp的左节点，则将pp的左节点赋值为替换节点replacement
else if (p == pp.left)
pp.left = replacement;
// 16.4 如果p不是root节点, 并且p为pp的右节点，则将pp的右节点赋值为替换节点replacement
else
pp.right = replacement;
// 16.5 p节点的位置已经被完整的替换为replacement, 将p节点清空, 以便垃圾收集器回收
p.left = p.right = p.parent = null;
}
// 17.如果p节点不为红色则进行红黑树删除平衡调整
// (如果删除的节点是红色则不会破坏红黑树的平衡无需调整)
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 18.如果p节点为叶子节点, 则简单的将p节点去除即可
if (replacement == p) {
TreeNode<K,V> pp = p.parent;
// 18.1 将p的parent属性设置为空
p.parent = null;
if (pp != null) {
// 18.2 如果p节点为父节点的左节点，则将父节点的左节点赋值为空
if (p == pp.left)
pp.left = null;
// 18.3 如果p节点为父节点的右节点， 则将父节点的右节点赋值为空
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
// 19.将root节点移到索引位置的头节点
moveRootToFront(tab, r);
}</code></pre>
<ul>
<li>如果 succ 节点不为空，则将 succ 的 prev 节点设置为 pred，与前面对应（TreeNode 链表的移除）。</li>
<li>代码中的第一次调整和第二次调整是将 p 节点和 s 节点进行了位置调换，然后找出要替换掉 p 节点的 replacement；第三次调整是将 replacement 节点覆盖掉 p 节点；</li>
<li>寻找 replacement，用来替换掉 p 节点。为什么 sr 是 replacement 的首选，p 为备选？
<strong>解析：首先我们看 sr 是什么？从代码中可以看到 sr 第一次被赋值时，是在 s 节点进行了向左穷遍历结束后，因此此时 s 节点是没有左节点的，sr 即为 s 节点的右节点。而从上面的第一次调整和第二次调整我们知道，p 节点已经跟 s 节点进行了位置调换，所以此时 sr 其实是 p 节点的右节点，并且 p 节点没有左节点，因此要移除 p 节点，只需要将 p 节点的右节点 sr 覆盖掉 p 节点即可，因此 sr 是 replacement 的首选，而如果 sr 为空，则代表 p 节点为叶子节点，此时将 p 节点直接移除即可。</strong></li>
</ul>
<p><strong>p 节点不为根节点，p 节点有左右节点，s 节点不为 pr 节点，s 节点有右节点。</strong></p>
<ul>
<li>第一次调整 + 第二次调整：将 p 节点和 s 节点进行了位置调换，选出要替换掉 p 节点的 replacement</li>
<li>第三次调整：将 replacement 节点覆盖掉 p 节点
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/d8ec93ede55f09310d03fc625f68a67c" alt="" /></li>
</ul>
<blockquote>
<p>关于红黑树的平衡调整？</p>
</blockquote>
<hr />
<p>答：红黑树的操作涉及的操作比较复杂，三言两语无法说清。有兴趣的可以去单独学习，本文由于篇幅关系暂不详细介绍红黑树的具体操作，在这简单的介绍：红黑树是一种自平衡二叉树，拥有优秀的查询和插入/删除性能，广泛应用于关联数组。</p>
<p>对比 AVL 树，AVL 要求每个节点的左右子树的高度之差的绝对值（平衡因子）最多为 1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，而这虽然会导致红黑树的查询会比 AVL 稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。</p>
<h2>在 HashMap 中的应用：HashMap 在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion 方法）或删除平衡调整（balanceDeletion 方法），调整的方式主要有以下手段：左旋转（rotateLeft 方法）、右旋转（rotateRight 方法）、改变节点颜色（x.red = false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。</h2>
<h2>死循环问题</h2>
<p>在 JDK 1.8 以前，Java 语言在并发情况下使用 HashMap 造成 Race Condition，从而导致死循环。程序经常占了 100% 的 CPU，查看堆栈，你会发现程序都 Hang 在了 “HashMap.get()” 这个方法上了，重启程序后问题消失。具体分析可以查看这篇文章：疫苗：JAVA HASHMAP的死循环，有人将这个问题当成一个 bug 提给了 Sun，但是 Sun 认为这并不是个 bug，因为HashMap 本来就不保证并发的线程安全性，在并发下，要用 ConcurrentHashMap 来代替。</p>
<p>那么，在JDK 1.8 的时候，这个问题解决了吗？</p>
<p>我们知道，JDK 1.8 以前，导致死循环的主要原因是扩容后，节点的顺序会反掉，如下图：扩容前节点 A 在节点 C 前面，而扩容后节点 C 在节点 A 前面。
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/ae61a9390a6c5da35f7d8b47acf07fb5" alt="" /></p>
<h2>JDK 1.8扩容过程</h2>
<pre><code>JDK1.8 普通链表的扩容代码，如下图所示，在上文已经分析过了：主要是在一个 do/while 中处理同一个位置的所有节点。</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/eeeea1495d7f111830dc052e2eadf25e" alt="" /></p>
<h3>举个例子</h3>
<p>前提：我们假设有3个节点，节点 A，节点 B，节点 C，并且假设他们的 hash 值等于 key 值，则按上图扩容的过程模拟如下。</p>
<p>先看下老表和新表计算索引位置的过程：（hash 计算省略前面 28 位 0，只看最后 4 位）
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/8178f3d96bb3a829833502a792c0d6de" alt="" /></p>
<h3>具体扩容过程：</h3>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/39743d707e96f33a3faf9a1f9d091570" alt="" />
<strong>结果：可以看出，扩容后，节点 A 和节点 C 的先后顺序跟扩容前是一样的。因此，即使此时有多个线程并发扩容，也不会出现死循环的情况。当然，这仍然改变不了 HashMap 仍是非并发安全，在并发下，还是要使用 ConcurrentHashMap 来代替。</strong></p>
<h2>HashMap 和 Hashtable 的区别</h2>
<ul>
<li>HashMap 允许 key 和 value 为 null，Hashtable 不允许。</li>
<li>HashMap 的默认初始容量为 16，Hashtable 为 11。</li>
<li>HashMap 的扩容为原来的 2 倍，Hashtable 的扩容为原来的 2 倍加 1。</li>
<li>HashMap 是非线程安全的，Hashtable是线程安全的。</li>
<li>HashMap 的 hash 值重新计算过，Hashtable 直接使用 hashCode。</li>
<li>HashMap 去掉了 Hashtable 中的 contains 方法。</li>
<li>HashMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类。</li>
</ul>
<h1>总结</h1>
<ol>
<li>HashMap 的底层是个 Node 数组（Node<K,V>[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。</li>
<li>增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key 的 hashCode 值；2）将 hashCode 的高位参与运算，重新计算 hash 值；3）将计算出来的 hash 值与 “table.length - 1” 进行 & 运算。</li>
<li>HashMap 的默认初始容量（capacity）是 16，capacity 必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * load factor。</li>
<li>HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。</li>
<li>导致 HashMap 扩容后，同一个索引位置的节点重 hash 最多分布在两个位置的根本原因是：1）table的长度始终为 2 的 n 次方；2）索引位置的计算方法为 “(table.length - 1) & hash”。HashMap 扩容是一个比较耗时的操作，定义 HashMap 时尽量给个接近的初始容量值。</li>
<li>HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。</li>
<li>当同一个索引位置的节点在增加后达到 9 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。</li>
<li>当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。</li>
<li>HashMap 在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。</li>
<li>HashMap 是非线程安全的，在并发场景下使用 ConcurrentHashMap 来代替。</li>
</ol>