jdk1.8 HashMap红黑树插入修正源码分析

2024-05-09 16:38

本文主要是介绍jdk1.8 HashMap红黑树插入修正源码分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这里是目录

  • 预备知识点
    • 红黑树
    • 红黑树的插入策略
    • 红黑树的插入新节点后的5种情况
    • 红黑树的插入修正的4种方式
  • 源码分析

预备知识点

进入代码分析之前简要介绍相关知识点,推荐一个视频,讲得很好:

  • youtube:https://www.youtube.com/watch?v=5IBxA-bZZH8
  • bilibili:https://www.bilibili.com/video/av14050857

红黑树

红黑树是一种平衡二叉树,除了二叉搜索树的基本特征外还有以下特征:

  • 所有节点分红黑两色
  • 根节点和空叶子为黑色
  • 不能出现相连红色节点
  • 从根节点到任意叶子节点的路径上具有相同数量的黑色节点

红黑树的插入策略

分两步:

  • 插入一个红色节点(红色需要修正的概率更小)
  • 通过变色和旋转来修正修正违反上述规则之处

红黑树的插入新节点后的5种情况

其中一种没有违反任何规则,无须修正:

  • 插入节点的父节点为黑色

插入新节点后的树可能不符合红黑树的定义,需要修正。红黑树的插入修正分4种情况:

  1. 插入的节点为根节点
  2. 插入节点的叔叔节点为红色
  3. 插入节点的叔叔节点为黑色(三角式)
    Z为插入节点,ZAB不在一条线上
  4. 插入节点的叔叔节点为黑色(直线式)
    Z为插入节点,ZAB在一条线上
    所谓插入节点既可以是新插入的节点,也可以是经过其他修正方式产生的新的红色节点的子红色节点

红黑树的插入修正的4种方式

4种方式对应上述4中情况:

  1. 将插入节点变为黑色,修正完成。
  2. 将插入节点的父节点、叔叔节点变成黑色,祖父节点变成红色。将祖父节点作为新的插入节点(可能需要继续修正)。
  3. 将插入节点的父节点进行旋转(方向为插入节点的反方向,例如插入节点为左子节点则右旋),转换为情况4。
  4. 将插入节点的父节点变黑,祖父节点变红,祖父节点进行旋转(方向为插入节点的反方向,例如插入节点为左子节点则右旋),修正完成。

源码分析

源码摘自JDK1.8 java.util.HashMap.java 2219行

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {// 插入节点为红色x.red = true;for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {// 如果没有父节点,说明已经是根节点,染成黑色,修正完成(可能是插入了根节点,也可能是经过情况1的修正后)if ((xp = x.parent) == null) {x.red = false;return x;}// 如果父节点是黑色(无须修正的情况) 或者 不存在祖父节点(什么时候会走这个条件,还没搞懂,有懂的请指教)else if (!xp.red || (xpp = xp.parent) == null)return root;// 父节点是祖父节点的左孩子if (xp == (xppl = xpp.left)) {// 情况1if ((xppr = xpp.right) != null && xppr.red) {// 叔叔节点改成黑色xppr.red = false;// 父节点改成黑色xp.red = false;// 祖父节点改成红色xpp.red = true;// 插入节点指向祖父节点x = xpp;}else {// 情况3(插入节点是右孩子,插入节点的父亲是祖父的左孩子)if (x == xp.right) {// 插入节点是右孩子,所以左旋root = rotateLeft(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}// 情况4if (xp != null) {// 父节点变黑xp.red = false;// 为什么要判空呢?理论上不可能有空的时候。// x只会代表一个红色节点(新插入的节点必然红色,否则方法已退出)// x的父节点一定是红色(如果是黑色,方法已经退出)// x一定有祖父节点(因为父节点一定是红色,那么红色节点一定有父节点,否则原来就不是红黑树)// 这里的疑问,有懂的欢迎留言解答下if (xpp != null) {// 祖父节点变红xpp.red = true;// 插入节点是左孩子(本来就是左或者经过上面的情况4处理变成左),右旋root = rotateRight(root, xpp);}}}}else {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);}}}}}}

这篇关于jdk1.8 HashMap红黑树插入修正源码分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/973926

相关文章

Redis主从/哨兵机制原理分析

《Redis主从/哨兵机制原理分析》本文介绍了Redis的主从复制和哨兵机制,主从复制实现了数据的热备份和负载均衡,而哨兵机制可以监控Redis集群,实现自动故障转移,哨兵机制通过监控、下线、选举和故... 目录一、主从复制1.1 什么是主从复制1.2 主从复制的作用1.3 主从复制原理1.3.1 全量复制

Redis主从复制的原理分析

《Redis主从复制的原理分析》Redis主从复制通过将数据镜像到多个从节点,实现高可用性和扩展性,主从复制包括初次全量同步和增量同步两个阶段,为优化复制性能,可以采用AOF持久化、调整复制超时时间、... 目录Redis主从复制的原理主从复制概述配置主从复制数据同步过程复制一致性与延迟故障转移机制监控与维

Redis连接失败:客户端IP不在白名单中的问题分析与解决方案

《Redis连接失败:客户端IP不在白名单中的问题分析与解决方案》在现代分布式系统中,Redis作为一种高性能的内存数据库,被广泛应用于缓存、消息队列、会话存储等场景,然而,在实际使用过程中,我们可能... 目录一、问题背景二、错误分析1. 错误信息解读2. 根本原因三、解决方案1. 将客户端IP添加到Re

Java汇编源码如何查看环境搭建

《Java汇编源码如何查看环境搭建》:本文主要介绍如何在IntelliJIDEA开发环境中搭建字节码和汇编环境,以便更好地进行代码调优和JVM学习,首先,介绍了如何配置IntelliJIDEA以方... 目录一、简介二、在IDEA开发环境中搭建汇编环境2.1 在IDEA中搭建字节码查看环境2.1.1 搭建步

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时,Tenda和锐捷都是备受关注的品牌,各自有独特的产品特点和市场定位,选择哪个品牌的路由器更合适,实际上取决于你的具体需求和使用场景,我们从... 在选购路由器时,锐捷和腾达都是市场上备受关注的品牌,但它们的定位和特点却有所不同。锐捷更偏向企业级和专

Spring中Bean有关NullPointerException异常的原因分析

《Spring中Bean有关NullPointerException异常的原因分析》在Spring中使用@Autowired注解注入的bean不能在静态上下文中访问,否则会导致NullPointerE... 目录Spring中Bean有关NullPointerException异常的原因问题描述解决方案总结

python中的与时间相关的模块应用场景分析

《python中的与时间相关的模块应用场景分析》本文介绍了Python中与时间相关的几个重要模块:`time`、`datetime`、`calendar`、`timeit`、`pytz`和`dateu... 目录1. time 模块2. datetime 模块3. calendar 模块4. timeit

python-nmap实现python利用nmap进行扫描分析

《python-nmap实现python利用nmap进行扫描分析》Nmap是一个非常用的网络/端口扫描工具,如果想将nmap集成进你的工具里,可以使用python-nmap这个python库,它提供了... 目录前言python-nmap的基本使用PortScanner扫描PortScannerAsync异

Oracle数据库执行计划的查看与分析技巧

《Oracle数据库执行计划的查看与分析技巧》在Oracle数据库中,执行计划能够帮助我们深入了解SQL语句在数据库内部的执行细节,进而优化查询性能、提升系统效率,执行计划是Oracle数据库优化器为... 目录一、什么是执行计划二、查看执行计划的方法(一)使用 EXPLAIN PLAN 命令(二)通过 S