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

Java基础系列-HashMap源码解析1-BST树

news 来源：原创 2025/7/5 17:05:45

文章目录

  • 序
  • 二叉搜索树（BST）
    • 引入
    • 查找5
    • 插入9
    • 极端情况
    • 删除
      • 删除叶节点 10
      • 删除节点只有左子树或只有右子树
      • 删除节点既有左子树又有右子树
      • 为什么这么代替？

序

提到HashMap，就不得不提红黑树（HashMap1.8之后），所以我们先来了解红黑树这个数据结构。但是在学习红黑树之前，又不得不提红黑树的由来。因此，让我们从二叉树搜索树开始，循序渐进理解HashMap原理。

二叉搜索树（BST）

引入

针对有序数组的存储，查找（二分查找）的效率可以达到O(log2n), 但是插入和删除操作因为需要挪动后面所有的元素，所以时间复杂度是O(n)。

由此引入我们的二叉搜索树，即BST树。
在这里插入图片描述左 < 根 < 右
中序遍历： 从小到大

查找5

在这里插入图片描述
查找效率取决于树的高度，O(log2n)

插入9

在这里插入图片描述插入效率也取决于树的高度，O(log2n)

极端情况

退化成链表
在这里插入图片描述

删除

删除叶节点 10

在这里插入图片描述
直接删除

删除节点只有左子树或只有右子树

在这里插入图片描述

删除节点既有左子树又有右子树

如删除根节点9， 拿左子树中最大的节点7代替9 ，然后删除 7
在这里插入图片描述
或者找到右子树中最小的节点10，用10代替9，删除10
在这里插入图片描述

为什么这么代替？

从中序遍历来看7 9 10 三个数的位置，用7 或 10 代替9 并不会影响BST树的性质。
在这里插入图片描述

相关文章：

Java基础系列-HashMap源码解析1-BST树

文章目录 序二叉搜索树&#xff08;BST&#xff09;引入查找5插入9极端情况删除删除叶节点 10删除节点只有左子树或只有右子树删除节点既有左子树又有右子树为什么这么代替&#xff1f; 序 提到HashMap&#xff0c;就不得不提红黑树&#xff08;HashMap1.8之后&#xff09;&am…...

编程日记 2025/7/5 17:05:45

生物计算安全攻防战：从DNA存储破译到碳基芯片防御体系重构

随着碳基生物芯片突破冯诺依曼架构限制&#xff0c;DNA数据存储密度达到1EB/克量级&#xff0c;合成生物学与信息技术的融合正引发新一轮安全革命。本文深入解析碳基芯片逆向工程路径&#xff0c;揭示酶驱动DNA数据解码的技术突破&#xff0c;预警合成生物回路潜在的数据泄露风…...

编程日记 2025/7/5 17:03:20

【金仓数据库征文】从Oracle到KingbaseES的语法兼容与迁移

随着“信创”战略的深入推进&#xff0c;国产数据库逐渐成为IT系统的重要组成部分。KingbaseES&#xff08;金仓数据库&#xff09;凭借其良好的Oracle兼容性和日益完善的生态&#xff0c;成为金融、政务等核心行业国产化替代的重要选项。本文将从语法兼容性分析出发&#xff0…...

编程日记 2025/7/2 15:12:02

MATLAB 下载安装教程

## 一、下载MATLAB 1. 访问 MathWorks 官方网站&#xff1a;https://www.mathworks.com/ 2. 点击右上角的"登录"按钮 - 如果没有账号&#xff0c;需要先注册一个 MathWorks 账号 - 学生可以使用教育邮箱注册&#xff0c;获得教育版授权 3. 登录后&#xff0c;点击&…...

编程日记 2025/7/5 16:55:49

Android kotlin通知功能完整实现指南：从基础到高级功能

本文将详细介绍如何在Android应用中实现通知功能&#xff0c;包括基础通知、动作按钮和内联回复等高级特性。 一、基础通知实现 1. 基本通知发送方法 fun sendBasicNotification(context: Context, title: String, message: String) {// 1. 创建通知渠道(Android 8.0必需)va…...

