java——HashSet底层机制——链表扩容和树化
HashSet在Java中是基于HashMap实现的,它实际上是将所有元素作为HashMap的key存储,而value则统一使用一个静态的Object对象(Present)作为占位符。
1.举例演示
下面我们就举例说明一下,HashSet集合中,一个节点上的链表添加数据以及树化的过程。
1.代码准备
首先我们写一个类A,用类A的对象作为放到集合中的数据。这里,我们还重写了hashCode()方法,我们知道,HashSet集合在执行add()方法添加数据时会计算其hash值,根据hash值分配在集合中的节点位置。所以我们重写了hashCode()方法,使类A的每一个对象计算的hash值都相同,都分配到同一结点,从而观察同一个节点中链表的增加。
然后,创建一个HashSet集合hashSet,
写一个for循环,循环往集合里加入A类的对象 new A(i)
为每个对象的属性n赋值i,因为每次循环的i不同,所以每个对象的属性不同,避免它们equals,无法添加
准备过程就结束了,接着我们开始debug调试
所用代码
//演示一下 一个结点的单链表的增加和表的树化import java.util.HashSet;public class HashSet_03 {public static void main(String[] args) {HashSet hashSet = new HashSet();for (int i = 1; i < 12; i++) {hashSet.add(new A(i));//向hashSet里添加A的对象,并且每个对象的属性不同,避免它们equals,无法添加//链表长度超过8后,table长度没超过64时,table长度翻倍,再往链表里添加,再翻倍,// 达到64后,再添加,table 转化为红黑树}}
}
class A{int n;public A(int n){this.n = n;}//为了让他们能添加到同一个链表,需要保证他们的hash值相同//重写Object类的hash计算方法@Overridepublic int hashCode() {return 100;//使其返回定值}
}
2.调试操作
设置
由于设置不同,调试界面可能不同,这里是本文的设置,大家可以参考
操作
在for语句上创建断点,右键开始调试,每点击两次步进,是添加一次数据
添加完第一个数据后,可以看到hashSet下面出现了一个table表,点开可以看到,当前tabel有16个节点(0-15),第一个数据被添加到了索引为4的位置。
再执行两次步进,点开4下面的next,可以看到第二个元素被添加到了4的next位置
同理,添加第三个元素,可以看到第三个元素被添加到了第二个元素的next位置
以此类推,一直添加到第八个元素,
因为前面我们重写了hashCode(),使其固定返回一个值,所以所有数据的hash值都相同,自然都被分配到了4的位置,在这个结点上形成了单链表!现在已经有八个元素了
现在,table的长度依然是当初创建时初始化的16,
我们知道,HashSet集合红红黑树化的条件是,单个链表长度超过8,而且,table长度超过64
树化条件
-
链表长度阈值:当链表长度达到8时
-
数组容量阈值:同时当前HashMap的数组(table)长度必须达到64
此时单个链表长度已经是8了,我们再执行两次步进,添加第九个元素,看看会怎样?
如下图,我们添加了第九个元素,而table的长度变成了32!!!!!
翻了一倍,第九个元素又添加到了第八个元素的next位置。
我们继续添加第十个元素!
于是,table的长度又翻了一倍,变成了64(0-63)!
所有的元素也从4号结点转移到了36号结点(这是由hash值计算位置的算法导致的,不是重点)
这时
树化条件
-
链表长度阈值:当链表长度达到8时(已经满足)
-
数组容量阈值:同时当前HashMap的数组(table)长度必须达到64(已经达到64)
于是我们再添加第十一个数据,见证它的树化!
如下图,这个位置由Node变为了TreeNode!
结点下面的属性也变成了树节点的属性!
树化成功!
2.总结,树化的条件和过程
树化条件
-
链表长度阈值:当链表长度达到8时
-
数组容量阈值:同时当前HashMap的数组(table)长度必须达到64
如果链表长度达到8但数组长度不足64,HashMap会优先进行扩容(resize)而不是树化。
树化过程
-
链表转树:当满足上述两个条件时,HashMap会将链表转换为红黑树
-
遍历链表节点,创建对应的TreeNode节点
-
按照红黑树的规则构建树结构
-
-
树退化为链表:
-
当树节点数减少到6时,红黑树会退化为链表
-
这个阈值(6)比树化阈值(8)小,避免了频繁的树化和退化
-
源码分析
// HashMap中的树化相关代码
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果数组为空或长度小于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 {// 将普通Node转换为TreeNodeTreeNode<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)// 将TreeNode链表转换为红黑树hd.treeify(tab);}
}
为什么需要树化
Java 8引入树化机制主要是为了解决哈希冲突严重时链表过长导致的性能下降问题:
-
链表查找时间复杂度:O(n)
-
红黑树查找时间复杂度:O(log n)
当哈希函数设计不佳或恶意攻击导致大量元素落入同一个桶时,树化能保证较好的性能。
相关文章:
java——HashSet底层机制——链表扩容和树化
HashSet在Java中是基于HashMap实现的,它实际上是将所有元素作为HashMap的key存储,而value则统一使用一个静态的Object对象(Present)作为占位符。 1.举例演示 下面我们就举例说明一下,HashSet集合中,一个节点上的链表添加数据以及…...
玩转Docker | 使用Docker搭建Blog微博系统
玩转Docker | 使用Docker搭建Blog微博系统 前言一、Blog介绍项目简介主要特点二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署Blog服务下载镜像创建容器检查容器状态设置权限检查服务端口安全设置四、访问Blog系统访问Blog首页登录Blog五、总结前言 在数字…...
Linux中的Vim与Nano编辑器命令详解
📢 友情提示: 本文由银河易创AI(https://ai.eaigx.com)平台gpt-4-turbo模型辅助创作完成,旨在提供灵感参考与技术分享,文中代码与命令建议通过官方渠道验证。 在Linux系统中,文本编辑是最常用的…...
G1垃圾回收器介绍
G1垃圾回收器简介 全称:Garbage-First Garbage Collector。目的:G1垃圾回收器是为了替代CMS垃圾回收器而设计的,它旨在提供更好的垃圾回收性能和可预测性,特别是在处理大内存堆时。特点:G1是一种服务器端的垃圾回收器…...
Python学习笔记(三)
文章目录 Python函数详解基本概念定义函数函数调用参数类型1. 位置参数2. 默认参数3. 关键字参数4. 可变参数 返回值函数作用函数中的变量作用域规则 递归函数Lambda函数函数注解装饰器文档字符串其他重要概念闭包生成器函数高阶函数 Python函数详解 基本概念 函数是Python中…...
Hqst的超薄千兆变压器HM82409S在Unitree宇树Go2智能机器狗的应用
本期拆解带来的是宇树科技推出的Go2智能机器狗,这款机器狗采用狗身体形态,前端设有激光雷达,摄像头和照明灯。在腿部设有12个铝合金精密关节电机,并配有足端力传感器,通过关节运动模拟狗的运动,并可做出多种…...
TaskFlow开发日记 #1 - 原生JS实现智能Todo组件
一、项目亮点 - 📌 **零依赖实现**:纯原生JavaScript CSS3 - 📌 **数据持久化**:LocalStorage自动同步 - 📌 **交互优化**:收藏置顶 动态统计 - 📌 **响应式设计**:完美适配移动端…...
es的告警信息
Elasticsearch(ES)是一个开源的分布式搜索和分析引擎,在运行过程中可能会产生多种告警信息,以提示用户系统中存在的潜在问题或异常情况。以下是一些常见的 ES 告警信息及其含义和处理方法: 集群健康状态告警 信息示例…...
vue实现在线进制转换
vue实现在线进制转换 主要功能包括: 1.支持2-36进制之间的转换。 2.支持整数和浮点数的转换。 3.输入验证(虽然可能存在不严格的情况)。 4.错误提示。 5.结果展示,包括大写字母。 6.用户友好的界面,包括下拉菜单、输…...
责任链设计模式(单例+多例)
目录 1. 单例责任链 2. 多例责任链 核心区别对比 实际应用场景 单例实现 多例实现 初始化 初始化责任链 执行测试方法 欢迎关注我的博客!26届java选手,一起加油💘💦👨🎓😄😂 最近在…...
Matlab 分数阶PID控制永磁同步电机
1、内容简介 Matlab 203-分数阶PID控制永磁同步电机 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略...
Java中LocalDateTime类
Java中的日期类 Date类LocalDateTime类创建LocalDateTime对象1 获取当前时间2 获取自己指定时间3 字符串创建日期 获取当前日期的信息1获取当前日期的年月日 时分秒2 获取当前日期周几\当年第几天\当月第几天3 获取当前⽇期所在周的周⽇和周⼀ 日期的运算1日期加减天数2 日期加…...
【C语言】--- 文件操作
文件操作 1. 为什么要使用文件2. 什么是文件2.1 程序文件2.2 数据文件2.3 文件名 3. 二进程文件和文本文件4. 文件的打开和关闭4.1 流和标准流4.1.1流4.2.2标准流 4.2 文件指针4.3 打开和关闭操作 5. 文件的顺序读写5.1 文件顺序读写函数5.1.1 fgetc 和 fputc5.1.2 fgets 和 fg…...
操作系统 4.4-从生磁盘到文件
文件介绍 操作系统中对磁盘使用的第三层抽象——文件。这一层抽象建立在盘块(block)和文件(file)之间,使得用户可以以更直观和易于理解的方式与磁盘交互,而无需直接处理磁盘的物理细节如扇区(se…...
第六章 进阶03 外包测试亮相
因为有年度重点项目,团队缺少测试资源,所以临时招聘了一个外包测试(后文用J代指),让产品经理亮亮来带她。 到今天J差不多入职有1个月时间了,亮亮组了个会,一起评审下J做的测试用例。 J展示了其…...
如何使用通义灵码完成PHP单元测试 - AI辅助开发教程
一、引言 在软件开发过程中,测试是至关重要的一环。然而,在传统开发中,测试常常被忽略或草草处理,很多时候并非开发人员故意为之,而是缺乏相应的测试思路和方法,不知道如何设计测试用例。随着 AI 技术的飞…...
使用 nano 文本编辑器修改 ~/.bashrc 文件与一些快捷键
目录 使用 nano 编辑器保存并关闭文件使用 sed 命令直接修改文件验证更改 如果你正在使用 nano 文本编辑器来修改 ~/.bashrc 文件,以下是保存并关闭文件的具体步骤: 使用 nano 编辑器保存并关闭文件 打开 ~/.bashrc 文件 在终端中运行以下命令…...
计算机组成原理——CPU与存储器连接例题
计算机组成原理——CPU与存储器连接例题 设CPU共有16根地址线和8根数据线,并用(MREQ) ̅作为访存控制信号(低电平有效),(WR) ̅作为读/写命令信号(高电平读,低电平写)。现有下列存储芯片&#…...
SQL 外键(Foreign Key)详细讲解
1. 什么是外键? 定义:外键是数据库表中的一列(或一组列),用于建立两个表之间的关联关系。外键的值必须匹配另一个表的主键(Primary Key)或唯一约束(Unique Con…...
B3647 【模板】Floyd
题目链接:点击进入 题目 思路 代码 #include <bits/stdc.h> #define inf 0x3f3f3f3f using namespace std; const int maxn 1e6 10;int n,m,g[110][5000];int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;memse…...
配置镜像端口和观察接口
top: 在G0/0/2上抓包通过其他端口ping pc4 可以看到 Wireshark 抓包没有任何反应,做个镜像端口并配置(观察接口和镜像接口) observe-port interface g0/0/2 #命令配置观察端口mirror to observe-port both …...
爬虫解决debbugger之替换文件
鼠鼠上次做一个网站的时候,遇到的debbugger问题,是通过打断点然后编辑断点解决的,现在鼠鼠又学会了一个新的技能 首先需要大家下载一个reres的插件,这里最好用谷歌浏览器 先请大家看看案例国家水质自动综合监管平台 这里我们只…...
erlang的安装-linux
1:解压 tar -zxvf 安装包 2:进入解压的目录执行: ./configure --prefix/usr/local/erlang --with-ssl --enable-threads --enable-smp-support --enable-kernel-poll --enable-hipe --without-javac 3:编译安装: m…...
Android Coil 3默认P3色域图加载/显示不出来
Android Coil 3默认P3色域图加载/显示不出来 解决,需要在Androidmanifest.xml使用Coil 3的activity配置属性: <activityandroid:colorMode"wideColorGamut"...</activity>...
【LaTeX】安装
Register - Overleaf, 在线LaTeX编辑器 注册Overleaf 安装 Latex2022 安装教程(附安装资源)_tex2022安装教程-CSDN博客 注:先安装 texlive,再安装TexStudio \documentclass{article} % 这里是导言区 \begin{document}Hello, wor…...
【2025年认证杯数学中国数学建模网络挑战赛】A题 解题建模过程与模型代码(基于matlab)
目录 【2025年认证杯数学建模挑战赛】A题解题建模过程与模型代码(基于matlab)A题 小行星轨迹预测解题思路第一问模型与求解第二问模型与求解 【2025年认证杯数学建模挑战赛】A题 解题建模过程与模型代码(基于matlab) A题 小行星轨…...
【KWDB 创作者计划】KWDB 数据库全维度解析手册
——从原理到实践,构建下一代数据基础设施 第一章:KWDB 设计哲学与技术全景 1.1 为什么需要 KWDB? 在数据爆炸与业务场景碎片化的今天,传统数据库面临三大挑战:扩展性瓶颈(单机性能天花板ÿ…...
低代码开发能否取代后端?深度剖析与展望-优雅草卓伊凡
低代码开发能否取代后端?深度剖析与展望-优雅草卓伊凡 在科技迅猛发展的当下,软件开发领域新思潮与新技术不断涌现,引发行业内外热烈探讨。近日,笔者收到这样一个颇具争议的问题:“低代码开发能取代后端吗?…...
LeetCode hot 100—最长回文子串
题目 给你一个字符串 s,找到 s 中最长的 回文 子串。 示例 示例 1: 输入:s "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。示例 2: 输入:s "cb…...
蓝桥杯知识总结
文章目录 1.常用的数学方法2.大小写转换3.数组和集合排序数组排序集合排序 4.控制小数位数5.栈6.队列7.字符串相关方法8.十进制转n进制模板字符转为十进制某进制转化为十进制 9.前缀和10.差分11.离散化12.双指针13.二分14.枚举模板组合型枚举模板排列型枚举模板 15.搜索算法BFS…...
leetcode:2839. 判断通过操作能否让字符串相等 I(python3解法)
难度:简单 给你两个字符串 s1 和 s2 ,两个字符串的长度都为 4 ,且只包含 小写 英文字母。 你可以对两个字符串中的 任意一个 执行以下操作 任意 次: 选择两个下标 i 和 j 且满足 j - i 2 ,然后 交换 这个字符串中两个…...
Python Lambda表达式详解
Python Lambda表达式详解 1. Lambda是什么? Lambda是Python中用于创建匿名函数(没有名字的函数)的关键字,核心特点是简洁。它适用于需要临时定义简单函数的场景,或直接作为参数传递给高阶函数(如map()、f…...
Matlab 平衡车的建模与控制
1、内容简介 Matlab 189-平衡车的建模与控制 可以交流、咨询、答疑 2、内容说明 略 平衡车的建模与控制 选择一款平衡车(如:小米九号平衡车等),并估计平衡车的关键参数。完成以下工作: 1. 建立平衡车模型…...
KWDB创作者计划—KWDB关系库与时序库混搭
📢📢📢📣📣📣 作者:IT邦德 中国DBA联盟(ACDU)成员,10余年DBA工作经验 Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主,全网粉丝10万 擅长主流Oracle、MySQL、PG、高斯…...
Android studio2024的第一个安卓项目
目录 一、创建项目 1、创建Empty Views Activity类型项目 2、Android项目结构解析 manifests 目录: Gradle Scripts目录 3、创建安卓应用 二、测试 1、模拟器测试效果 2、连接真机,然后直接选择真机运行即可(点击Run或Shift F10运行…...
航电系统之障碍物监测技术篇
航电系统的障碍物监测技术是保障飞行安全、提升飞行效率的核心技术之一,尤其在复杂环境和低空飞行中发挥着关键作用。以下从技术原理、传感器类型、数据处理与应用等方面进行系统介绍: 一、技术原理 航电系统的障碍物监测技术通过多传感器融合和智能算法…...
网站DDoS防护方案——构建企业级安全屏障的关键路径
本文深度解析DDoS攻击最新演变趋势与防御技术体系,通过攻击特征图谱、云原生防护架构、混合防御模型等维度,揭示企业级网站防护方案的设计逻辑。结合2023年金融行业千万级QPS攻击事件,引用Gartner最新防御技术成熟度曲线,给出可落…...
Linux系统使用lshw生成硬件报告方法
使用 lshw 生成 HTML 硬件报告指南 一、工具简介 lshw(List Hardware)是 Linux 系统下用于检测并报告硬件详细信息的命令行工具,支持输出多种格式(文本、HTML、XML 等)。 核心功能: 显示 CPU、内存、磁盘、PCI/USB 设备等完整硬件信息生成结构化报告,便于存档或分析支…...
力扣 905 按奇偶排序数组:双指针法的优雅实现
目录 问题背景 题目解析 解题思路 暴力解法 双指针法 代码实现 代码解析 算法效率 实际应用场景 总结 问题背景 在编程的世界里,数组排序问题一直是经典中的经典。今天我们要解决的是一个有趣的变种:按奇偶排序数组。题目要求我们将一个整数数…...
LeetCode hot 100—子集
题目 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 示例 1: 输入:nums [1,2,3] 输出:[[],[1],[2…...
BERT - BertTokenizer, BertModel API模型微调
本节代码将展示如何在预训练的BERT模型基础上进行微调,以适应特定的下游任务。 ⭐学习建议直接看文章最后的需复现代码,不懂得地方再回看 微调是自然语言处理中常见的方法,通过在预训练模型的基础上添加额外的层,并在特定任务的…...
通过代码获取接口文档工具
通过代码获取接口文档工具 介绍使用到的技术使用说明核心源码演示截图工具源码 介绍 1.通过前后端代码来生成规格化的接口文档 2.支持拖拽上传或点击选择文件,可以一次选择多个文件或选择文件夹 3.用户选择前后端代码,工具调用GPT解析,得到规…...
不再卡顿!如何根据使用需求挑选合适的电脑内存?
电脑运行内存多大合适?在选购或升级电脑时,除了关注处理器的速度、硬盘的容量之外,内存(RAM)的大小也是决定电脑性能的一个重要因素。但究竟电脑运行内存多大才合适呢?这篇文章将帮助你理解不同使用场景下适…...
leetcode589 N叉树的前序遍历
前序遍历的顺序是:根节点 -> 子节点1 -> 子节点2 -> ... -> 子节点N 递归: class Solution { private:void traverse(Node* cur, vector<int>& res){if(cur NULL) return;res.push_back(cur->val);for(Node* child: cur->…...
游戏引擎学习第216天
回顾并为当天做准备 你可以看到,游戏现在正在运行。如果我没记错的话,我们之前把调试系统关闭了,留下一个状态,让任何想要在这段时间内进行实验的人可以自由操作,因为我们还没有完全完成这个系统。所以这样做是为了确…...
JavaSE反射机制干货
1.反射(Relection) 理解 定义:程序运行状态,动态地获取程序信息及调用程序功能即为java反射机制 2.获取class对象 掌握 2.1 Java代码的3个阶段 Java代码在计算机中经历的三个阶段:Source源代码阶段-Class类对象阶段-Runt…...
[特殊字符] 第十一讲 | 空间回归模型实战:SAR / SEM / GWR逐个击破
📘 专栏:科研统计方法实战分享 | 地学/农学人的数据分析工具箱 ✍️ 作者:平常心0715 🔑 本讲关键词:空间滞后模型(SAR)、空间误差模型(SEM)、地理加权回归(G…...
AI前沿周报:2025年3月技术深度解析
以下是基于2024-2025年AI技术前沿动态的深度技术周报示例,结合行业最新突破与研究进展,突出技术原理与应用场景分析: AI前沿周报:2025年3月技术深度解析 时间范围:2025年3月1日-3月31日 本期焦点:模型透明…...
aidigu开源微博项目程序,PHP开发的开源微博系统,自媒体个人创业、网盘推广首先
一、软件介绍 文末提供程序和源码下载学习 PHP开发的开源微博系统,采用PHP MySQL开发,框架采用ThinkPHP5.1,用户登录后拥有专属ID,支持表情、关注用户,网盘分享等功能,支持图片上传,视频上传,网盘存储分享…...
Tabnet介绍(Decision Manifolds)和PyTorch TabNet之TabNetRegressor
Tabnet介绍(Decision Manifolds)和PyTorch TabNet之TabNetRegressor Decision ManifoldsTabNet1.核心思想2. 架构组成3. 工作流程4. 优点PyTorch TabNetTabNetRegressor参数1. 模型相关参数`n_d``n_a``n_steps``gamma``cat_idxs``cat_dims``cat_emb_dim`2. 训练相关参数`opti…...