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

【Java 面试合集】HashMap中为什么引入红黑树,而不是AVL树呢

HashMap中为什么引入红黑树,而不是AVL树呢

1. 概述

开始学习这个知识点之前我们需要知道,在JDK1.8 以及之前,针对HashMap有什么不同。

  • JDK 1.7的时候,HashMap的底层实现是数组 + 链表
  • JDK1.8的时候,HashMap的底层实现是数组 + 链表 + 红黑树

我们要思考一个问题,为什么要从链表转为红黑树呢。

首先先让我们了解下链表有什么不好???

2. 链表

链表

上述的截图其实就是链表的结构,我们来看下链表的增删改查的时间复杂度

  • 增:因为链表不是线性结构,所以每次添加的时候,只需要移动一个节点,所以可以理解为复杂度是N(1)
  • 删:算法时间复杂度跟保持一致
  • 查:既然是非线性结构,所以查询某一个节点的时候,最起码要遍历一遍,所以时间复杂度为O(n).

所以问题就来了,我们的目的就是优化链表查询效率,结果就是转换数据结构,从而引出了我们的平衡二叉树

3. 平衡二叉树

平衡二叉树是一种结构相对平衡的二叉搜索树。既然是二叉树结构,比较理想的状态如上图所示,节点分布相对平衡

但是还有一种情况:

在这里插入图片描述
这种也是一种平衡二叉树的结构,而我们实际的业务中出现这种状态概率很多,而那种理想的平衡二叉树的状态就很少。

所以我们为了保证,如果生成一个平衡二叉树,我们要求这个二叉树无论有多少节点,都一定要保持相对平衡。

所以我们使用了红黑树来满足这个需求

红黑树

相关文章:

【Java 面试合集】HashMap中为什么引入红黑树,而不是AVL树呢

HashMap中为什么引入红黑树,而不是AVL树呢1. 概述 开始学习这个知识点之前我们需要知道,在JDK1.8 以及之前,针对HashMap有什么不同。 JDK 1.7的时候,HashMap的底层实现是数组 链表JDK1.8的时候,HashMap的底层实现是数…...

深度学习Week15-common.py文件解读(YOLOv5)

目录 简介 一.基本组件 1.1autopad 1.2Conv 1.3 Focus 1.4Bottleneck 1.5BottleneckCSP 1.6 C3 1.7 SPP 1.8Concat 1.9Contract、Expand 二、重要类 2.1非极大值抑制(NMS) 2.2AutoShape 2.3 Detections 2.4 Classify 三、实验 &#x1f…...

qemu的snapshot快照功能的详细使用介绍

快照功能还是蛮有趣的,就是资料比较少,这边万能菜道人特意整理了一下。参考内容:QEMU checkpoint(snapshot) 使用-pudn.comKVM&QEMU学习笔记(二)-蒲公英云 (dandelioncloud.cn)在线迁移存储 - 爱码网 (likecs.com)…...

谷歌关键词优化多少钱【2023年调研】

本文主要分享Google关键词排名优化的一些成本调研,方便大家参考。 本文由光算创作,有可能会被剽窃和修改,我们佛系对待这种行为吧。 今年2023年了,谷歌关键词优化到底要多少钱? 答案是:价格在2w~25w左右…...

凸包及其算法

概念 凸包:一个能够将所有给定点围住的最小周长封闭图形。 稳定凸包:在当前组成凸包的点集 V0V_0V0​ 中新增一个不在凸包上的点,形成新点集 V1V_1V1​,若可以使 V1V_1V1​ 中所有点都在 V1V_1V1​ 的点的凸包上,则这…...

计算机网络学习笔记(二)物理层

物理层(传输比特0/1)基本概念 物理层下的传输媒体 1. 导引型 同轴电缆,双绞线(绞合可抵御干扰),光纤,电力线 2. 非导引型(调制振幅 频率 相位) 无线电波,微…...

为什么职称要提前准备?

职称反映专业技术人员的学术和技术水平、工作能力的工作成就,具有学衔、岗位两种性质。目前中国现状下,职称主要代表社会地位,就业经验,职称等级越高,越容易得到更高的社会经济和福利待遇。 职称通过申报、评审的形式…...

MyBatis详解1——相关配置

