Java中TreeSet和TreeMap的底层原理

TreeSet

Java中的TreeSet是一个基于红黑树(Red-Black Tree)实现的NavigableSet接口的实现类。红黑树是一种自平衡的二叉查找树,能够在动态数据结构中维持排序和二分搜索的性能。下面是关于TreeSet底层原理的总结:
数据结构:

TreeSet使用红黑树作为其底层数据结构。红黑树是一种特殊的二叉查找树,它满足以下五个特性:
1. 每个节点要么是红色,要么是黑色。
2. 根节点是黑色的。
3. 每个叶节点(NIL或空节点)是黑色的。
4.如果一个节点是红色的,则它的两个子节点都是黑色的。
5. 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
这些特性保证了红黑树的平衡性,从而保证了在插入、删除和查找等操作中的对数时间复杂度。

排序和唯一性:

TreeSet中的元素按照它们的自然顺序(如果元素实现了Comparable接口)或者根据提供的Comparator进行排序。
由于红黑树的特性,TreeSet中的元素总是保持有序的。
TreeSet不允许插入重复的元素。在添加新元素时,它会先检查元素是否已经在树中存在(通过比较操作)。如果存在,则不会添加该元素。

主要操作:

add(Object o): 将指定元素添加到TreeSet中,如果该元素已经存在,则不添加。
remove(Object o): 从TreeSet中移除指定元素。
contains(Object o): 检查TreeSet中是否包含指定元素。
size(): 返回TreeSet中元素的数量。
iterator(): 返回一个迭代器,按照元素的自然顺序或者根据提供的Comparator的顺序遍历元素。
descendingIterator(): 返回一个逆序迭代器,按照与iterator()相反的顺序遍历元素。

排序方式:

TreeSet提供了两种排序方式:自然排序(通过元素的compareTo()方法)和定制排序(通过提供Comparator对象)。
对于自然排序,元素必须实现Comparable接口,并覆写compareTo()方法。
对于定制排序,可以在创建TreeSet时传入一个实现了Comparator接口的匿名内部类对象。

总的来说,TreeSet通过红黑树数据结构保证了元素的排序和唯一性,提供了高效的插入、删除和查找操作,并支持两种排序方式:自然排序和定制排序。

TreeMap

Java中的TreeMap是一个基于红黑树(Red-Black Tree)实现的有序Map接口的实现类。它提供了键的自然排序或者根据创建时提供的Comparator进行排序的能力。以下是TreeMap底层原理的总结:
数据结构:

TreeMap使用红黑树作为其底层数据结构。红黑树是一种自平衡的二叉查找树,能够在动态数据结构中维持排序和二分搜索的性能。

排序:

TreeMap中的元素(键-值对)根据键的自然顺序进行排序,或者根据创建TreeMap时提供的Comparator进行排序。
如果元素实现了Comparable接口,并且没有提供Comparator,则使用元素的自然顺序。
如果提供了Comparator,则使用该Comparator来确定元素的顺序。

内部构成:

TreeMap由一系列节点组成,每个节点都是红黑树的节点,包含了键、值、左子节点、右子节点、父节点以及颜色属性。
这些节点按照键的排序顺序进行连接,从而保证了TreeMap的有序性。

主要操作:

put(K key, V value): 将指定的键-值对添加到TreeMap中。如果键已经存在,则替换其值。
get(Object key): 返回与指定键关联的值,如果键不存在,则返回null。
remove(Object key): 从TreeMap中移除与指定键关联的值(如果存在)。
containsKey(Object key): 检查TreeMap中是否包含指定的键。
size(): 返回TreeMap中键-值对的数量。
keySet(): 返回TreeMap中键的Set视图,其中的元素按照它们在TreeMap中的排序顺序排列。
entrySet(): 返回TreeMap中键-值对的Set视图,其中的元素按照它们在TreeMap中的排序顺序排列。

性能:

TreeMap的查找、插入和删除操作的时间复杂度通常为O(log n),其中n是TreeMap中元素的数量。
由于红黑树的平衡性,TreeMap在动态数据结构中能够保持相对稳定的性能。

