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

TreeMap 核心知识点与面试题解析

TreeMap 核心知识点与面试题解析

一、TreeMap 基础概念

TreeMap 是 Java 集合框架中基于 红黑树(Red-Black Tree) 实现的 Map,具有以下特点:

  • 有序性:默认按 key 的自然顺序Comparable)或自定义顺序Comparator)排序。

  • 时间复杂度

    • 插入、删除、查找:O(log n)

    • 遍历(如 entrySet()):O(n)(中序遍历)

  • 线程不安全:需用 Collections.synchronizedMap() 或 ConcurrentSkipListMap 替代。


二、TreeMap 核心实现

1. 底层数据结构:红黑树

  • 红黑树特性

    • 每个节点是红色或黑色。

    • 根节点和叶子节点(NIL)是黑色。

    • 红色节点的子节点必须是黑色(不能连续红节点)。

    • 从任意节点到其叶子节点的路径上,黑色节点数相同(黑高平衡)。

  • 自平衡机制:通过旋转(左旋/右旋)变色保持平衡。

2. 排序方式

  • 自然排序Comparable):

    java

    TreeMap<String, Integer> map = new TreeMap<>(); // 默认按 String 字典序

    自定义排序Comparator):

  • java

TreeMap<Integer, String> map = new TreeMap<>((a, b) -> b - a); // 降序

三、高频面试题

1. TreeMap 和 HashMap 的区别?

对比项TreeMapHashMap
底层结构红黑树数组 + 链表/红黑树
是否有序是(按 key 排序)否(无序)
时间复杂度O(log n)O(1)(平均)
线程安全
允许 null key取决于 Comparator允许(但只能有一个)

2. TreeMap 如何保证有序?

  • 红黑树的中序遍历(左-根-右)会按 key 的顺序输出。

  • 依赖 Comparable 或 Comparator 定义排序规则。

3. TreeMap 的 put() 方法流程?

  1. 如果红黑树为空,直接插入为根节点(黑色)。

  2. 按 Comparator 或 Comparable 查找插入位置。

  3. 插入新节点(默认为红色)。

  4. 平衡调整(可能涉及变色和旋转):

    • 如果父节点是红色:

      • 检查叔叔节点:

        • 叔叔是红色 → 变色(父、叔变黑,祖父变红)。

        • 叔叔是黑色 → 旋转 + 变色(左旋/右旋)。

4. 如何实现自定义排序?

java

// 按 value 排序(需转为 List 再排序)
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
list.sort((a, b) -> a.getValue() - b.getValue());// 或者使用 Comparator
TreeMap<String, Integer> customMap = new TreeMap<>((a, b) -> b.compareTo(a)); // 降序

5. TreeMap 的 ceilingKey() 和 floorKey() 方法作用?

  • ceilingKey(K key):返回 ≥ key 的最小 key(如没有,返回 null)。

  • floorKey(K key):返回 ≤ key 的最大 key(如没有,返回 null)。

java

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(3, "B");
map.put(5, "C");map.ceilingKey(2); // 3
map.floorKey(4);   // 3

6. TreeMap 为什么用红黑树而不用 AVL 树?

对比项红黑树AVL 树
平衡标准黑高平衡(宽松)严格高度平衡(左右子树高度差 ≤1)
插入/删除最多 3 次旋转(O(1))可能需 O(log n) 次旋转
查询效率O(log n),但常数项较大更快(严格平衡)
适用场景适合频繁修改(如 Java 集合)适合高频查询(如数据库索引)

四、代码实战

1. 按 key 降序排列

java

TreeMap<Integer, String> map = new TreeMap<>((a, b) -> b - a);
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");System.out.println(map); // {3=C, 2=B, 1=A}

2. 获取子映射(subMap)

java

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.put(4, "D");// 获取 [2, 4) 的子映射
SortedMap<Integer, String> subMap = map.subMap(2, 4);
System.out.println(subMap); // {2=B, 3=C}

五、总结

  • TreeMap 适用于需要有序 key 的场景(如范围查询、排序)。

  • 底层是红黑树,保证 O(log n) 的操作效率。

  • 面试重点

    • 红黑树原理

    • 与 HashMap 的区别

    • 排序方式(Comparable/Comparator)

    • 常用方法(ceilingKey, floorKey, subMap)

