《Java8源码》图解HashMap链表转红黑树含红黑树插入节点、平衡、变色、左/右旋
一、前言
1、链表是什么时候转红黑树的?
1、在putVal()方法中如果链表长度
大于阈值8
;会进入到treeifyBin()
方法中执行链表转红黑树操作;
2、HashMap中有个MIN_TREEIFY_CAPACITY
变量 等于64,表示允许执行treeifyBin()
链表转红黑树操作时HashMap数组的最小容量;如果数组容量容量小于64,则先执行扩容操作;
聊完了链表什么时候转红黑树,下面我们来看一下链表是怎么转红黑树的?
上面我们提到了treeifyBin()这个方法,链表转红黑树的逻辑也就在这个方法中。
二、源码分析
1、treeifyBin()
HashMap的putval()方法中调用treeifyBin()方法执行链表转红黑树操作;而treeifyBin()主要做两件事:
1、先根据hash计算出当前链表所在table数组中的位置,然后将其数据结构从
单向链表Node
转为双向链表TreeNode
;
2、如果双向链表TreeNode的头节点hd不为null,则调用treeify()
方法对TreeNode双向链表进行树型化操作
;
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 数组长度小于64时,就先进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 如果新增的node 要插入的数组位置已经有node存在了,取消插入操作
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 步骤一:遍历链表中每个节点,将Node转化为TreeNode
// hd指向头节点,tl指向尾节点
TreeNode<K,V> hd = null, tl = null;
do {
// 将链表Node转换为红黑树TreeNode结构
TreeNode<K,V> p = replacementTreeNode(e, null);
// 以hd为头结点,将每个TreeNode用prev和next连接成新的TreeNode链表
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 步骤二:如果头结点hd不为null,则对TreeNode双向链表进行树型化操作
if ((tab[index] = hd) != null)
// 执行链表转红黑树的操作
hd.treeify(tab);
}
}
接着我们看一下真正将链表转成红黑树的地方:treeify()
方法;
2、treeify()
treeify()方法中大体上分为三步:
1、遍历TreeNode双向链表,确定
待插入节点x
在其父节点的左边还是右边
,然后将其插入节点到红黑树中;
2、插入节点之后树结构发生变化,需要通过变色和旋转操作维护红黑树的平衡;
3、因为调整了红黑树,root节点可能发生了变化,所以需要把最新的root节点放到双向链表的头部,并插⼊到table数组中。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 最开始的x表示TreeNode双向链表的头结点
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;
}
else {
// 第一部分
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// p 表示parent节点
for (TreeNode<K,V> p = root;;) {
// dir表示x节点在parent节点的左侧还是右侧
int dir, ph; // ph表示parent节点的hash值
K pk = p.key; // pk表示parent节点的key值
// x节点在parent节点的左侧
if ((ph = p.hash) > h)
dir = -1;
// x节点在parent节点的右侧
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 第二部分
TreeNode<K,V> xp = p; // xp表示x的父节点
// 如果p节点的左节点/右节点不为空,则令p = p.left/p.right,继续循环
// 直到p.left/p.right为空
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 令待插入节点x的父节点为xp, 即p
x.parent = xp;
// 根据dir判断插入到xp的左子树(<0)还是右子树(>0)
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 往红黑树中插入节点后,进行树的平衡操作
root = balanceInsertion(root, x);
break;
}
}
}
}
// 将root节点插入到table数组中
moveRootToFront(tab, root);
}
在往红黑树中插入一个节点之后,会调用balanceInsertion()
方法进行树的平衡操作,我们来看一下红黑树是怎么进行平衡的?
3、balanceInsertion()
这里和TreeMap中插入节点之后进行的红黑树平衡操作fixAfterInsertion()
类似。在文章:图解TreeMap的红黑树平衡操作fixAfterInsertion(),接着手撕红黑树添加节点中我们详细介绍;
对红黑树进行平衡操作时,主要分两部分:直接返回、变色旋转后返回;
第一部分:
直接返回
根节点:1、如果待插入节点x
没有parent节点
,直接把x的节点变为黑色
,并作为根节点返回
;2、如果
x的父节点为黑色
、或者没有祖父节点
,则直接返回
根节点root;第二部分:根据x节点在父节点xp的左侧还是右侧、xp节点再其父节点xpp的左侧还是右侧进行
旋转、变色
;
- 如果x的父节点xp是祖父节点xpp的
左子节点
:0)若x的祖父节点xpp的右子节点xppr存在并且是红色,直接交换祖父节点和其子节点的颜色、并返回。
1)若x是其父节点xp的右子节点,交换x和xp的位置
,然后对x进行左旋
;2)接着设置
父节点xp为黑色
、祖父节点xpp为红
色,以xpp节点为轴右旋
。
x的父节点xp是祖父节点的右子节点:
这里和上面的类似,只是左旋变右旋、右旋变左旋;
0)若x的祖父节点xpp的左子节点xppl并在并且是红色,直接交换祖父节点和其子节点的颜色、并返回。
1)若x是其父节点xp的左子节点,交换x和xp的位置
,然后对x进行右旋
;2)接着设置
父节点xp为黑色
、祖父节点xpp为红
色,以xpp节点为轴左旋
。
代码如下:
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 将待插入节点x的节点颜色置为红色
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 1、如果x没有父节点,自己变为黑色节点、作为根节点返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 2、如果x的父节点为黑色或者没有祖父节点,则直接返回root
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 3、如果x的父节点xp是祖父节点的左子节点
if (xp == (xppl = xpp.left)) {
// 1)仅变色:
// 如果xp和xppr都是红色节点,则把xppr、xp置为黑色、zpp置为红色。
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// 2)旋转 变色:
else {
// (1)如果x 是其父节点xp的右子节点。令当前节点为其父节点,然后对当前节点x进行左旋
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// (2)如果x的父节点xp不为空
if (xp != null) {
// 令xp的颜色为黑色
xp.red = false;
// 如果x的祖父节点xpp不为空
if (xpp != null) {
// 令xpp的颜色为红色
xpp.red = true;
// 对祖父节点xpp进行右旋
root = rotateRight(root, xpp);
}
}
}
}
// 4、x的父节点xp是祖父节点的右子节点
else {
// 逻辑和3、类似,只是单纯的左变右、右变左
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
可能上面一顿文字描述,不够直观,下面我们结合源代码图解分析;
上面第二部分的场景一:
x的父节点xp是祖父节点xpp的左子节点
;
0)变色操作
若x的祖父节点xpp的左子节点xppl并在并且是红色,直接交换祖父节点和其子节点的颜色;
1、2)左旋 变色 右旋操作
(1)步骤一:将树节点左旋到同一侧;
(2)步骤二:父节点和祖父节点变色,以祖父节点xpp为轴右旋;
上面第二部分的场景二:
x的父节点xp是祖父节点xpp的右子节点
;
0)变色操作
若x的祖父节点xpp的左子节点xppl并在并且是红色,直接交换祖父节点和其子节点的颜色;
1、2)右旋 变色 左旋操作
(1)步骤一:将树节点右旋到同一侧;
(2)步骤二:父节点和祖父节点变色,以祖父节点xpp为轴左旋;
4、rotateLeft()
左旋操作是将待旋转节点p的和其右子节点r交换位置和所有的节点关联关系,具体如下:
1、令当前旋转节点
p的右子节点
为其原右子节点r的左子节点rl
(右儿子节点中的 左孙子节点);rl节点的parent节点为p;2、先令r的parent指向p的parent,然后再判断p节点的父节点pp的情况:
1)pp为空时,设置r为root节点,并将r的parent节点置为空;
2)p节点是父节点pp的左子节点时,pp的的左子节点变更为r;
3)p节点是父节点pp的右子节点时,pp的的右子节点变更为r;
3、最后将r的left指向p,p的parent指向r;
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl; // r为p的右子节点,pp为p的父节点,rl为r的左子节点
// 如果p的右节点不为空
if (p != null && (r = p.right) != null) {
// rl赋值,并将p.right指向r.left
if ((rl = p.right = r.left) != null)
// rl的父节点为p
rl.parent = p;
// 1)当p节点没有父节点时,先令r的父节点为p的父节点
if ((pp = r.parent = p.parent) == null)
// 把p节点的右子节点r变为黑色,并作为root节点
(root = r).red = false;
// 2)p节点在其父节点pp的左子节点
else if (pp.left == p)
// 令pp节点的左子节点为r
pp.left = r;
// 3)p节点在其父节点的右子节点
else
// 令pp节点的右子节点为r
pp.right = r;
// 令r的左子节点为p
r.left = p;
// p的父节点为r
p.parent = r;
}
return root;
}
结合源代码图解分析:
1)左旋操作的最终态:
2)细化每种情况
5、rotateRight()
右旋操作和左旋类似,只是左变右、右变左;本质上逻辑都是一样的;
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr; // l为p的左子节点,pp为p的父节点,lr为l的右子节点
// 如果p的左节点不为空
if (p != null && (l = p.left) != null) {
// rl赋值,并将p.left指向r.right
if ((lr = p.left = l.right) != null)
// 设置lr的父节点为p
lr.parent = p;
// 1)将l的parent指向p的parent,如果p的父节点pp为空
if ((pp = l.parent = p.parent) == null)
// 将的l的颜色设置为黑色,并作为根节点root
(root = l).red = false;
// 2)p节点在其父节点pp的右子节点
else if (pp.right == p)
// 令pp节点的右子节点为l
pp.right = l;
// 3)p节点在其父节点pp的左子节点
else
// pp节点的左子节点为l
pp.left = l;
// 令l的右子节点为p
l.right = p;
// p的父节点为l
p.parent = l;
}
return root;
}
结合源代码图解分析:
既然左旋的大家已经看懂了,右旋大家可以尝试一下自己画个图呀;锻炼一下自己的动手能力;
6、moveRootToFront()
在treeify()
方法中调用balanceInsertion()
对红黑树平衡完之后,最后会进入moveRootToFront()
方法,将root节点放到整条双向链表的头部,并插⼊到table数组中。
注意这里说的双向链表是红黑树中的TreeNode
。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 判断table数组中存储的元素是不是最新的root节点
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 如果不是
if (root != first) {
// 重塑双向链表的连接,把root放到整个链表的头位置,并将root插入到table数组中
// A <--> root <--> C 变为 root <--> A <--> C
Node<K,V> rn; // rn表示root的下一个节点
tab[index] = root;
TreeNode<K,V> rp = root.prev; // rp表示root的前一个节点
if ((rn = root.next) != null)
// rn的prev节点修改为rp
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
// rp的next节点修改为rn
rp.next = rn;
if (first != null)
// 把root节点移动到first节点之前
first.prev = root;
root.next = first;
// root的前一个节点置为空
root.prev = null;
}
// 对整个红黑树结构执行check校验
assert checkInvariants(root);
}
}
重塑双向链表的连接,把root放到整个链表的头位置,并将root插入到table数组中;
将A <–> root(B) <–> C 变为 root(B) <–> A <–> C。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfijfj
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01