JAVA集合框架----HashMap之红黑树_hashmap 红黑树

「这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战」

1. 红黑树概述

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求： 【1】性质1. 节点是红色或黑色。 【2】性质2. 根节点是黑色。 【3】性质3 每个叶节点（NIL）是黑色的。 【4】性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 【5】性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2.HashMap源码分析

hashmap实现树化代码如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// resize()扩容。
resize();
// 通过hash求出bucket的位置。
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 将每个节点包装成TreeNode。
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
// 将所有TreeNode连接在一起此时只是链表结构。
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 对TreeNode链表进行树化。
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}

这个方法所做的事情就是将刚才九个项以链表的方式连接在一起，然后通过它构建红黑树。可以看出出真正的维护红黑树结构的方法并没有在HashMap中，全部都在TreeNode类内部。

final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 以for循环的方式遍历刚才我们创建的链表。
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 为树根节点赋值。
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
// x即为当前访问链表中的项。
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//此时红黑树已经有了根节点,上面获取了当前加入红黑树的功Bkey和hash值进入核心循环,这里从root开始，是以一个自质向下的方式遍历添加 for循环设有控制条件,由代码内reak.跳出循环
for (TreeNode<K,V> p = root;