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转红黑树的两个条件 的相关文章

  • Android 使用包含另一个 hashmap 的 hashmap 实现 Parcelable 对象

    这是一个扩展Android 实现具有 hashmap 的 Parcelable 对象 https stackoverflow com questions 22498746 android implement parcelable objec
  • 我们可以将嵌套映射作为其他映射中的键吗?

    我刚刚开始用 Java 实现数据结构 想知道我们是否可以遇到这样的情况 Map
  • HashMap 分组依据 (Java)

    有没有一种方法可以在Java中按Key分组并将值添加到HashMap中 HashMap
  • 奇怪的 Java HashMap 行为 - 找不到匹配的对象

    当我试图在里面寻找钥匙时 我遇到了一些奇怪的行为java util HashMap 我想我错过了一些东西 代码段基本上是 HashMap
  • 根据键名从 HashMap 获取字符串值

    我有一个HashMap有各种键和值 我怎样才能得到一个值 我在地图上有一把钥匙叫my code 它应该包含一个字符串 我怎样才能得到它而不必遍历地图 到目前为止我已经 HashMap newMap new HashMap paramMap
  • 当客户端读取 HashMap 时如何刷新 HashMap

    我有一个静电HashMap在服务器启动时初始化 客户端在登录时从该地图初始化其数据 现在我需要刷新这张地图 但是客户端可以同时登录并从这张地图中获取数据 当他们阅读时 我可以更改如下所示的地图参考吗 我不能使用synchronized因为它
  • HashMap 可串行化

    HashMap实现了Serialized接口 所以可以序列化 我查看了 HashMap 的实现 并且 Entry 表被标记为瞬态 由于Entry 表是存储Map全部内容的表 如果不能序列化 那么反序列化时Map是如何构造回来的 如果你看来源
  • Guava 地图中的驱逐惰性

    当前的地图驱逐算法相当懒惰 看起来过期的对象只有在访问数据结构时才会被驱逐 例如 从地址到索引器的映射定义为 ConcurrentMap
  • Java中如何从HashMap中获取对象

    我试图在给定密钥时从 HashMap 获取测试对象的速度 但我不太确定该怎么做 我尝试过这种方式 但它是错误的 hash values getSpeed 有什么帮助吗 谢谢 class Test private String id priv
  • Ruby - 将数组映射到哈希图

    我有一个数组和一个返回给定值的函数 最终我想创建一个哈希映射 将数组的值作为键值 将 f key value 的结果作为值 是否有一种干净 简单的方法 例如类似于数组的each map 使用块来执行此操作 所以相当于 hsh 1 2 3 4
  • 以 null 为键的 HashMap

    How HashMap内部区分null and 0作为关键 按照这个post https stackoverflow com questions 17268212 hashcode for null key in hashmap的哈希码nu
  • Java HashMap - 深拷贝

    我只是想找出如何进行深层复制的最佳解决方案HashMap 该映射中没有对象实现Cloneable 我想找到比序列化和反序列化更好的解决方案 看一眼深度克隆 在 Google Code 上您可以找到一个库 你可以阅读它https github
  • Java 中的 HashMap 和 Map 对象有什么区别?

    我创建的以下地图之间有什么区别 在另一个问题中 人们似乎可以互换使用它们来回答 我想知道它们是否 如何不同 HashMap
  • Map:为 Integer 和 Double 类型定义方法,但不为 String 类型定义方法

    我正在尝试定义一个方法putIfGreaterThan 为了我的新Map class 给定一个键 仅当新值大于旧值时 它才会用新值替换旧值 我知道我可以通过组合来实现这一点 通过有一个private final Map
  • Java中HashMap和ArrayList的区别?

    在爪哇 ArrayList and HashMap被用作集合 但我不明白我们应该在哪些情况下使用ArrayList以及使用时间HashMap 他们两者之间的主要区别是什么 您具体询问的是 ArrayList 和 HashMap 但我认为要完
  • Hashmap 不适用于 int、char [重复]

    这个问题在这里已经有答案了 可能的重复 在 Java 集合中存储原始值 https stackoverflow com questions 2504959 storing primitive values in a java collect
  • 如何制作具有两个索引的 Map?

    我在java中有一张这样的地图 Map
  • 添加到 HashMap 中的列表的快捷方式

    我经常需要获取一个对象列表 并根据对象中包含的值将它们分组到一个 Map 中 例如 按国家 地区获取用户和组列表 我的代码通常如下所示 Map
  • Struts 2 - s:使用Map选择

    在 struts 2 中 我想使用从 Map 填充的 s select 我的地图有这样的值 键1 值1 键2 值2 键是我想要发布的内容 确实如此 但它显示了值 我不想显示这些值 但从我在其他方法 如 s text getTranslati
  • 从 HashMap 条目列表中删除重复项

    我有一个List

随机推荐

  • 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