编程日记 2025/6/29 11:48:32

Javase 基础入门 —— 04 继承

本系列为笔者学习Javase的课堂笔记&#xff0c;视频资源为B站黑马程序员出品的《黑马程序员JavaAI智能辅助编程全套视频教程&#xff0c;java零基础入门到大牛一套通关》&#xff0c;章节分布参考视频教程&#xff0c;为同样学习Javase系列课程的同学们提供参考。 01 什么是继…...

编程日记 2025/7/5 4:58:45

2.4/Q2，Charls最新文章解读

文章题目&#xff1a;The impact of hearing ability on depression among retired middle-aged and elderly individuals in China: the chain mediating role of self-rated health and life satisfaction DOI&#xff1a;10.1186/s41043-025-00791-9 中文标题&#xff1a;中…...

编程日记 2025/7/5 16:47:08

对流对象的理解

在c里&#xff0c;“流”可以理解为数据传输与操作的“介质”。 从输入输出角度来看&#xff0c;有输入流&#xff08;比如cin&#xff09;和输出流&#xff08;cout&#xff09;。对于输入流&#xff0c;数据通过它从外部设备&#xff08;例如键盘&#xff09;“流入”程序内…...

编程日记 2025/6/29 11:30:05

RBAC权限-笔记

1. RBAC模型简介 1.1. RBAC三要素 RBAC权限模型&#xff08;Role-Based Access Control&#xff1a;基于角色的访问控制&#xff09;有3个基础组成部分&#xff0c;分别是&#xff1a;用户、角色和权限。它们之间的关系如下图所示&#xff1a; 用户(User&#xff09;&#xf…...

编程日记 2025/7/5 16:42:19

stm32之GPIO函数详解和上机实验

目录 1.LED和蜂鸣器1.1 LED1.2 蜂鸣器 2.实验2.1 库函数&#xff1a;RCC和GPIO2.1.1 RCC函数1. RCC_AHBPeriphClockCmd2. RCC_APB2PeriphClockCmd3. RCC_APB1PeriphClockCmd 2.1.2 GPIO函数1. GPIO_DeInit2. GPIO_AFIODeInit3. GPIO_Init4. GPIO_StructInit5. GPIO_ReadInputDa…...

编程日记 2025/6/29 11:52:57

MsQuick编译和使用

MsQuick编译和使用 编译克隆代码使用cmakevs2022编译 使用示例 编译 克隆代码 git clone --recurse-submodules https://github.com/microsoft/msquic.git使用cmakevs2022编译 然后直接configure之后Generate然后打开vs工程编译即可生成动态库 使用示例 #include <s…...

编程日记 2025/6/29 10:58:43

01 ubuntu中wps桌面快捷键无法使用

文章目录 1. 问题描述&#xff1a;2. 解决方法&#xff1a;3. 结果展示4. 参考 1. 问题描述&#xff1a; 2. 解决方法&#xff1a; 添加权限 chmod 755 ./wps-office-prometheus.desktop 右键选择允许运行 3. 结果展示 修改前 修改后 4. 参考 参考1...

编程日记 2025/7/4 11:57:35

云原生后端架构：重塑后端开发的新范式

📝个人主页🌹：慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、引言：后端开发的新时代正在到来 传统的后端开发常常面临如下挑战：部署流程复杂、环境不一致、系统难以扩展、监控能力薄弱、上线流程缓慢。在企业数字化转型、业务快速迭代的大背景下，这些问题暴露得…...

编程日记 2025/7/5 16:54:49

Linux命令-tcpdump

tcpdump 是一个功能强大的网络数据包捕获和分析工具。以下是 tcpdump 命令的完整参数列表及说明&#xff1a; 参数 -a 将网络地址和广播地址转换为名字 tcpdump -a -i eth0-A 以 ASCII 格式打印所有分组&#xff0c;最小化链路层头部信息 tcpdump -A-b 在数据链路层上选择协议…...