非同步性:

TreeMap是非同步的。如果多个线程同时访问和修改TreeMap,并且至少有一个线程在结构上修改了映射(不包括仅仅修改值),则必须在外部同步。这通常通过包装对象(或集合的自然封装)在Collections.synchronizedSortedMap方法中来实现。

总结来说,TreeMap通过红黑树数据结构保证了元素的排序和高效的查找、插入、删除操作,并支持自然排序和定制排序两种方式。然而,由于它是非同步的,因此在多线程环境中使用时需要额外的同步措施。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/605328.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C语言—深入理解指针(2)

1.数组名的理解 不难发现,数组名就是数组首元素的地址。 但是有两个例外: 1.sizeof(数组名) 这里的数组名表示整个数组,计算的是整个数组的大小,单位是字节。 2.&数组名 这里的数组名也表示整个数…

MacOS miniconda安装方法

打开macos “终端” 应用 执行命令 mkdir -p ~/miniconda3curl https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/Miniconda3-latest-MacOSX-arm64.sh -o ~/miniconda3/miniconda.shbash ~/miniconda3/miniconda.sh -b -u -p ~/miniconda3rm -rf ~/miniconda3/mini…

CPU基本知识点

目录 1.概念 2.分类 3.运作原理 4.指令系统 1.概念 CPU:英文Central Processing Unit,即中央处理器。 解释和执行指令的功能单元,它是计算机的中枢神经系统(即核心)。 是计算机最核心的部件,主要是运算…

嵌入式数据库SQLite 3配置使用详细笔记教程

0、惨痛教训 随着管理开发的项目体积越来越庞大,产品系统涉及的数据量也越来越多,并且伴随着项目不久就要交付给甲方了。如果项目的数据信息没有被妥善管理,后期设备的运行状态、操作状况等数据流信息不能被溯源,当出现了一些特殊…

【35分钟掌握金融风控策略16】贷前风控策略详解-1

目录 贷前风控策略详解 贷前风控目标 精准审核申请贷款客户资质 对申请贷款客户进行合理定额 对申请贷款客户进行合理定价 推动实现利润最大化 贷前风控数据源 客户贷款时提供的数据 贷前风控策略详解 俗话说,良好的开端是成功的一半,而贷前是风…

C++新手村指南:入门基础

目录 C概念 C发展史 C关键字(C98) 命名空间 命名空间的定义 命名空间的使用 C中的输入&&输出 缺省参数 缺省参数的概念 缺省参数的分类 函数重载 函数重载概念 函数重载实现 引用 引用的概念 引用的特性 常引用 引用的使用场景…

基于单片机的小型自动浇灌系统设计

摘 要:以单片机为主控芯片,结合传感器和计算机,搭建了一套智能化的浇灌系统;利用LabVIEW 设计并编写了基于状态机程序架构的上位机软件,实现了友好的用户交互界面,实时测量、显示与记录等功能,并由主控芯片进行浇灌。经测试,本系统具有结构简单,研制成本低,运…

详细介绍一下PointPillars算法的网络结构

PointPillars是一种用于3D目标检测的算法,它主要使用了点云数据和深度学习模型。 PointPillars算法的网络结构主要可以分为三个主要阶段: Pillar Feature Net(点云特征处理网络):此阶段的主要任务是将输入的点云数据转…

回答篇:测试开发高频面试题目

引用之前文章:《测试开发高频面试题目》 https://blog.csdn.net/qq_41214208/article/details/138193469?spm1001.2014.3001.5502 本篇文章是回答篇(持续更新中) 1. 什么是测试开发以及其在软件开发流程中的作用。 a. 测试开发是指测试人员或…

Java:Servlet详解

目录 一、什么是Servlet 二、Servlet原理 Servlet的生命周期 三、 Servlet注释 WebServlet 一、什么是Servlet Servlet是JavaWeb开发的一种技术,Servlet程序需要部署在Servlet容器(服务端)中才能运行,常见的Servlet容器有Tom…

