HashMap 链表与红黑树转换

article/2025/6/9 15:54:39

链表转换为红黑树

                //此处遍历链表for (int binCount = 0; ; ++binCount) {//遍历到链表最后一个节点if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//如果链表元素个数大于等于TREEIFY_THRESHOLDif (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;}
    static final int MIN_TREEIFY_CAPACITY = 64;static final int UNTREEIFY_THRESHOLD = 6;/*** Replaces all linked nodes in bin at index for given hash unless* table is too small, in which case resizes instead.*/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();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}

可以看到在treeifyBin中并不是简单地将链表转换为红黑树,而是先判断table的长度是否大于64,如果小于64,就通过扩容的方式来解决,避免红黑树结构化.
个人觉得链表长度大于8有两种情况:

  • table长度足够,hash冲突过多
  • table长度太小,但是在计算table下标的时候,导致很多hash不一致的key计算的下标一致

所以扩容后链表长度变短,读写效率自然提高。另外,扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。并不是链表长度超过8就一定会转换成红黑树,而是先尝试扩容。

红黑树转换为链表

基本思想是当红黑树中的元素减少并小于一定数量时,会切换回链表。

而元素减少有两种情况:

  • 调用map的remove方法删除元素
  • resize的时候,对红黑树进行了拆分

1、hashMap的remove方法,会进入到removeNode方法,找到要删除的节点,并判断node类型是否为treeNode,然后进入删除红黑树节点逻辑的removeTreeNode方法中,该方法有关解除红黑树结构的分支如下

 //判断是否要解除红黑树的条件