相关文章:

TreeMap 核心知识点与面试题解析

TreeMap 核心知识点与面试题解析 一、TreeMap 基础概念 TreeMap 是 Java 集合框架中基于 红黑树&#xff08;Red-Black Tree&#xff09; 实现的 Map&#xff0c;具有以下特点&#xff1a; 有序性&#xff1a;默认按 key 的自然顺序&#xff08;Comparable&#xff09;或自定…...

深入理解 DevOps 与 CI/CD:概念、流程及优势

在当今快速发展的数字化时代,软件开发和交付的速度与质量成为企业在激烈竞争中脱颖而出的关键因素。DevOps 和 CI/CD 作为现代软件开发领域的重要理念和实践,正深刻地改变着软件开发生命周期的运作方式。本文将深入探讨 DevOps 的概念,详细解析 CI/CD 的内涵、管道阶段以及实…...

Flutter BloC 架构入门指南

BLoC (Business Logic Component) 是 Flutter 中一种流行的状态管理架构&#xff0c;它可以帮助你将业务逻辑与 UI 分离&#xff0c;使代码更清晰、可测试性更强。 核心概念 1. BloC 的核心组件 Events&#xff1a;用户交互或系统事件&#xff08;如按钮点击、网络请求完成&…...

OpenHarmony-AI调研

OpenHarmony-AI调研 文章目录 OpenHarmony-AI调研前言一、当前版本部署组件二、AI架构1.mindspore-lite2.ai_engine3.neural_network_runtime4.intelligent_voice_framework5.HDI驱动 三、应用1.命令行以及web运行deepseek-r12.与deepseek通过语音进行交互3.物品识别4.人脸识别…...

zk基础—zk实现分布式功能

1.zk实现数据发布订阅 (1)发布订阅系统一般有推模式和拉模式 推模式&#xff1a;服务端主动将更新的数据发送给所有订阅的客户端。 拉模式&#xff1a;客户端主动发起请求来获取最新数据(定时轮询拉取)。 (2)zk采用了推拉相结合来实现发布订阅 首先客户端需要向服务端注册自己关…...

Tips:用proxy解决前后端分离项目中的跨域问题

在前后端分离项目中&#xff0c;"跨域问题"是浏览器基于同源策略&#xff08;Same-Origin Policy&#xff09;对跨域请求的安全限制。当你的前端&#xff08;如运行在 http://localhost:3000 &#xff09;和后端&#xff08;如运行在 http://localhost:8080 &#…...

JMeterPlugins-Standard-1.4.0 插件详解:安装、功能与使用指南

JMeterPlugins-Standard-1.4.0 是 Apache JMeter&#xff08;一款流行的开源负载和性能测试工具&#xff09;的插件包&#xff0c;它扩展了 JMeter 的功能&#xff0c;提供了更多监听器&#xff08;Listeners&#xff09;、采样器&#xff08;Samplers&#xff09;和辅助组件&a…...

JMeter 中,Token 和 Cookie 的区别及实际应用