一、什么是MyBatis 1.定义:是一个优秀的持久层框架(ORM框架),它支持自定义 SQL、存储过程以及高级映射。MyBatis是一个用来更加简单的操作和读取数据库的工具。 2.支持的操作方式:xml或者注解实现操作(xm…...

字节青训营——秒杀系统设计学习笔记(三)

限流算法 限流顾名思义,就是对请求或并发数进行限制;通过对一个时间窗口内的请求量进行限制来保障系统的正常运行。如果我们的服务资源有限、处理能力有限,就需要对调用我们服务的上游请求进行限制,以防止自身服务由于资源耗尽而…...

每天一道大厂SQL题【Day10】电商分组TopK实战

每天一道大厂SQL题【Day10】电商分组TopK实战 大家好,我是Maynor。相信大家和我一样,都有一个大厂梦,作为一名资深大数据选手,深知SQL重要性,接下来我准备用100天时间,基于大数据岗面试中的经典SQL题&…...

最全的免费录屏工具,这 19 款录屏软件绝对值得你收藏

屏幕录制软件可让您捕获屏幕以与他人共享,创建与产品相关的视频、教程、课程、演示、视频等。这些软件是您能够从网络摄像头和屏幕录制视频。以下是精选的顶级屏幕录像机列表。 适用于 PC 的19 款免费录屏屏幕录像机软件 1)奇客免费录屏 奇客免费录屏&am…...

vb.net计算之.net core基础(2)-发布应用

目录 发布程序测试运行运行方式发布程序 首先,将编译配置改为Release 然后,发布应用,在生成菜单下。 选择发布到文件夹 继续选择文件夹 接着,完成 关闭 点击发布标签栏的发布按钮...

微服务项目【商品秒杀接口压测及优化】

生成测试用户 将UserUtils工具类导入到zmall-user模块中,运行生成测试用户信息,可根据自身电脑情况来生成用户数量。 UserUtils: package com.xujie.zmall.utils;import com.alibaba.nacos.common.utils.MD5Utils; import com.fasterxml.j…...

1997. 访问完所有房间的第一天

题目 你需要访问 n 个房间,房间从 0 到 n - 1 编号。同时,每一天都有一个日期编号,从 0 开始,依天数递增。你每天都会访问一个房间。 最开始的第 0 天,你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 n…...

通达信交易接口以什么形式执行下单的?

通达信程交易接口 以API形式来执行下单接口,一般不再需要通过接口系统之间进行连接,通过直接调用通达信dll交易函数的方式直接进行交易,包括下单,撤单,查询资金股份、当日委托、当日成交等方面都能很快的执行出来。以a…...

CobaltStrike上线微信通知

CobaltStrike上线微信通知 利用pushplus公众号(每天免费发送200条消息) http://www.pushplus.plus/push1.html 扫码登录后需要复制token 可以测试一下发送一下消息,手机会受到如下消息。可以在微信提示里将消息免打扰关闭(默认…...

喜茶、奈雪的茶“花式”寻生路

配图来自Canva可画 疫情全面开放不少人“阳了又阳”,电解质饮品成为热销品,梨子、橘子、柠檬等水果被卖断货,凉茶、黄桃罐头被抢购一空,喜茶的“多肉大橘”、奈雪的“霸气银耳炖梨”、蜜雪冰城的“棒打鲜橙”、沪上阿姨的“鲜炖整…...

Xstream使用教程

1.Xstream介绍 官网:https://x-stream.github.io/tutorial.html 介绍:XStream 对象序列化和反序列化为 XML的一个JAVA类库。JDK 1.4以上适用。 PS:与JAXB相比,Xstream更好用一些,像XStreamImplicit这种注解,我在JAX…...

【正点原子FPGA连载】第十一章PL SYSMON测量输入模拟电压 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南

1)实验平台:正点原子MPSoC开发板 2)平台购买地址:https://detail.tmall.com/item.htm?id692450874670 3)全套实验源码手册视频下载地址: http://www.openedv.com/thread-340252-1-1.html 第十一章PL SYSM…...

纷享销客百思特 | 数字化营销赋能企业新增长沙龙圆满落幕

为进一步帮助企业客户实现数字化转型,纷享销客联合百思特管理咨询集团,于2月10日举办 “数字化营销赋能企业新增长”主题沙龙。本次活动以“新变革新增长”为主题,现场30余位制造企业高管齐聚一堂,共同探讨企业如何在当前复杂的宏…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...