hashmap转红黑树的两个条件

2023-11-02

一个是链表长度到8(实际是要超过8,后面有补充说明),一个是数组长度到64.

上图所示是判断链表长度到达8调用treeifyBin方法转换红黑树,TREEIFY_THRESHOLD的值为8 ,TREEIFY_THRESHOLD-1=7,所以binCount >=7时调用treeifyBin方法

上图所示是treeifyBin的方法代码,开头有判断数组长度是否小于64,小于则进行扩容,否则转红黑树.MIN_TREEIFY_CAPACITY的值为64.

补充:转红黑树链表长度是要超过8不是达到8,根据 凯_天 的评论提供的补充:

1.测试代码可以看 凯_天  评论

2.当binCount=0,put的第2个元素,binCount 1对应put的第3个元素,1对以此类推,当binCount=7时此时put的是第9个元素,而上面的已经说了binCount >=7时调用treeifyBin方法,所以链表长度是要超过8

2.详细的解释可以看下面代码的注释

/*HaskMap putVal 源码 put ele1,ele2...ele8,ele9*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
    //2.当put第二个元素ele2时,p == tab[i] 即p=ele1 != null所以走else
	if ((p = tab[i = (n - 1) & hash]) == null)
        //1.当put第一个元素ele1的时候走这个地方,tab[i] =ele1
		tab[i] = newNode(hash, key, value, null);
	else {
		Node<K,V> e; K k;
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
             //3.从put第二个元素ele2的时候才开始走以下代码
			for (int binCount = 0; ; ++binCount) {
                //4.p每次都是从ele1元素开始,可以看序号2的注释
                //5.当binCount=0的时候p=ele1,此时如果p.next==null时让p.next=ele2并判断(binCount >= TREEIFY_THRESHOLD - 1)是否满足,满足则触发转红黑树,当前put的值是ele2.
                //6.而如果p.next不是null则赋值p=ele2,进行下一次循环binCount++及当binCount=1的时候p=ele2,此时赋值p.next=ele3,当前put的是ele3
                //7.综上所诉,binCount 0对应2,1对应3,以此类推7对应9
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
                    //8.TREEIFY_THRESHOLD - 1 = 7
                    //9.所以当binCount = 7的时候触发转红黑数,此时put的是ele9,所以是超过8转红黑树
					if (binCount >= TREEIFY_THRESHOLD - 1)
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		.....后面代码省略
}

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

hashmap转红黑树的两个条件 的相关文章

  • 为什么Java中的Set数据结构内部使用Map?

    我想知道为什么HashSet http www docjar com html api java util HashSet java html uses HashMap TreeSet uses TreeMap and LinkedHash
  • 如何对 HashMap 键进行排序[重复]

    这个问题在这里已经有答案了 我有一个问题 HashMap
  • 二和 Leetcode 解释、Hashmap、Javascript

    我只是想知道谁能一步一步解释这个解决方案的算法 我不知道哈希图是如何工作的 您能否还提供一个使用哈希图的基本示例 以便我理解该算法 谢谢你 var twoSum function nums target let hash for let i
  • 以 null 为键的 HashMap

    How HashMap内部区分null and 0作为关键 按照这个post https stackoverflow com questions 17268212 hashcode for null key in hashmap的哈希码nu
  • java hashmaps 的 get() 函数

    我声明了以下哈希图 HashMap
  • 为什么 Map.of 不允许空键和空值?

    在 Java 9 中 引入了新的工厂方法List Set and Map接口 这些方法允许使用一行中的值快速实例化 Map 对象 现在 如果我们考虑 Map
  • 地图中的最大元素数

    GO 中的 Map 最多可以存储多少个元素 如果我需要经常从 Map 访问数据 那么在长时间运行的程序中不断向 Map 添加项目并从中检索项目是一个好主意吗 除了map length类型的最大值之外 map中的元素数量没有理论上的限制 in
  • Java 中的 ConcurrentHashMap 和 Hashtable [重复]

    这个问题在这里已经有答案了 Java 中的 ConcurrentHashMap 和 Hashtable 有什么区别 哪个对于线程应用程序更有效 ConcurrentHashMap 和 Hashtable 锁定机制 Hashtable属于Co
  • Java 弱哈希映射 - 需要根据值的弱点而不是键来删除条目

    所以JavaWeakHashMap让我们创建一个映射 如果其键变弱 则删除该映射的条目 但是我怎样才能创建一个Map 当它的条目被删除时values地图上变弱了 我想使用映射的原因是作为全局哈希表 它根据对象的 ID 跟踪对象 ID gt
  • HashSet如何不允许重复?

    我正在经历add的方法HashSet 值得一提的是 如果该集合已包含该元素 则调用将保持该集合不变并返回 false But the add方法在内部保存值HashMap public boolean add E e return map
  • hashmap包含键的复杂度

    我写了一个方法来查找列表中的重复项 它工作正常 但我担心使用 containsKey 的复杂性 当我们使用 containsKey 时 我们必须为每个键计算一个哈希函数 然后将每个键与我们的搜索项进行比较 对吗 那么复杂度不是 O n 吗
  • JQuery $.ajax() 在 java servlet 中发布数据

    我想将数据发送到 java servlet 进行处理 数据将具有可变长度并采用键 值对 A1984 1 A9873 5 A1674 2 A8724 1 A3574 3 A1165 5 数据不需要这样格式化 这就是我现在的方式 var sav
  • 如何将列表转换为地图?

    最近我和一位同事讨论了转换的最佳方式是什么List to Map在 Java 中 这样做是否有任何具体的好处 我想知道最佳的转换方法 如果有人可以指导我 我将非常感激 这是个好方法吗 List
  • 如果计算的哈希码超过整数最大限制,会发生什么?

    这是 Java HashTable 类的 hashCode 实现 如果哈希表中的元素数量很大并且哈希码超过 INTEGER MAX LIMIT 2 147 483 648 到 2 147 483 647 该怎么办 我假设 hashCodes
  • 如何在 Java 中访问嵌套的 HashMap?

    我有一个 Java 中的 HashMap 其中的内容 你们可能都知道 可以通过以下方式访问 HashMap get keyname 如果一个 HashMap 位于另一个 HashMap 中 即嵌套的 HashMap 我将如何访问内容 我可以
  • 为什么 HashMap.clear() 中不再使用 Arrays.fill() ?

    我注意到执行中有些奇怪的事情HashMap clear 这就是它的样子OpenJDK 7u40 http grepcode com file repository grepcode com java root jdk openjdk 7u4
  • 哈希桶数量

    In the HashMap http docs oracle com javase 7 docs api java util HashMap html文档中提到 the 初始容量只是创建哈希表时的容量 the capacity是哈希表中的
  • 如何在Java中创建关联列表?

    我正在尝试让用户输入String在列表中搜索值 这工作正常 但我也想要String具有数值 这样我就可以得到清单价格中的某些商品 我试过 public List
  • 在 Java 中存储国家/地区代码、名称和大陆的最佳方式

    我想要一个List or Array某种形式 存储有关每个国家的信息 2个字母的代码 国家名称 例如巴西 世界各大洲 地区 如东欧 北美等 我将手动将每个国家 地区划分为地区 大陆 但如果存在自动执行此操作的方法 请告诉我 这个问题是关于如
  • 从 ArrayList HashMap 中获取多个随机值

    我想从 ArrayList 中获取一些特定数字的随机值 final ArrayList

随机推荐

  • 2023年第十五届华中杯赛题C 题 空气质量预测与预警

    2023年五一假期期间 数学建模竞赛就有四场 各种比赛各种需求应接不暇 因此 对于本次浅析有不足的地方欢迎大家指出 为了更好的帮助大家华中杯参赛 下面带来 C题详细版思路 由于C题的难度 注定选题人数将不可计数 因此对于每一问求解已经不再是
  • Unity 串口接收的报文不完整?处理方式在这

    Unity 串口通讯接收完整报文并处理 串口通讯 Read 函数的处理 解决问题的过程 对Read 函数的应用 弊端 结束 串口通讯 Unity 中的串口通讯和C 的处理方式基本一致 Serial Read 可以读取缓存区中的十六进制数 S
  • Mybatis - 常用 SQL 语句设计思路及具体实现 - 数据存在则更新,不存在则插入、批量更新、批量插入、连表查询 + - 字段加减法

    目录 序言 一 数据存在则更新 不存在则插入 ON DUPLICATE KEY UPDATE 的具体 xml 用法 虽然有点问题 但没准以后有用到的时候 on duplicate key update 用法总结 二 批量更新 方法 一 方法
  • 数组里的对象去重

    今天分享的是数组对象去重的方式 先看看数组对象的形式 let arrObj name 小红 id 1 name 小橙 id 1 name 小黄 id 4 name 小绿 id 3 name 小青 id 1 name 小蓝 id 4 下面是我
  • [人工智能-深度学习-26]:卷积神经网络CNN - 为啥要卷积神经网络以及卷积神经网络的应用

    作者主页 文火冰糖的硅基工坊 文火冰糖 王文兵 的博客 文火冰糖的硅基工坊 CSDN博客 本文网址 https blog csdn net HiWangWenBing article details 120805258 目录 第1章 全连接
  • c语言动态内存管理

    在C语言中 有几个动态内存管理的函数 分别是malloc calloc realloc和free free free函数用于释放由malloc calloc或realloc函数分配的内存空间 它接受一个指向要释放的内存的指针作为参数 注意
  • 在kali linux里利用SQLmap实现SQL注入

    SQLMap简介 SQLMap 是一个自动化的SQL注入工具 其主要功能是扫描 发现并利用给定URL的SQL注入漏洞 内置了很多绕过插件 支持的数据库是MySQL Oracle PostgreSQL Microsoft SQL Server
  • 第五阶段学习测试

    逐梦 一 单选题 1 下列各项中 执行流程正确的是 A InputFormat Mapper Reducer OutputFormat B Mapper InputFormat Reducer OutputFormat C InputFor
  • 《动手学深度学习 Pytorch版》 6.6 卷积神经网络

    import torch from torch import nn from d2l import torch as d2l 6 6 1 LeNet LetNet 5 由两个部分组成 卷积编码器 由两个卷积核组成 全连接层稠密块 由三个全连
  • Docker存储卷(Volume)

    简介 想要了解Docker Volume 首先我们需要知道Docker的文件系统是如何工作的 Docker镜像是由多个文件系统 只读层 叠加而成 当我们启动一个容器的时候 Docker会加载只读镜像层并在其上镜像栈顶部添加一个读写层 如果运
  • RTP如何打包H264数据

    拿到H264的裸流数据是 一般码流结构是SPS PPS I帧 P帧 SPS PPS I帧 P帧 用RTP打包H264数据时 SPS和PPS可以不发 直接发I帧和P帧数据即可 还要看I帧和P帧有多大 如果小于MTU就直接加RTP包发送就可以
  • 关于Unity任何版本点击Play运行就黑屏,除了摄像机窗口其他全部黑掉的问题解决~

    问题如图所示 这个问题一般人很少遇到 我却遇见了N次 每次重装都是这样从5 0到5 4 0版本都是如此 几乎崩溃 咨询很多人都一脸茫然 重装系统 重装软件 更新版本 都不行 后来 偶然间 我这样解决了问题 1 打开Unity 点击Edit
  • 【从零开始学c++】————模板初阶

    模板初阶 一 模板函数 1 模板函数的概念 2 模板的匹配原则 二 类模板 1 类模板的定义格式 2 类模板的实例化 一 模板函数 如何实现一个通用的的两个数相加的函数呢 我们可以通过函数重载把各个类型的两个数相加给写出来 如下 int A
  • python+requests+pytest 接口自动化框架(八)

    今日内容 接口自动化测试框架封装之数据类型处理以及DDT数据驱动封装 一 数据类型处理 read extract data tag id 替换成 110 json tag id read extract data tag id 二 DDT数
  • 解决 error: style attribute '@android:attr/windowEnterAnimation' not found.

    在Project gradle properties中添加 android enableAapt2 false
  • 5.3.4 因特网的路由协议(四)BGP协议

    5 3 4 因特网的路由协议 四 BGP协议 我们学习的RIP协议 5 3 2 因特网的路由协议 二 基于距离向量算法的RIP协议 和OSPF协议 5 3 3 因特网的路由协议 三 OSPF协议 都是内部网关协议 都是只能作用于一个自治系统
  • 【原创】xenomai UDD介绍与UDD用户态驱动示例

    xenomai UDD与用户态驱动示例 本文介绍xenomai UDD原理和相关代码 并给出一个基于UDD的用户态操作GPIO的示例 以及内核收发网络包与用户态操作网卡收发包的CPU耗时对比 版权声明 本文为本文为博主原创文章 转载请注明出
  • Web.xml配置详解

    1 定义头和根元素 部署描述符文件就像所有XML文件一样 必须以一个XML头开始 这个头声明可以使用的XML版本并给出文件的字符编码 DOCYTPE声明必须立即出现在此头之后 这个声明告诉服务器适用的servlet规范的版本 如2 2或2
  • 浏览器中地址框输入url地址会进行什么操作?

    一 http请求流程 http 超文本传输协议 是基于TCP协议之上的应用层协议 http的请求会进行以下操作 一 http请求流程 1 1 url域名解析成ip地址 dns解析 1 2 建立三次握手TCP连接 1 2 1 报文中SYN S
  • hashmap转红黑树的两个条件

    一个是链表长度到8 实际是要超过8 后面有补充说明 一个是数组长度到64 上图所示是判断链表长度到达8调用treeifyBin方法转换红黑树 TREEIFY THRESHOLD的值为8 TREEIFY THRESHOLD 1 7 所以bin