编程日记 2025/7/5 16:53:09

分糖果——牛客

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 题目描述 幼儿园准备了nnn包糖果&#xff0c;每包糖果里有111、222或333颗美味的糖果。现在需要将这些这些糖果平分给两个表现优异的小朋友以作奖励&#xff0c;为了公平公正&#xff0c;需要…...

编程日记 2025/7/5 17:03:21

L0、L2和L∞范数这三种范数的区别

目录 一、解释 ​​1. L0范数&#xff1a;数一数你有多少件行李​​ ​​2. L2范数&#xff1a;别把行李塞得太满​​ ​​3. L∞范数&#xff1a;别带任何超重的东西​​ ​​一句话总结​​ 二、作用 ​​1. L0范数的作用&#xff1a;做减法&#xff0c;只留最重要的​…...

编程日记 2025/7/5 16:50:49

[实战]zynq7000设备树自动导出GPIO

目录 zynq7000设备树自动导出GPIO添加设备树节点验证实验 结论 zynq7000设备树自动导出GPIO 今天无聊&#xff0c;掏出我82年产的microzed玩一玩。玩啥好呢&#xff0c;要不点个灯吧。于是&#xff0c;三下五除二&#xff0c;通过linux sys接口以及echo&#xff0c;很快就点亮…...

编程日记 2025/7/3 1:34:14

java六人打分