if (root == null || root.right == null ||(rl = root.left) == null || rl.left == null) {tab[index] = first.untreeify(map);  // too smallreturn;}

此时是通过红黑树根节点及其子节点是否为空来判断,而满足该条件的最大红黑树结构如下:
在这里插入图片描述
节点数为10,大于 UNTREEIFY_THRESHOLD(6),但是根据该方法的逻辑判断,是需要转换为链表的

2、resize的时候,判断节点类型,如果是链表,则将链表拆分,如果是TreeNode,则执行TreeNode的split方法分割红黑树,而split方法中将红黑树转换为链表的分支如下

//在这之前的逻辑是将红黑树每个节点的hash和一个bit进行&运算,
//根据运算结果将树划分为两棵红黑树,lc表示其中一棵树的节点数
if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map);else {tab[index] = loHead;if (hiHead != null) // (else is already treeified)loHead.treeify(tab);}

这里才用到了 UNTREEIFY_THRESHOLD 的判断,当红黑树节点元素小于等于6时,才调用untreeify方法转换回链表

总结
1、hashMap并不是在链表元素个数大于8就一定会转换为红黑树,而是先考虑扩容,扩容达到默认限制后才转换
2、hashMap的红黑树不一定小于6的时候才会转换为链表,而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。


http://chatgpt.dhexx.cn/article/7gdVJ4t4.shtml

相关文章

为什么要有红黑树?什么是红黑树?

为什么要有红黑树 想必大家对二叉树搜索树都不陌生&#xff0c;首先看一下二叉搜索树的定义&#xff1a;二叉搜索树&#xff08;Binary Search Tree&#xff09;&#xff0c;或者是一棵空树&#xff0c;或者是具有下列性质的二叉树&#xff1a; 若它的左子树不空&#xff0c;则…

HashMap与红黑树

一、为什么需要HashMap? 在我们写程序的时候经常会遇到数据检索等操作&#xff0c;对于几百个数据的小程序而言&#xff0c;数据的存储方式或是检索策略没有太大影响&#xff0c;但对于大数据&#xff0c;效率就会差很远。 1、线性检索&#xff1a; 线性检索是最为直白的方法…

数据结构:什么是红黑树?为什么要用红黑树?

本篇主要谈谈对红黑树的理解&#xff0c;大家都晓得JDK8中的hashmap底层是数组链表红黑树实现的&#xff0c;当面试官问你&#xff1a;为啥要加上红黑树实现呢&#xff1f;&#xff1f; 那我们首先从概念来了解一下&#xff1a; 一、什么是红黑树&#xff1f; 红黑树是一个接…

随处可见的红黑树详解

随处可见的红黑树详解 前言为什么要有红黑树二叉搜索树平衡二叉搜索树红黑树 红黑树的应用场景红黑树的性质&#xff08;重点&#xff09;红黑树的定义红黑树的左旋与右旋红黑树插入结点与插入维护红黑树的三种情况插入结点插入结点后维护红黑树父结点是爷结点是左子树1. 叔结点…

HashMap-链表与红黑树转换触发条件

JDK1.8对HashMap进行了很多优化。 例如当一个槽位slot上的链表个数过多时&#xff0c;则会将链表转换为红黑树&#xff0c;以提高查询检索的效率。 访问节点方式&#xff1a;先找到节点所在的数组index索引位置&#xff0c;然后判断节点是什么结构进行遍历。 节点结构是非树…

9.HashMap里的红黑树是什么

1. 简介 红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树&#xff08;AVL树&#xff09;&#xff0c;因此&#xff0c;红黑树在很多地方都有应用。在C STL中&#xff0c;很多部分(目前包括set, multiset, map,multimap)应用了红黑树的变体(SGI STL中的红黑树有一…

算法:什么是红黑树

红黑树的定义 红黑树的英文是“Red-Black Tree”&#xff0c;简称 R-B Tree。它是一种不严格的平衡二叉查找树。顾名思义&#xff0c;红黑树中的节点&#xff0c;一类被标记为黑色&#xff0c;一类被标记为红色。除此之外&#xff0c;一棵红黑树还需要满足这样几个要求&#x…

pygraphviz的安装与红黑树可视化

大家好&#xff0c;我是小小明&#xff0c;今天我将带大家安装pygraphviz&#xff0c;并通过它对红黑树这种数据结构进行可视化。 pygraphviz的安装与红黑树的可视化 安装graphviz 下载地址&#xff1a;http://www.graphviz.org/download/ windows平台下可以选择&#xff1…

到底什么是红黑树?

到底什么是红黑树&#xff1f; 首先&#xff0c;可以这么简单粗暴的理解&#xff0c;红黑树≈平衡的二叉排序树。 那么很显然&#xff0c;要想弄懂红黑树&#xff0c;得先明白什么是树、二叉树、二叉排序树、平衡树以及不平衡树。下面我们一个个来了解。 1.第一个问题&#x…

面试常问:什么是红黑树?

什么是红黑树&#xff1f; ———————————— 二叉查找树&#xff08;BST&#xff09;具备什么特性呢&#xff1f; 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下图…

红黑树简介

一、什么是红黑树 红黑树&#xff08;Red Black Tree&#xff09; 是一种自平衡二叉查找树&#xff0c;是在计算机科学中用到的一种数据结构&#xff0c;典型的用途是实现关联数组。 红黑树是在1972年由Rudolf Bayer发明的&#xff0c;当时被称为平衡二叉B树&#xff08;symme…

什么是红黑树?

一、红黑树的产生 1.二叉树 定义&#xff1a;二叉树&#xff08;binary tree&#xff09;是指树中节点的度不大于2的有序树&#xff0c;它是一种最简单且最重要的树。二叉树的递归定义为&#xff1a;二叉树是一棵空树&#xff0c;或者是一棵由一个根节点和两棵互不相交的&…

说说什么是红黑树?

分析&回答 红黑树介绍 R-B Tree&#xff0c;全称是Red-Black Tree&#xff0c;又称为“红黑树”&#xff0c;红黑树就是一种平衡的二叉查找树&#xff0c;说他平衡的意思是他不会变成“瘸子”&#xff0c;左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外&#xf…

漫画:什么是红黑树?(整合版)

前段时间&#xff0c;小灰发布了红黑树相关的文章&#xff0c;分成上下篇来讲解。 这一次&#xff0c;小灰把两篇文章做了整合&#xff0c;并且修正了红黑树删除部分的图片错误&#xff0c;感谢大家的指正。 ————— 第二天 ————— ———————————— 二叉查找…

抗性基因数据库CARD介绍

随着抗生素药物的发现及使用&#xff0c;越来越多的耐药菌株由此产生。而耐药菌株的发展则会增加疾病治疗的难度和成本&#xff0c;因此耐药微生物的研究则显得尤为重要。目前&#xff0c;通过对耐药基因的鉴定挖掘能够一定程度上帮助我们揭开耐药机制&#xff0c;为疾病的治疗…

关于 GIL

目录 GIL是什么GIL产生的原因如何避免受到GIL的影响什么时候会释放GIL锁互斥锁和Gil锁的关系 参考链接 python中的GIL详解 python面试不得不知道的点——GIL 《Python面试每日一题》之GIL Python GIL 是功能和性能之间权衡后的产物&#xff0c;它尤其存在的合理性&#xff0…

gin介绍

Gin的介绍与应用 Gin是一个golang的web框架&#xff0c;Gin像是一些常用函数或者工具的集合。具有快速灵活&#xff0c;容错方便等特点。Gin自身的net/http足够简单&#xff0c;性能也非常不错。 Gin的官网&#xff1a;https://github.com/gin-gonic/gin 安装前保证git和go都安…

gin_gorm

一、使用形式 1、引入gorm包 import "github.com/jinzhu/gorm" 2、导入数据库驱动 import _ "github.com/go-sql-driver/mysql"为了方便记住导入路径&#xff0c;GORM包装了一些驱动&#xff1a; import _ "github.com/jinzhu/gorm/dialects/mysq…

【GIC】配置GIC

本章介绍如何在裸机环境中启用和配置兼容GICv3的中断控制器。 目录 一、全局设置 二、单独PE设置 2.1 Redistributor配置 2.2 CPU接口配置 2.3 PE配置 三、SPI, PPI, SGI配置 3.1设置SPI的目标PE 附&#xff1a;寄存器介绍 附1&#xff1a;GICD_CTLR 附2&#xff1a;…