【C++】环境搭建CentOS Clion报错Unsupported git Version 1.8.3.1

【C】环境搭建Clion-Unsupported git Version 1.8.3.1 Git升级步骤1.卸载旧版本2.安装依赖3.下载git最新版本包4.解压git文件包5.编译文件5.将git加入环境变量6.验证git版本 如上图所示,报错Unsupported git Version 1.8.3.1 At least 2.17.0 is required 报错意思…

windows驱动开发-inf文件(一)

驱动总是和inf文件相关,在WinDDK的时候,许多inf文件都需要开发工程师手动编写,不过,现在已经可以使用inx文件来生成inf文件了,它经常用于驱动的安装和卸载;不过,并不是所有的驱动都需要使用inf文…

小白修复msvcp140.dll丢失的解决方法,一键修复丢失的dll文件

在我们使用电脑时,常常会碰到各种烦人的状况。比方说,当我们期待畅玩游戏时,可能会突然遭遇一则令人沮丧的提示:“打开游戏缺少msvcp140.dll文件”。这个问题会给我们带来困扰和不愉快,但庆幸的是,有多种解…

UE4_Water插件_Buoyancy组件使用

water插件提供了一个浮力Actor蓝图类。 需要注意的几个问题: 1、StaticMesh需要替换根组件。 2、需要模拟物理设置质量。 3、需要添加浮力组件,设置浮力点,应用水中牵引力。 4、最重要的是需要激活——自动启用。 5、调水波长的地方 双击图片…

【JavaScript】内置对象 - Date 日期对象 ④ ( 制作倒计时页面 )

文章目录 一、倒计时页面实现1、需求分析2、计算秒数3、计算倒计时时间的 天 / 时 / 分 / 秒4、页面中显示倒计时时间 二、完整代码示例1、完整代码2、执行结果 Date 日期对象参考文档 : https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Da…

北京大学肖臻老师《区块链技术与应用》P16(状态树)和P17(交易树和收据树)

1️⃣ 参考 北京大学肖臻老师《区块链技术与应用》 P16 - ETH状态树篇P17 - ETH交易树和收据树篇 部分文字和图片 北京大学肖臻老师《区块链技术与应用》公开课笔记18——ETH数据结构篇2(状态树2)北京大学肖臻老师《区块链技术与应用》公开课笔记19——ETH数据结构篇3(交易树和…

入门视频剪辑:视频合并不再难,批量嵌套合并的简单步骤

在数字媒体时代,视频剪辑已成为一项基本技能。无论是制作家庭电影、公司宣传片还是在线教育内容,视频剪辑都扮演着重要角色。对于初学者来说,视频剪辑可能看起来有些复杂,但掌握了正确的步骤和技巧后,你会发现它其实并…

Angular中的路由

Angular中的路由 文章目录 Angular中的路由前言一、创建路由二、创建多个组件路由三、创建子路由四、创建多个组件子路由 前言 在Angular中,路由是用于在不同的视图和组件之间导航的机制。Angular提供了一种强大的路由机制来管理单页应用(SPA&#xff0…

十九、分布式数据库MyCat

目录 一、概述 1、MyCat是什么? 2、原理: 3、能干什么 1、读写分离 2、数据分片 3、多数据源整合 4、Mycat监控 4、安装部署 1、环境准备 2、安装 3、Mycat配置详解 1、server.xml user 标签 2、schema.xml schema标签: table标签&…

实践遥感卫星场景海洋船只检测,基于YOLOv8全系列【n/s/m/l/x】参数模型开发构建卫星遥感场景下海洋海面船只检测识别系统

遥感相关的实践在我们前面的系列博文中也有相关的一些实践,胡药师基于MASTAR数据集开发构建对应的目标检测系统在前文也有一些介绍,感兴趣的话可以自行移步阅读即可: 《基于YOLOv7开发构建MSTAR雷达影像目标检测系统》 《基于yolov5n的轻量…
最新文章