import java.util.Scanner;public class HelloWorld {public static void main(String[] args) {//打分平均分System.out.println("请输入六个评分");Scanner sc new Scanner(System.in);double[] score new double[6];for(int i0;i<score.length;i){System.ou…...

编程日记 2025/6/29 10:25:29

量子计算浪潮下的安全应对之法

量子计算凭借其强大的计算能力&#xff0c;被传言能够在极短时间内秒级破解传统计算机需耗时漫长岁月&#xff08;以万年算&#xff09;才能解开的密码&#xff0c;成为了近年来人们讨论的热点。这看似高深的科技名词在网络安全中又扮演着何种角色&#xff1f;我们应从当前人们…...

编程日记 2025/7/2 15:44:45

Windows Server 2022 常见问题解答

一、安装与部署 1.1 系统要求 硬件配置：最低需要 1.4 GHz 64 位处理器、512 MB 内存、32 GB 硬盘空间。但在实际生产环境中，为确保系统流畅运行，建议使用 2.0 GHz 以上处理器、8 GB 以上内存和 100 GB 以上硬盘。软件兼容性：与大多数基于 Windows 的企业级应用兼容，但在安…...

编程日记 2025/7/2 11:14:28

项目组合管理PPM

项目组合管理（Project Portfolio Management, PPM）详述 一、定义与核心目标 定义 项目组合管理是通过系统化的方法，对组织的所有项目和项目集进行识别、选择、优先级排序、资源配置和动态监控，以确保其与战略目标一致，并最大化投资回报（ROI）的管理过程。 核心目标 战略…...

编程日记 2025/7/3 11:13:45

自建开源远程协助服务RustDesk —— 筑梦之路

开源项目 # 服务端https://github.com/rustdesk/rustdesk-server.git# 客户端https://github.com/rustdesk/rustdesk.git 搭建服务端 需要使用的端口、协议 hbbs - RustDesk ID 注册服务器 hbbr - RustDesk 中继服务器默认情况下&#xff0c;hbbs 监听 21115(tcp) , 21…...

编程日记 2025/7/2 13:22:58

【android bluetooth 协议分析 11】【AVDTP详解 2】【avdtp 初始化阶段主要回调关系梳理】

在车机中 a2dp 通常情况下作为 sink. 本篇来帮助各位 朋友梳理一下&#xff0c;这部分的初始化流程。 我们着重梳理 native 层的逻辑&#xff0c; framework - java 侧一般比较容易看明白&#xff0c; 暂时不做梳理。 如果需要笨叔梳理的可以在博客评论。 出专门的章节来梳理。…...

编程日记 2025/7/4 5:49:08

C++回顾 day3

宏定义的数据是在预处理发生了替换 const类型的数据是在编译阶段发生的替换 命名空间 namespace 空间名{int a;void func_print(){printf("func_print");}struct Stu{int x;char *y;};//或者其他命名空间 } Space::x 20; cout << Space::x;using Space::x;…...

编程日记 2025/6/29 11:34:50

机器学习算法-分类决策树

分类决策树算法-python实现 数据集 具体方法是&#xff1a;从根结点开始&#xff0c;对结点计算所有可能的特征的信息增益&#xff0c;选择信息增益最大的特征作为结点的特征&#xff0c;由该特征的不同取值建立子节点&#xff1b;再对子结点递归地调用以上方法&#xff0c;构…...

编程日记 2025/7/4 20:19:32

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（9）： 意向形

日语学习-日语知识点小记-构建基础-JLPT-N4阶段&#xff08;9&#xff09;&#xff1a; 意向形 1、前言&#xff08;1&#xff09;情况说明&#xff08;2&#xff09;工程师的信仰 2、知识点&#xff08;1&#xff09;「&#xff5e;てしまう」&#xff1d;「&#xff5e;ちゃう…...

编程日记 2025/7/3 1:34:26

kotlin与MVVM结合使用总结（一）

一、Kotlin 与 MVVM 结合的核心优势 代码简洁性 数据类&#xff08;data class&#xff09;简化 Model 层定义&#xff0c;自动生成equals/hashCode/toString扩展函数简化 View 层逻辑&#xff08;如点击事件扩展&#xff09;lateinit/by lazy优化 ViewModel 属性初始化 异步处…...

编程日记 2025/7/3 12:48:32

达妙电机CAN通信及实验

项目进一步往下做的时候&#xff0c;要上实物了&#xff0c;需要用到达妙电机&#xff0c;虽然有说明书和例程&#xff0c;但是STM32控制电机的具体时间还是花了些时间&#xff0c;我的板子和例程的有些区别&#xff0c;中间很多地方都需要进行修改完善&#xff0c;而且还补充了…...

编程日记 2025/7/4 12:12:48

语音合成之四基于LLM的语音合成

基于LLM的语音合成 1.技术架构1.1 LlaSA1.2 CosyVoice (和 CosyVoice2)1.3 SparkTTS 2 特性对比2.1 零样本语音克隆2.2 多语种支持2.3 可控语音生成2.4 计算效率和模型大小 总结 当前&#xff0c;在大型语言模型&#xff08;Large Language Models&#xff0c;LLMs&#xff09;…...

编程日记 2025/6/29 11:12:36

Docker Python 官方镜像使用说明（TAG说明）

Docker Python 官方镜像使用说明&#xff08;TAG说明&#xff09; 本文将以python的3.12版本&#xff0c;详细讲解官方 Python 镜像 的TAGS含义 官方文档&#xff1a;https://github.com/tuonioooo/docker &#x1f9ed; 一张图先看懂&#xff08;最常见 Tag&#xff09; py…...

编程日记 2025/7/3 19:46:59

Node.js 开发用户登录功能（使用mysql实现）

在 Web 开发中&#xff0c;用户登录功能是一个基础且重要的部分。、 一、环境搭建 在开始开发之前&#xff0c;我们需要搭建好相应的开发环境。以下是所需的工具和库&#xff1a; Node.js&#xff1a;作为 JavaScript 的运行环境&#xff0c;为我们的项目提供支持。mysql2&am…...

编程日记 2025/6/29 9:23:59

程序员学英文之Shipment Claim 运输和索赔

Time is precious , don’t waste your time, you should spend your time on something valuable . 时间很宝贵&#xff0c;不要浪费时间&#xff0c;你应该把时间用在有 价值的事情上。 Dia-1: Shipment by Voyage Charter 租船装运 1. May I know when your bo…...

编程日记 2025/7/3 21:06:08

python实战项目64：selenium采集软科中国大学排名数据

python实战项目64：selenium采集软科中国大学排名数据 一、项目需求二、流程分析三、完整代码一、项目需求 本项目的需求是使用selenium采集软科中国大学排名的数据。网站首页如下： 抓取此网页数据一般有两种方式，一种是直接发requests请求，我们这里采用的是使用selenium控…...

编程日记 2025/7/3 17:58:38

Linux服务器:在ufw防火墙设置这套规则sudo ufw allow from 172.0.0.0/8,为什么容器就可以访问宿主机的服务了?

在 Docker 环境中，容器默认使用 桥接网络（bridge），宿主机和容器之间的通信会受到防火墙（如 ufw）的限制。当你执行 sudo ufw allow from 172.0.0.0/8 后，容器可以访问宿主机上的服务，原因如下： 1. Docker 默认使用 172.x.x.x 网段 Docker 默认会创建一个 docker0 网桥…...

编程日记 2025/7/3 4:58:58

Google搜索技巧

谷歌搜索 1. 使用双引号 (" ") 精确匹配短语 ● 例子&#xff1a;"人工智能的定义" ● 作用&#xff1a;确保搜索结果中包含完全匹配的短语&#xff0c;而不是单独的单词。 2. 使用减号 (-) 排除特定词语 ● 例子&#xff1a;苹果 -水果 ● 作用&…...

编程日记 2025/7/4 4:29:22

Reactor编程模型介绍

Reactor 模型是一种基于事件驱动的编程模型，广泛应用于高并发网络服务器的设计中。它通过事件循环和回调机制，将事件的处理逻辑从主线程中解耦出来，从而实现高效的异步 I/O 操作。Reactor 模型的核心思想是利用一个或多个事件分发器（Reactor）来监听各种事件（如 I/O 事件、…...

编程日记 2025/7/3 17:58:53

C++笔记-stack_queue(含deque，priority_queue，仿函数的讲解)

一.stack和queue的基本使用 stack和queue就是我们之前所学的栈和队列&#xff0c;这两个和之前学的vector&#xff0c;list不太一样&#xff1a; 这是vector和list的&#xff0c;注意第一行中写的containers&#xff0c;代表这两个都是容器&#xff0c;但是&#xff1a; stac…...

编程日记 2025/7/3 12:56:30

意见反馈留言二维码制作

意见反馈对于工作整改具有重要作用&#xff0c;在工作中一味埋头苦干不如抬头多听听反馈声音。而传统的反馈内容投递后&#xff0c;因为繁琐性和时效性的枷锁&#xff0c;往往石沉大海&#xff0c;不知何时才能得到回应&#xff0c;这就导致反馈信息的延迟&#xff0c;一些时效…...

编程日记 2025/7/3 8:46:10

扣子智能体平台深度解读：功能剖析与全流程工作流详解

在上一篇文章中&#xff0c;我们已经带大家了解了“智能体”这一概念的内涵&#xff0c;并通过扣子智能体平台的各大模块做了初步介绍&#xff0c;同时用一个简单的示例演示了如何构建和部署第一个智能体。那篇文章打好了基础&#xff0c;让大家对智能体的基本组成与工作方式有…...

编程日记 2025/7/3 11:29:57

C语言五子棋项目

头文件与宏定义 #include <graphics.h> #include <conio.h> graphics.h&#xff1a;EasyX 图形库&#xff0c;提供图形绘制功能&#xff08;画线、画圆、显示文字等&#xff09;。 conio.h&#xff1a;提供控制台输入输出函数&#xff08;这里只是为了兼容性&…...

编程日记 2025/7/4 1:10:43

建筑安全员 A 证与 C 证：差异决定职业方向

在建筑行业的职业发展道路上&#xff0c;安全员 A 证和 C 证就像两条不同的岔路&#xff0c;它们之间的差异&#xff0c;在很大程度上决定了从业者的职业方向。 从证书性质和用途来看&#xff0c;A 证是从业资格证书&#xff0c;更像是一把开启安全管理高层岗位的 “金钥匙”。…...

编程日记 2025/7/3 1:34:39

长连接、短连接与WebSocket的基本知识

目录 前言正文 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 爬虫神器&#xff0c;无代码爬取&#xff0c;就来&#xff1a;bright.cn Java基本知识&#xff1a; java框架 零基础从入门到精通的学习路线 附…...

编程日记 2025/7/3 7:05:46

MySQL常见问题解答

一、安装与配置问题 1. 安装失败（权限 / 依赖 / 端口冲突） 权限问题：以管理员身份运行安装程序（Windows）或使用sudo（Linux）。依赖缺失： Windows 需安装 Visual C++ Redistributable（如 2013 版）。Linux 通过包管理器安装依赖（如libaio、perl）。端口冲突： 检查 33…...

编程日记 2025/7/3 19:07:29

Codeforces Round 1019 (Div. 2)（ABCD）

A. Common Multiple 翻译&#xff1a; 给你一个整数数组 a1,a2,...,an。如果存在一个数组 y1,y2,...,ym&#xff0c;且 y 的元素是不同的&#xff08;换句话说&#xff0c;对于所有 1≤i<j≤m 的数组&#xff0c;yi≠yj&#xff09;&#xff0c;并且对于所有 1≤i≤m 的数组…...

编程日记 2025/6/29 11:21:37

爬虫学习总结

通过前几次课&#xff0c;我们学习了爬虫的相关基础知识。 以下是我对爬虫学习做的一些总结&#xff1a; 一、认识爬虫&#xff1a;开启数据抓取之旅 1.1 什么是网络爬虫​ 网络爬虫就像是一个不知疲倦的 “数据搬运工”&#xff0c;它能按照预先设定的规则&#xff0c;自动…...

编程日记 2025/6/29 10:53:41

UE5的 Modify Curve 蓝图节点

In Unreal Engine’s Animation Blueprints, the Modify Curve node lets you drive and alter any named Animation Curve on your character at runtime. The Apply Mode setting on that node controls how the “new” value you feed in (via the added curve‐input pin)…...

编程日记 2025/7/3 19:36:11

鸿蒙中的并发线程间通信、线程间通信对象

目录 并发线程间通信1. 线程间通信对象1.1 普通对象1.2 ArrayBuufer对象1.3 SharedArrayBuffer对象1.4 Transferable对象&#xff08;NativeBinding对象&#xff09;1.5 Sendable对象简介异步锁ASON解析与生成共享容器共享模块Sendable对象冻结 2 线程间通信场景2.1 使用TaskPo…...

编程日记 2025/6/29 9:24:00

Elasticsearch内核探秘：从Shard分配到网络通信的深度实践指南

#作者&#xff1a;孙德新 文章目录 一、底层模块深入解析之shard allocation1、shard allocation的介绍2、cluster level shard allocation介绍3、disk-based shard allocation介绍4、shard allocation awareness5、shard allocation filtering6、node下线时的shard延迟分配7、…...

编程日记 2025/7/4 13:32:39

Vue3 模板语法

目录 一、插值语法 {{ }} 二、核心指令 三、动态属性绑定 四、事件修饰符 五、条件渲染 vs 列表渲染总结 六、最佳实践 示例 1&#xff1a;插值语法 & 基础绑定 示例 2&#xff1a;条件渲染 示例 3&#xff1a;列表渲染 示例 4&#xff1a;事件处理 示例 5&…...

编程日记 2025/7/4 2:02:47

第1节：Backtrader到底是个啥？能干嘛？

——“框架在手&#xff0c;天下我有&#xff1b;不是吹&#xff0c;Backtrader真香警告&#xff01;” &#x1f423; 一句话简介 Backtrader 是一个 专门为量化交易打造的 Python 回测框架&#xff0c;说白了&#xff0c;它就是一个量化策略“模拟器控制台评审团”&#xff…...

编程日记 2025/6/29 9:23:53