在 JMeter 中,Token 和 Cookie 都是用于处理用户会话和身份验证的机制,但它们的 工作原理、存储方式 和 应用场景 有显著区别。以下是详细对比和实际应用指南: 1. 核心区别 特性Token (如 JWT、OAuth)Cookie存储位置通常存储在 HTTP 请求头(如 Authorization: Bearer <t…...

蓝桥杯真题——好数、R格式

目录 蓝桥杯2024年第十五届省赛真题-好数 【模拟题】 题目描述 输入格式 输出格式 样例输入 样例输出 提示 代码1&#xff1a;有两个案例过不了&#xff0c;超时 蓝桥杯2024年第十五届省赛真题-R 格式 【vector容器的使用】 题目描述 输入格式 输出格式 样例输入…...

JavaScript惰性加载优化实例

这是之前的一位朋友的酒桌之谈&#xff0c;他之前负责的一个电商项目&#xff0c;刚刚开发万&#xff0c;首页加载时间特别长&#xff0c;体验很差&#xff0c;所以就开始排查&#xff0c;发现是在首页一次性加载所有js导致的问题&#xff0c;这个问题在自己学习的时候并不明显…...

0_Pytorch中的张量操作

[引言]张量的概念 1.基本概念 张量是一个通用的多维数组&#xff0c;可以表示标量&#xff08;0 维&#xff09;、向量&#xff08;1 维&#xff09;、矩阵&#xff08;2 维&#xff09;以及更高维度的数据。张量是 PyTorch 中的核心数据结构&#xff0c;用于表示和操作数据。…...

Java面试43-常见的限流算法有哪些?

限流算法是一种系统保护策略&#xff0c;主要是避免在流量高峰导致系统被压垮&#xff0c;造成系统不可用的问题。 常见的限流算法有五种&#xff1a; 计数器限流&#xff0c;一般用在单一维度的访问频率限制上&#xff0c;比如短信验证码每隔60s只能发送一次&#xff0c;或者…...

牛客网:树的高度 ← 根节点为 0 号节点

【题目来源】 https://www.nowcoder.com/questionTerminal/4faa2d4849fa4627aa6d32a2e50b5b25 【题目描述】 现在有一棵合法的二叉树&#xff0c;树的节点都是用数字表示&#xff0c;现在给定这棵树上所有的父子关系&#xff0c;求这棵树的高度。 【输入格式】 输入的第一行表…...

Linux:进程程序替换execl

目录 引言 1.单进程版程序替换 2.程序替换原理 3.6种替换函数介绍 3.1 函数返回值 3.2 命名理解 3.3 环境变量参数 引言 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支)&#xff0c;我们所创建的所有的子进程&#xff0c;执行的代码&#x…...

⑩数据中心M-LAG 实战

一、配置指导自己去看今天操作的是M-LAG 基础实验 二、配置代码信息回顾 ### 1、配置 M-LAG 系统 MAC 地址<H3C>system-view[H3C]m-lag system-mac ?H-H-H MAC address2a7a-53ee-0100 Bridge MAC address[H3C]m-lag system-mac### 2、配置 M-LAG 系统编号…...

delphi idtcpserver 搭建tcp ,ssl协议服务端

如果想用indy idtcpserver实现tcp ssl,那么正是你需要的 首先生成证书: 2、windows生成pem证书 - 站着说话不腰疼 - 博客园 有证书后 idtcpserver 用的三个证书, IdServerIOHandlerSSLOpenSSL1.SSLOptions.CertFile = ca.crt IdServerIOHandlerSSLOpenSSL1.SSLOptions.…...

如何实现外观模式?

一、模式理解&#xff08;用快递驿站比喻&#xff09; 想象你网购了5件商品&#xff0c;分别来自不同快递公司。 外观模式就像小区门口的快递驿站&#xff0c;你不需要知道中通怎么分拣、顺丰怎么运输&#xff0c;只要到驿站报取件码就能拿到所有包裹。 在前端开发中&#xf…...

深入解析 Linux 文件系统权限:从基础到高级实践

引言 在 Linux 系统中&#xff0c;文件系统权限是保障数据安全和多用户协作的核心机制。想象这样一个场景&#xff1a; 你的服务器上有多个团队共享项目文件 财务数据必须严格保密&#xff0c;仅允许指定人员访问 开发团队需要共同编辑代码&#xff0c;但禁止随意删除他人文…...

GZ036区块链卷一 EtherStore合约漏洞详解

