当前位置: 首页 > news >正文

Hashmap链表长度大于8真的会变成红黑树吗?

1、本人博客《HashMap、HashSet底层原理分析》
2、本人博客《若debug时显示的Hashmap没有table、size等元素时,查看第19条》

结论

1、链表长度大于8时(插入第9条时),会触发树化(treeifyBin)方法,但是不一定会树化,若数组大小小于64时,则会先扩容。
2、假设扩容后该链表重新计算Hash后还是放在同一个数组下标时,则会出现链表长度大于8时,未树化的情况。

jdk8源码(treeifyBin)

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// MIN_TREEIFY_CAPACITY = 64// 链表长度小于64时会优先扩容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);}
}

测试源码(大于8时,未树化)

import java.util.HashMap;
import java.util.Objects;public class HashmapTest {public static void main(String[] args) {HashMap<User,User> hashMap = new HashMap<>();// 同一链表插入8条for (int i = 0; i < 8; i++) {hashMap.put(new User("张三", 18),new User("张三", i));}// 插入第九条,链表长度大于8,会进入treeifyBin树化方法,但是未树化,会执行扩容方法// 默认数组大小16扩容到32// 链表长度变成了9个Node节点,并非红黑树hashMap.put(new User("张三", 18),new User("张三", 9));// 插入第10条,链表长度大于8,会进入treeifyBin树化方法,但是未树化,会执行扩容方法// 数组大小由32扩容到了64// 链表长度变成了10个Node节点,并非红黑树hashMap.put(new User("张三", 18),new User("张三", 10));// 插入第十一条时树化// 数组容量还是64未触发扩容// 链表变成红黑树,节点由Node变成TreeNodehashMap.put(new User("张三", 18),new User("张三", 11));}
}// 重写hashCode方法,保证值一样是hashcode是一样的,可以使值一样的对象出现在同一链表上
class User{private String name;private int age;public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public User(String name, int age) {this.name = name;this.age = age;}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int hashCode() {return Objects.hash(name, age);}
}

插入第九条时的Hashmap
插入第十条时结果是一样的,只是数组扩容到了64
1、数组长度扩容到了32
2、Hashmap中保存了9个数据,均在同一条链表
3、节点为Node节点,并不是treenode(红黑树)
在这里插入图片描述
插入第十一条时的Hashmap
1、数组大小为64
2、节点变成了treenode(红黑树)
在这里插入图片描述

测试源码(大于8时,树化)

初始化Hashmap时,直接大于等于64,则同一个链表插入第九条时直接执行了树化。
treeifyBin方法中只有数组长度小于64时才会执行扩容方法,否则则是树化

// 初始化大小,其他同上,插入第九条时,节点就变成了treenode
HashMap<User,User> hashMap = new HashMap<>(64);

插入第九条时的Hashmap
1、数组大小为64
2、节点变成了treenode(红黑树)
在这里插入图片描述

相关文章:

Hashmap链表长度大于8真的会变成红黑树吗?

1、本人博客《HashMap、HashSet底层原理分析》 2、本人博客《若debug时显示的Hashmap没有table、size等元素时&#xff0c;查看第19条》 结论 1、链表长度大于8时(插入第9条时)&#xff0c;会触发树化(treeifyBin)方法&#xff0c;但是不一定会树化&#xff0c;若数组大小小于…...

关于接地:数字地、模拟地、信号地、交流地、直流地、屏蔽地、浮地

除了正确进行接地设计、安装,还要正确进行各种不同信号的接地处理。控制系统中&#xff0c;大致有以下几种地线&#xff1a; &#xff08;1&#xff09;数字地&#xff1a;也叫逻辑地&#xff0c;是各种开关量&#xff08;数字量&#xff09;信号的零电位。 &#xff08;2&am…...

排序

一、数据流中的中位数题目描述&#xff1a;如何得到一个数据流中的中位数&#xff1f;如果从数据流中读出奇数个数值&#xff0c;那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值&#xff0c;那么中位数就是所有数值排序之后中间两个数的平均值。…...

Android DataStore Proto存储接入流程详解与使用

一、介绍 通过前面的文字&#xff0c;我们已掌握了DataStore 的存储&#xff0c;但是留下一个尾巴&#xff0c;那就是Proto的接入。 Proto是什么&#xff1f; Protobuf&#xff0c;类似于json和xml&#xff0c;是一种序列化结构数据机制&#xff0c;可以用于数据通讯等场景&a…...

HiEV洞察 | 卖一台亏半台,激光雷达第一股禾赛隐忧仍在

作者 | 感知君Alex 编辑 | 王博2月9日晚&#xff0c;禾赛在万众瞩目下登陆纳斯达克&#xff0c;发行价19美元每股&#xff0c;首日涨超11%&#xff0c;市值超过Luminar&#xff0c;登顶全球市值最高的激光雷达公司。 随后两个交易日&#xff0c;其股价均有不同程度的涨幅&#…...

面试题61. 扑克牌中的顺子

题目 从若干副扑克牌中随机抽 5 张牌&#xff0c;判断是不是一个顺子&#xff0c;即这5张牌是不是连续的。2&#xff5e;10为数字本身&#xff0c;A为1&#xff0c;J为11&#xff0c;Q为12&#xff0c;K为13&#xff0c;而大、小王为 0 &#xff0c;可以看成任意数字。A 不能视…...

有特别有创意的网站设计案例

有人说 UI 设计师集艺术性与科学性于一身&#xff0c;不仅需要对工具的使用熟练&#xff0c;更需要对美术艺术有一定的基础了解。如果想要成为优秀的 UI 设计师是一个需要磨砺的过程&#xff0c;需要不断的学习和积累&#xff0c;多看多练多感受&#xff0c;其中对于优质的设计…...

Python基础-数据类型之列表

一、列表的定义 name ["小明", "小红", "笑笑"] 二、列表的使用 除了序列中的操作&#xff0c;列表还有一些其他的操作。 &#xff08;1&#xff09;不使用列表方法对列表进行修改 1&#xff1a;通过索引修改列表中的值 name ["Kit…...

Linux系统基本设置:网络设置(三种界面网络地址配置)

网络地址配置&#xff1a;图形界面配置、命令行界面配置、文本图形界面配置 命令行界面配置 查看网络命令&#xff1a; 想要知道你有多少网卡&#xff0c;都可以通过这两个命令来查看 手动设置网络参数&#xff0c;我们可以使用nmcli这个命令来设置&#xff0c;我们需要知道…...

MySQL(二):查询性能分析

文章目录一、使用explain进行分析二、如何优化数据的访问三、如何重构大查询一、使用explain进行分析 Explain 用来分析 SELECT 查询语句&#xff0c;开发人员可以通过分析 Explain 结果来优化查询语句。 比较重要的字段有&#xff1a; select_type : 查询类型&#xff0c;有…...

Java基础-类加载器

写在前面的话&#xff1a; 基础加强包含了&#xff1a; 反射&#xff0c;动态代理&#xff0c;类加载器&#xff0c;xml&#xff0c;注解&#xff0c;日志&#xff0c;单元测试等知识点 其中最难的是反射和动态代理&#xff0c;其他知识点都非常简单 由于B站P数限制&#xff0c…...

Python 使用pandas处理Excel —— 快递订单处理 数据匹配 邮费计算

问题背景 有表A&#xff0c;其数据如下 关键信息是邮寄地址和单号。 表B&#xff1a; 关键信息是运单号和重量 我们需要做的是&#xff0c;对于表A中的每一条数据&#xff0c;根据其单号&#xff0c;在表B中查找到对应的重量。 在表A中新增一列重量&#xff0c;将刚才查到的…...

【黑马SpringCloud(7)】分布式事务

分布式事务事务的ACID原则分布式事务理论基础CAP定理BASE理论Seataseata的部署seata的集成事务模式XA模式Seata的XA模型优缺点实现XA模式AT模式案例&#xff1a;AT模式更新数据脏写问题优缺点实现AT模式TCC模式流程分析Seata的TCC模型事务悬挂和空回滚实现TCC模式优缺点SAGA模式…...

百度地图API添加自定义标记解决单html文件跨域

百度地图API添加自定义标记解决单html文件跨域 因为要往百度地图上添加一些标注点&#xff0c;而且这些标注点要用自定义的图片&#xff0c;而且只能使用单html文件&#xff0c;不能使用服务器&#xff08;也别问为什么&#xff0c;就是这么个需求&#xff09;&#xff0c;做起…...

如何停止/重启/启动Redis服务

一、命令行直接启动/停止/重启redis 可以直接通过下面的命令启动/停止/重启redis /etc/init.d/redis-server start 启动redis服务 /etc/init.d/redis-server stop 停止redis服务 /etc/init.d/redis-server restart 重启redis服务1、启动redis服务…...

python 的selenium自动操控浏览器教程(2)

人生苦短&#xff0c;我用py 文章目录人生苦短&#xff0c;我用py关于部分网页无法找到元素的问题1方案1方案2关于部分网页无法找到元素的问题2解决方案被网站检查出来我们使用了selenium了怎么办&#xff1f;如何实现前进后退当使用py删除文件时报禁止访问怎么办怎么使用py实现…...

【Deformable Convolution】可变形卷积记录

every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 可变形卷积记录 1. 正文 预印版&#xff1a; Deformable Convolutional Networks v1 Deformable ConvNets v2: More Deformable, Better Results 发表版…...

Oracle-Mysql 函数转换

Oracle-Mysql 函数转换limit <> ROWNUMcast <> TO_NUMBERcast as signedcast as unsignedregexp a_\\d <> REGEXP_LIKEschema() <> SELECT USER FROM DUALinformation_schema.COLUMNS表 <> ALL_TAB_COLUMNS表unix_timestampfrom_unixtime <&g…...

【Kafka】一.认识Kafka

kafka是一个分布式消息队列。由 Scala 开发的高性能跨语言分布式消息队列&#xff0c;单机吞吐量可以到达 10w 级&#xff0c;消息延迟在 ms 级。具有高性能、持久化、多副本备份、横向扩展能力。 生产者往队列里写消息&#xff0c;消费者从队列里取消息进行业务逻辑。 一般在…...

Linux软件管理YUM

目录 yum配置文件 创建仓库 yum查询功能 yum安装与升级功能 yum删除功能 yum仓库产生的问题和解决之道 yum与dnf 网络源 YUM就是通过分析RPM的标头数据后&#xff0c;根据各软件的相关性制作出属性依赖时的解决方案&#xff0c;然后可以自动处理软件的依赖属性问题&…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

PydanticAI快速入门示例

参考链接&#xff1a;https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...

ffmpeg(三):处理原始数据命令

FFmpeg 可以直接处理原始音频和视频数据&#xff08;Raw PCM、YUV 等&#xff09;&#xff0c;常见场景包括&#xff1a; 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装&#xff08;如封装为 MP4、TS&#xff09; 处理原始 YUV 视频…...

LTR-381RGB-01RGB+环境光检测应用场景及客户类型主要有哪些?

RGB环境光检测 功能&#xff0c;在应用场景及客户类型&#xff1a; 1. 可应用的儿童玩具类型 (1) 智能互动玩具 功能&#xff1a;通过检测环境光或物体颜色触发互动&#xff08;如颜色识别积木、光感音乐盒&#xff09;。 客户参考&#xff1a; LEGO&#xff08;乐高&#x…...

Modbus转Ethernet IP深度解析:磨粉设备效率跃升的底层技术密码

在建材矿粉磨系统中&#xff0c;开疆智能Modbus转Ethernet IP网关KJ-EIP-101的应用案例是一个重要的技术革新。这个转换过程涉及到两种主要的通信协议&#xff1a;Modbus和Ethernet IP。Modbus是一种串行通信协议&#xff0c;广泛应用于工业控制系统中。它简单、易于部署和维护…...