Java高频面试之集合-10
hello啊,各位观众姥爷们!!!本baby今天来报道了!哈哈哈哈哈嗝🐶
面试官:详解红黑树?HashMap为什么不用二叉树/平衡树呢?
一、红黑树(Red-Black Tree)的核心特性
红黑树是一种 自平衡二叉搜索树,通过颜色标记和旋转规则确保树的高度平衡,从而保证操作效率。其核心规则如下:
- 节点颜色:每个节点为红色或黑色。
- 根节点:根必须是黑色。
- 叶子节点:所有叶子(NIL节点)均为黑色。
- 红色节点规则:红色节点的子节点必须为黑色(无连续红色节点)。
- 黑高一致:从任一节点到其所有叶子节点的路径包含相同数量的黑色节点(黑高相同)。
平衡性保障:
- 红黑树的最长路径不超过最短路径的2倍(通过规则4和5保证)。
- 树的高度
h ≤ 2log(n+1)
,确保查找、插入、删除操作的时间复杂度为 O(log n)。
二、红黑树的操作与调整
-
插入操作:
- 新节点初始为红色,插入后可能破坏红黑树规则。
- 通过 旋转(左旋/右旋) 和 颜色翻转 调整树结构。
- 调整策略包括:
- 叔节点为红色:颜色翻转(父、叔变黑,祖父变红)。
- 叔节点为黑色且形成“三角”结构:旋转后调整颜色。
-
删除操作:
- 删除节点后可能破坏黑高平衡。
- 通过旋转和颜色调整修复树结构,确保满足红黑树规则。
示例插入调整:
插入前(父节点为红,叔节点为红):B/ \R R/R(新节点)调整后(颜色翻转):R/ \B B/R
三、HashMap为何选择红黑树而非二叉树/AVL树?
1. 普通二叉搜索树(BST)的问题
- 退化风险:若数据有序插入(如递增序列),BST退化为链表,查找效率降至 O(n)。
- 不稳定性:无法保证动态操作后的平衡性,不适合高并发场景。
2. AVL树的局限性
AVL树是严格平衡的二叉搜索树(左右子树高度差 ≤1),但存在以下问题:
- 维护成本高:插入/删除时需频繁旋转(平均旋转次数高于红黑树)。
- 写性能差:对于频繁修改的场景(如HashMap的
put
/remove
),AVL树的严格平衡导致性能下降。
3. 红黑树的优势
- 平衡性与性能的折衷:
- 红黑树允许一定的“不平衡”(最长路径 ≤ 2倍最短路径),减少旋转次数。
- 插入/删除的调整复杂度为 O(1)(仅颜色翻转)或 O(log n)(旋转),整体性能优于AVL树。
- 更适合动态数据:
HashMap在哈希冲突时,链表可能频繁转换为树或退化,红黑树的动态调整效率更高。
4. HashMap的具体考量
- 冲突处理场景:
- 当链表长度 ≥8 且桶数组容量 ≥64 时,链表转为红黑树。
- 树节点数 ≤6 时退化为链表(避免小数据量下树的结构开销)。
- 综合性能:
- 红黑树在查找(O(log n))与修改(较少旋转)间取得平衡,适合HashMap的读写混合负载。
四、性能对比:红黑树 vs AVL树 vs 链表
指标 | 红黑树 | AVL树 | 链表 |
---|---|---|---|
查找速度 | O(log n) | O(log n)(更快,因更平衡) | O(n) |
插入/删除 | O(log n)(旋转次数少) | O(log n)(旋转次数多) | O(1)(头尾操作) |
平衡严格度 | 宽松(最长路径 ≤2倍最短) | 严格(高度差 ≤1) | 无平衡 |
适用场景 | 频繁修改的动态数据(如HashMap) | 静态数据或读多写少(如字典) | 数据量小或无序访问 |
五、红黑树在HashMap中的实现细节
-
树化条件:
- 链表长度 ≥8 且桶数组容量 ≥64(否则优先扩容)。
- 退化为链表的阈值:树节点数 ≤6。
-
树节点结构:
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // 父节点TreeNode<K,V> left; // 左子节点TreeNode<K,V> right; // 右子节点TreeNode<K,V> prev; // 前驱节点(用于快速退化为链表)boolean red; // 颜色标记 }
-
哈希分布优化:
- 通过
hashCode()
扰动函数减少哈希冲突。 - 扩容时拆分树节点,保持红黑树结构或退化为链表。
- 通过
🐮🐎
- 红黑树:以适度的平衡性换取插入/删除的高效性,适合动态数据场景。
- HashMap的选择:在哈希冲突严重时,红黑树提供比链表更高的查询效率,同时避免AVL树的写性能瓶颈。
- 设计哲学:权衡空间、时间与实现复杂度,红黑树是HashMap在高冲突场景下的最优解。
相关文章:
Java高频面试之集合-10
hello啊,各位观众姥爷们!!!本baby今天来报道了!哈哈哈哈哈嗝🐶 面试官:详解红黑树?HashMap为什么不用二叉树/平衡树呢? 一、红黑树(Red-Black Treeÿ…...
Keil 5 环境下STM32F4 HAL库版本MDK工程创建详细步骤(适合小白,附工程源码)
一、前期准备 1.安装好keil Keil(MDK) 5 软件安装教程-CSDN博客https://blog.csdn.net/qq_42748213/article/details/90485750 2.安装好STM32F4的芯片包 Keil5中STM32F4xx芯片包下载安装_stm32f4芯片包-CSDN博客https://blog.csdn.net/weixin_45783141/article/details/131…...
【微服务】Nacos 配置动态刷新(简易版)(附配置)
文章目录 1、实现方法2、配置依赖 yaml3、验证效果 1、实现方法 环境:Nacos、Java、SpringBoot等 主要是在boostrap.yaml中的data-id属性下配置refresh:true来实现动态更新 2、配置依赖 yaml 具体的版本参考官方的说明:官方版本说明 <!--读取boo…...
LabVIEW cRIO中CSV文件的读取
在LabVIEW cRIO中读取CSV文件,需通过文件传输、路径配置、数据解析等步骤实现。本文详细说明如何通过代码读取本地存储的CSV文件,并探讨直接通过对话框选择文件的可行性及替代方案。 一、CSV文件传输至cRIO本地存储 1. 使用NI MAX文件管理 步骤…...
双周报Vol.67: 模式匹配支持守卫、LLVM 后端发布、支持 Attribute 语法...多项核心技术更新!
2025-03-10 语言更新 模式匹配支持守卫(Pattern Guard) 模式守卫可以通过在模式后追加 if ... 的语法结构来指定。有模式守卫的分支只有在被模式匹配的值满足对应模式,并且模式守卫为真的情况下才会执行。如果模式守卫为假,则会…...
从青铜到王者:六大排序算法实战解析
前言 在编程的世界里,排序算法如同一颗璀璨的明珠,闪耀着智慧的光芒。它不仅是计算机科学的基础知识点,更是每一位程序员必备的技能。今天,就让我们一同走进排序算法的世界,深入探究冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序这六大经典算法的精髓所在,…...
011-base64
base64 编码 以下是C实现的Base64字符串加密算法及其原理说明,综合了多个技术文档的核心要点: 一、Base64编码原理 Base64是一种将二进制数据转换为ASCII字符的编码方式,核心原理基于 3字节转4字符 的转换规则: 分组规则&…...
汽车NVH诊断案例 | 纯电车急加速过大弯底盘异响
引言 失去发动机的掩蔽效应后,新能源电车的NVH问题,成为了困扰维修技师新难点。风噪、胎噪、电机高频啸叫等问题更容易车主识别,根源却难以被有效分辨。如何更精准且高效地识别电车NVH问题根源?今天分享的这个案例,内…...
springcloud gateway通过数据库获取路由信息
在 Spring Cloud Gateway 中结合 MyBatis 动态从数据库加载路由配置,可以实现灵活的路由管理。以下是详细实现步骤: 1. 数据库表设计 创建路由配置表 gateway_route: CREATE TABLE gateway_route (id varchar(50) NOT NULL COMMENT 路由唯一…...
QtDataVisualization使用
Qt Data Visualization 是一个开源的第三方库,它为Qt框架提供了高级的数据可视化功能。这个库允许开发者创建复杂的3D和2D图表,包括但不限于散点图、曲面图、条形图等。它基于Qt 3D模块,因此可以充分利用Qt 3D引擎的强大功能来呈现三维数据。…...
【Go每日一练】实现简单的控制台计算器
👻创作者:丶重明 👻创作时间:2025年3月7日 👻擅长领域:运维 目录 1.😶🌫️题目:简单的控制台计算器2.😶🌫️代码输出3.😶&#…...
TDengine 数据对接 EXCEL
简介 通过配置使用 ODBC 连接器,Excel 可以快速访问 TDengine 的数据。用户可以将标签数据、原始时序数据或按时间聚合后的时序数据从 TDengine 导入到 Excel,用以制作报表整个过程不需要任何代码编写过程。 前置条件 准备以下环境: TDen…...
1.8 双指针专题:四数之和
1.题目链接 18. 四数之和 - 力扣(LeetCode)18. 四数之和 - 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元…...
基于用户标签和协同过滤混合算法的商城推荐系统设计与实现
一、研究背景 随着电子商务的快速发展,用户面对海量商品时往往面临“信息过载”问题。传统的推荐算法(如协同过滤)在用户行为数据稀疏或新用户场景下存在冷启动、推荐多样性不足等缺陷。 现状与挑战: 协同过滤:依赖用…...
软件版本号设计
软件版本号的设计是软件开发中的重要环节,它不仅帮助开发团队管理代码,还能让用户清楚地了解软件的更新状态。以下是常见的版本号设计方法和最佳实践,供你参考: 1. 常见的版本号设计规范 语义化版本控制(Semantic Ver…...
ESMFold对决AlphaFold:蛋白质-肽相互作用预测的新进展
今天向大家介绍的这篇文章题目为:“Protein−Peptide Docking with ESMFold Language Model”,近期发表在JCTC上。 本文主要研究 ESMFold 语言模型在蛋白质-肽对接中的应用。通过探索多种对接策略,评估其在预测蛋白质-肽相互作用方面的性能&a…...
【项目】负载均衡式在线OJ
负载均衡式在线OJ 目录 负载均衡式在线OJ 1.项目介绍: 2.comm 2.1 log.hpp 日志等级 开放式日志 时间戳工具 2.2 util.hpp TimeUtil类 PathUtil类 FileUtil类 StringUtil类 3.Compile_server 3.1compile_run.hpp RemoveTempFile CodeToDesc Start 3.…...
Android启动速度优化
Android启动速度优化 一、应用启动基础知识 1.1 启动类型 Android应用的启动类型主要分为三种: 冷启动(Cold Start):应用进程不存在,系统需要创建新的进程,加载并启动应用。这是最耗时的启动方式。 温启动(Warm Start):应用进程存在,但Activity可能被销毁,需要重新创…...
python爬虫碰到IP被封的情况,如何解决?
在数据抓取和爬虫开发的实践中,Python作为一种功能强大且易于上手的编程语言,被广泛应用于网络数据的采集。然而,随着网络环境的日益复杂,爬虫活动也面临着越来越多的挑战,其中IP被封便是常见且棘手的问题。IP被封不仅…...
Web网页制作(静态网页):千年之恋
一、是用的PyCharm来写的代码 二、代码中所用到的知识点(无 js) 这段HTML代码展示了一个简单的注册页面,包含了多个HTML元素和CSS样式的应用。 这段HTML代码展示了一个典型的注册页面,包含了常见的HTML元素和表单控件。通过CSS样…...
mac安装mysql之后报错zsh: command not found: mysql !
在Mac上安装MySQL后,如果终端中找不到mysql命令,通常是 因为MySQL的命令行工具(如mysql客户端)没有被正确地添加到你的环境变量中。 检查 MySQL 是否已安装 ps -ef|grep mysql查看到路径在 /usr/local/mysql/bin 查看 .bash_pro…...
Spring Boot 启动失败:Failed to start bean ‘documentationPluginsBootstrapper’ 解决方案
文章目录 1. 问题描述 🎯2. 可能原因分析 🔍原因 1:SpringFox 版本与 Spring Boot 版本不兼容 ❌✅ 解决方案:添加兼容性配置(首选!!!!) 原因 2:S…...
Python Cookbook-3.16 查看汇率
任务 想周期性地(用 crontab 或者 Windows计划任务来运行某 Python 脚本)从 Web 获取数据,监视某两种货币之间的兑换比例,并在两者之间的汇率达到某个值时发送提醒邮件。 解决方案 这个任务和一系列的从 Web 获取数据的监控任务很类似,它们…...
Manus(一种AI代理或自动化工具)与DeepSeek(一种强大的语言模型或AI能力)结合使用任务自动化和智能决策
一、Manus与DeepSeek差异 十分好奇DeepSeek和Manus究竟谁更厉害些,DeepSeek是知识型大脑,Manus则是全能型执行者。即DeepSeek专注于语言处理、知识整合与专业文本生成。其核心优势在于海量参数支持的深度学习和知识推理能力,例如撰写论文、润…...
Redis存数据就像存钱:RDB定期存款 vs AOF实时记账
Redis持久化 ◆ 核心概念1. ◆ 持久化全景图2. ◆ 生产环境黄金法则 ◆ RDB深度优化1. ◆ 生产配置精要2. ◆ 高级触发场景3. ◆ 故障应急方案 ◆ AOF深度解析1. ◆ 7.0版本革命性改进2. ◆ 同步策略深度测试3. ◆ 重写过程优化 ◆ 混合持久化实战1. ◆ 配置示例2. ◆ 数据恢复…...
【从零开始学习计算机科学】编译原理(一)编译过程概述
【从零开始学习计算机科学】编译原理(一)编译过程概述 绪论编译过程概述词法分析语法分析代码优化代码生成其他功能编译器的前端和后端绪论 什么叫编译程序?为什么我们需要编译程序?编译程序就是一个程序,将便于人编写、阅读、维护的高级计算机语言所写作的源代码程序,翻…...
第十八:go 并发 goroutine
channel 可以让多个goroutine 之间实现通信 Add方法调用时机:必须在goroutine 启动之前调用Add方法来增加计数器的值。 如果在goroutine已经启动之后再调用Add,可能会导致Wait方法提前返回,因为计数器没有正确反映正在运行的goroutine的数量…...
基于QGIS的二次开发(四):矢量编辑与属性表操作
一、实验目的 本次实验续接上一次的实验内容,旨在通过设计与开发地理信息系统的过程,加深学生对地理信息系统的理解,并掌握相关的设计与开发技能,包括熟悉地理信息系统的设计与开发流程,加强对 MVC 软件设计模式的理解…...
AI日报 - 2025年3月13日
🌟 今日概览(60秒速览) ▎🤖 AGI突破 | Reka开源21B参数推理模型Flash 3,推出企业智能平台Nexus 🔬 模型采用RLOO方法结合模型与规则基础奖励,实现高效推理 ▎💼 商业动向 | Waymo在…...
lua C语言api学习1 编译第一个程序
本文开始进行lua C语言api的学习 1 简介 lua语言与C语言使用还是很紧密,以前我只是学习lua语言比较多,C语言api部分了解比较少,最近在学习tcc编译器的使用进一步学习一下lua C语言api的使用。 2 配置编译环境 首先需配置好tcc编译器环境[参考],再配置好lua源码路径[参考],新…...
【物联网-WIFI】
物联网-WIFI ■ ESP32-C3-模块简介■ ESP32-C3-■ ESP32-C3-■ WIFI-模组■ WIFI-■ WIFI- ■ ESP32-C3-模块简介 ■ ESP32-C3- ■ ESP32-C3- ■ WIFI-模组 ■ WIFI- ■ WIFI-...
在MATLAB中实现PID控制仿真
在MATLAB中实现PID控制仿真可以通过代码编程或Simulink图形化建模两种方式完成。以下是两种方法的详细操作步骤和示例: 方法1:使用MATLAB脚本编程(基于控制系统工具箱) 步骤1:定义被控对象的数学模型 假设被控对象是…...
C#实现本地Deepseek模型及其他模型的对话v1.4
前言 系 统:Window11 开发工具:Visual Studio 2022 相关技术:C# 、WPF .Net 8.0 1、C#实现本地AI聊天功能 WPFOllamaSharpe实现本地聊天功能,可以选择使用Deepseek 及其他模型。 新增根据聊天记录回复的功能。 优化了部分ViewModelÿ…...
用sphinx-doc整理文档#2
上一篇博客:用sphinx-doc整理文档 回头看,上一篇博客已经是18年的事情了。最近我又开始维护起18年的项目了。最近策划同事提了一些需求。我又改进了一波,所以有本文。 sphinx支持导出pdf sphinx本身是支持导出pdf的,命令如下&am…...
DBeaver部分操作指南(数据库连接,构造ERD图,格式化SQL)
详细步骤指导如何使用DBeaver来连接到数据库: 步骤 1: 下载并安装 DBeaver 如果还没有安装DBeaver,请访问DBeaver官网下载适合操作系统的版本,并按照指示完成安装。 步骤 2: 启动 DBeaver 安装完成后,启动DBeaver应用程序。 …...
十种处理权重矩阵的方法及数学公式
1. 权重归一化(Weight Normalization) 目的:通过分离权重向量的范数和方向来加速训练。公式:对于权重向量 w \mathbf{w} w,归一化后的权重 w ′ \mathbf{w} w′ 为: w ′ w ∥ w ∥ \mathbf{w} \frac{…...
姚安娜新剧瘦了一圈,《仁心俱乐部》急诊医生顾诗宜在线上岗
《仁心俱乐部》在芒果 TV 播出,湖南卫视金鹰独播剧场也随之播出,这一剧集受到了不少观众的关注。姚安娜在剧中饰演的急诊科医生顾诗宜,她为患者检查身体时动作娴熟,与患者沟通时展现出的耐心和专注,都展现出很高的专业…...
postgresql源码安装
步骤 1: 安装依赖 在开始之前,请确保您的系统上安装了编译 PostgreSQL 所需的依赖包。使用以下命令安装必要的软件包: 对于 Debian/Ubuntu 系统: sudo apt update sudo apt install build-essential libreadline-dev zlib1g-dev flex biso…...
【51单片机】程序实验15.DS18B20温度传感器
主要参考学习资料:B站【普中官方】51单片机手把手教学视频 开发资料下载链接:http://www.prechin.cn/gongsixinwen/208.html 单片机套装:普中STC51单片机开发板A4标准版套餐7 目录 DS18B20介绍主要特性内部结构控制时序初始化时序写时序读时序…...
Java 集合框架:数据管理的强大工具
Java集合框架:数据管理的强大工具 目录 Java集合框架:数据管理的强大工具引言一、Set集合1. 定义与特点2. 常用实现类 - HashSet创建方式常用方法遍历方式 二、Map集合1. 定义与特点2. 常用实现类 - HashMap创建方式常用方法遍历方式 三、List集合1. 定义…...
AIM-T500绝缘监测仪:实时监测,确保IT系统绝缘安全-安科瑞 蒋静
在现代工业生产中,电力系统的稳定性和安全性至关重要。电力系统的绝缘状况直接关系到设备的正常运行和人员的安全。为了确保IT配电系统(不接地系统)的绝缘状况始终处于好的状态,安科瑞电气股份有限公司推出了AIM-T500绝缘监测仪&a…...
css3-学习
css 特性 选择器 基础选择器 标签选择器 ID 选择器 类选择器 CSS 的优先级是什么? !important > 内联样式(style“”) > ID 选择器 > 类选择器 属性选择器 伪类 > 标签选择器 伪元素选择器。 层级选择器 foo bar 后代选择器,元素的…...
neo4j图数据库
neo4j图数据库 学习neo4j图数据库的使用 文章目录 neo4j图数据库[toc]1-核心知识点2-思路整理3-参考网址4-上手实操1-安装neo4j-docker2-要学习CQL语句3-解决cmake问题1-可能的原因及解决办法1. cmake 未正确安装或者版本不兼容2. 依赖库缺失3. 环境变量配置问题4. 网络问题 2-…...
go下的Prototype学习笔记
本博文讲解prototype的学习笔记,内容包含了syntax、option go_package、message、service进行讲解,举例了常见写法。 文章目录 1.syntax 声明语法版本2.package 给当前的proto分配包名称3.option4.message4.1 切片数组4.2 map4.3 类型嵌套 5. 消息定义 …...
[高阶技术了解]WebRPC详解
“webrpc详解”,我需要根据我搜索到的资料来回答这个问题。首先,得弄清楚webrpc到底是什么。根据,Webrpc是一个模式驱动的后端服务开发工具,允许通过RIDL或JSON模式文件生成代码,支持多种语言如Go、TypeScript等。它类…...
地基注解@Controller和@RestController区别
前记:基础啊,区别点重点理解; 在Spring和Spring Boot框架中,Controller和RestController都用于处理HTTP请求,但它们在设计目的和用法上有显著区别。以下是它们的核心区别及示例说明: 1. 核心区别 特性C…...
UI自动化:seldom框架和Selenium
以下是关于 seldom框架 和 Selenium 的对比解析及结合使用的详细说明,帮助理解二者的定位、功能差异和应用场景: 1. 核心定位 工具定位Selenium浏览器自动化工具库,提供直接操控浏览器的底层API(如点击、输入、获取元素等&#x…...
机器学习项目实战——信用评分与贷款风险评估(主页有源码)
✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 1. 领域介绍 信用评分与贷款风险评估是金融领域中的一个重要应用场景。随着金融科技的快速发展,银行、信用卡公司、P2P…...
使用 OptiSLang 和 MotorCAD 构建一个强大的电机优化元模型
介绍 在本文中,我们将检查这些敏感性分析的结果,并构建一个健壮的元模型,作为优化过程的基础。 本文涵盖: 解释敏感性分析结果了解元模型及其在优化中的重要性构建和完善最佳预后模型 (MOP)使用预后系数…...
【科研绘图系列】python绘制分组点图(grouped dot plot)
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍加载R包数据下载导入数据函数`generateRectBoxDF` 函数主要作用参数解释逻辑流程`nmfDotPlot` 函数主要作用参数解释逻辑流程画图1画图2画图3画图4介绍 【科研绘图系列】python绘制…...