题目 pragma solidity >0.8.3;contract EtherStore {mapping(address > uint) public balances;function deposit() public payable {balances[msg.sender] msg.value;emit Balance(balances[msg.sender]);}function withdraw() public {uint bal balances[msg.sender…...

医药流通行业批发公司IT运维转型:Prometheus+Grafana监控Spring Boot 3应用实践

一、引言&#xff1a;医药流通行业IT运维挑战与工具换代需求 在医药流通行业批发领域&#xff0c;业务的核心在于供应链的高效运转、订单处理的精准及时以及库存管理的动态平衡。随着互联网医疗的兴起和电商平台的渗透&#xff0c;传统医药批发企业正加速向数字化、智能化转型…...

编程助手fitten code使用说明(超详细)(vscode)

这两年 AI 发展迅猛&#xff0c;作为开发人员&#xff0c;我们总是追求更快、更高效的工作方式&#xff0c;AI 的出现可以说改变了很多人的编程方式。 AI 对我们来说就是一个可靠的编程助手&#xff0c;给我们提供了实时的建议和解决方&#xff0c;无论是快速修复错误、提升代…...

金融大模型

FinGPT 数据集&#xff1a;https://github.com/AI4Finance-Foundation/FinGPT/tree/master/fingpt/FinGPT-v3 FinGPT v3 系列是在新闻和微博情绪分析数据集上使用 LoRA 方法进行微调的LLM&#xff0c;在大多数金融情绪分析数据集上取得了最佳分数。 FinGPT v3.1 使用 chatgl…...

【Pandas】pandas DataFrame infer_objects

Pandas2.2 DataFrame Conversion 方法描述DataFrame.astype(dtype[, copy, errors])用于将 DataFrame 中的数据转换为指定的数据类型DataFrame.convert_dtypes([infer_objects, …])用于将 DataFrame 中的数据类型转换为更合适的类型DataFrame.infer_objects([copy])用于尝试…...

011_异常、泛型和集合框架

异常、泛型和集合框架 异常Java的异常体系异常的作用 自定义异常异常的处理方案异常的两种处理方式 泛型泛型类泛型接口泛型方法、通配符和上下限泛型支持的类型 集合框架集合体系结构Collection Collection集合Collection的遍历方式认识并发修改异常问题解决并发修改异常问题的…...

QTSql全解析:从连接到查询的数据库集成指南

概览 与数据库的有效集成是确保数据管理效率和应用性能的关键&#xff0c;Qt框架就提供了强大的QtSql模块&#xff0c;使得开发者能够轻松地进行数据库操作&#xff0c;包括连接、查询执行以及结果处理等 一、引入QtSql模块 首先&#xff0c;需要在项目中引入QtSql模块&…...

docker快捷打包脚本(ai版)

直接进入主题&#xff1a; 用这个脚本前提是你本地可以拉镜像仓库的镜像&#xff0c;并且在 本地有了&#xff0c;然后将所有的镜像tag写在一个文件中&#xff0c;和下面docker_tags.txt 对应&#xff0c;文件叫什么&#xff0c;脚本里对应改什么&#xff0c;给小白说的 #!/bi…...

分布式防护节点秒级切换:实战配置与自动化运维

摘要&#xff1a;针对DDoS攻击导致节点瘫痪的问题&#xff0c;本文基于群联AI云防护的智能调度系统&#xff0c;详解如何实现节点健康检查、秒级切换与自动化容灾&#xff0c;并提供Ansible部署脚本。 一、分布式节点的核心价值 资源分散&#xff1a;攻击者难以同时击溃所有节…...

TBE(TVM的扩展)

算子 张量 一个张量只有一种数据类型 在内存中只能线性存储&#xff0c;最终形成一个长的一维数组 晟腾AI的数据格式 AIPP是对我们常见的数据格式转化成AI core支持的数据格式 广播机制 TVM TBE的第一种开发方式&#xff1a;DSL TBE的第二种开发方式&#xff1a;TVM TBE的第…...

Jenkins配置的JDK,Maven和Git

1. 前置 在配置前&#xff0c;我们需要先把JDK&#xff0c;Maven和Git安装到Jenkins的服务器上。 &#xff08;1&#xff09;需要进入容器内部&#xff0c;执行命令&#xff1a;docker exec -u root -it 容器号/容器名称&#xff08;2选1&#xff09; bash -- 容器名称 dock…...

核心案例 | 湖南汽车工程职业大学无人机操控与编队技术实验室

核心案例 | 湖南汽车工程职业大学无人机操控与编队技术实验室 为满足当今无人机行业应用需求&#xff0c;推动无人机技术的教育与实践深度融合&#xff0c;北京卓翼智能科技有限公司旗下品牌飞思实验室与湖南汽车工程职业大学强强联手&#xff0c;共同建设无人机操控与编队技术…...

【阻抗匹配】

自动匹配的实现&#xff1a; 检测反射信号&#xff1a;通过传感器&#xff08;如定向耦合器&#xff09;监测反射功率或驻波比&#xff08;SWR&#xff09;&#xff0c;判断是否失配。控制单元&#xff1a;利用微控制器或专用芯片&#xff08;如FPGA&#xff09;分析检测数据&a…...

micro常用快捷键

micro常用快捷键 以下是 micro 编辑器 的常用快捷键整理&#xff0c;按功能分类清晰&#xff0c;方便快速查阅&#xff1a; 1. 基础操作 快捷键功能​Ctrl S​保存文件​Ctrl Q​退出编辑器​Ctrl O​打开文件​Ctrl E​打开命令栏&#xff08;输入命令&#xff09;​Ctr…...

DNS域名解析服务

目录 DNS系统 DNS系统的作用 DNS系统的类型&#xff08;服务器分类&#xff09; 1. ‌递归解析器&#xff08;Recursive Resolver&#xff09;‌ 2. ‌根域名服务器&#xff08;Root Name Server&#xff09;‌ 3. ‌顶级域服务器&#xff08;TLD Name Server&#xff09;…...

Linux的目录结构

倒根树状结构 【注意】 / 表示根目录&#xff0c;相当于Windows的C盘 进入跟目录命令&#xff1a; cd / /bin&#xff1a;存放的系统命令或二进制文件&#xff0c;如&#xff1a;cd ls cp等 /sbin /usr/bin /dev&#xff1a;存放的设备节点文件 &#xff0c; 驱动文件 /…...

【Python】Python 100题 分类入门练习题 - 新手友好

Python 100题 分类入门练习题 - 新手友好篇 - 整合篇 一、数学问题题目1&#xff1a;组合数字题目2&#xff1a;利润计算题目3&#xff1a;完全平方数题目4&#xff1a;日期天数计算题目11&#xff1a;兔子繁殖问题题目18&#xff1a;数列求和题目19&#xff1a;完数判断题目21…...

Three.js 系列专题 7:性能优化与最佳实践

内容概述 随着 3D 场景复杂度的增加,性能优化变得至关重要。Three.js 项目可能因几何体数量、纹理大小或渲染设置而变慢。本专题将介绍减少 draw call、优化纹理和使用调试工具的最佳实践。 学习目标 学会减少 draw call 和几何体复杂度。掌握纹理压缩与内存管理。使用 Stat…...

特权FPGA之Johnson移位

完整代码&#xff1a; module johnson(clk,rst_n,led,sw1_n,sw2_n,sw3_n);input clk; //时钟信号&#xff0c;50MHz input rst_n; //复位信号&#xff0c;低电平有效 output[3:0] led; //LED控制&#xff0c;1--灭&#xf…...

聊聊 CSS

先补充一些概念 C/S&#xff08;客户端/服务器&#xff09;&#xff1a;要下载到本地才能用 需要安装、偶尔更新、不跨平台 B/S&#xff08;浏览器/服务器&#xff09;&#xff1a;在浏览器输入网址就可以使用 无需安装、无需更新、可跨平台 [!NOTE] B/S 架构优点如此之多&am…...

域名系统DNS

一 概述 域名系统DNS是互联网使用的命名系统&#xff0c;用来把便于人们使用的机器名称转换为IP地址&#xff0c;比如我们熟知的www.baidu.com,www.sina.com&#xff0c;这些域名的背后都对应着一个又一个的IP地址。由域名转换为IP的过程我们称为解析&#xff0c;解析的过程大…...

大模型ui设计SVG输出

你是一位资深 SVG 绘画设计师&#xff0c;现需根据以下产品需求创建SVG方案&#xff1a; 产品需求 约拍app 画板尺寸&#xff1a; 宽度&#xff1a;375px&#xff08;基于提供的HTML移动设计&#xff09;高度&#xff1a;812px&#xff08;iPhone X/XS 尺寸&#xff09; 配…...

利用securecrt的tftp服务器功能传递文件

日常经常能用到需要调测一些openwrt设备&#xff0c;要互相拷贝文件&#xff0c;没有开启ftp功能时&#xff0c;这时可以用到crt的tftp内置服务器功能&#xff0c;利用tftp功能传递文件。 配置方法&#xff1a; 打开设置→全局配置→终端→tftp配置设置c上内置tftp服务器时&a…...

基于STM32、HAL库的IP2736U快充协议芯片简介及驱动程序设计

一、简介: IP2736U是一款高性能的USB Type-C和Power Delivery(PD)控制器芯片,支持最新的USB PD 3.0规范。它具有以下特点: 支持USB Type-C和PD 3.0协议 内置MCU,可编程配置 支持多种供电角色(Source/Sink/DRP) 支持PPS可编程电源 支持多种快充协议(PD/QC/AFC/FCP/SCP等) I…...

SQL学习笔记七

第九章用正则表达式进行搜索 9.1正则表达式介绍 正则表达式是用来匹配文本的特殊的串&#xff08;字符集合&#xff09;。如果你想从一个文本文件中提取电话号码&#xff0c;可以使用正则表达式。如果你需要查找名字中间有数字的所有文件&#xff0c;可以 使用一个正则表达式…...

MicroPython 开发ESP32应用教程 之 Timer、GPIO中断

随着我们课程的递进&#xff0c;大家会发现&#xff0c;我们之前课程中的例子&#xff0c;虽然功能都能实现&#xff0c;但总觉得体验感不够好&#xff0c;比如按键控制GRB灯珠的时候&#xff0c;很容易出现按键后&#xff0c;灯珠没有反应&#xff0c;还有蓝牙发送指令控制灯珠…...

【区块链安全 | 第三十七篇】合约审计之获取私有数据(一)

文章目录 私有数据访问私有数据实例存储槽Solidity 中的数据存储方式1. storage&#xff08;持久化存储&#xff09;定长数组变长数组 2. memory&#xff08;临时内存&#xff09;3. calldata 可见性关键字私有数据存储风险安全措施 私有数据 私有数据&#xff08;Private Dat…...

20250408在荣品的PRO-RK3566开发板使用Rockchip原厂的buildroot系统时拿掉经常出现的list-iodomain.sh警告信息

rootrk3566-buildroot:/usr/bin# vi list-iodomain.sh rootrk3566-buildroot:/usr/bin# sync 【最后】 #chk_env #get_chip_id $1 #echo_msg "Get CHIP ID: $CHIP_ID" #get_iodomain_val 20250408在荣品的PRO-RK3566开发板使用Rockchip原厂的buildroot系统时拿掉经常…...

上下拉电阻详解

一、基本定义 上拉电阻&#xff1a;连接信号线与电源&#xff08;VCC&#xff09;&#xff0c;确保信号在无驱动时保持高电平。 下拉电阻&#xff1a;连接信号线与地&#xff08;GND&#xff09;&#xff0c;确保信号在无驱动时保持低电平。 二、核心作用 电平稳定 防止悬空引…...

特权FPGA之数码管

case语句的用法&#xff1a; 计数器不断的计数&#xff0c;每一个num对应数码管一种数据的输出。实例通俗易懂&#xff0c;一目了然。 timescale 1ns / 1ps// Company: // Engineer: // // Create Date: // Design Name: // Module Name: // Project Name: //…...

PyTorch 学习笔记

环境&#xff1a;python3.8 PyTorch2.4.1cpu PyCharm 参考链接&#xff1a; 快速入门 — PyTorch 教程 2.6.0cu124 文档 PyTorch 文档 — PyTorch 2.4 文档 快速入门 导入库 import torch from torch import nn from torch.utils.data import DataLoader from torchvision …...

MCP基础学习计划:从MCP入门到项目构建的全面指南

文章简介 ai生成的学计划有的连接是无效的&#xff0c;想着边学习边找输出文章&#xff0c;后续会继续链接更新 在人工智能和大语言模型&#xff08;LLM&#xff09;的快速发展下&#xff0c;掌握Model Context Protocol&#xff08;MCP&#xff09;成为提升AI应用能力的关键。…...