首页 > 其他分享 >TreeMap&TreeSet解析

TreeMap&TreeSet解析

时间:2024-08-24 10:15:57浏览次数:9  
标签:Cherry treeMap TreeMap Date 红黑树 put 解析 TreeSet

TreeMap

TreeSet使用适配器模式包装了TreeMap,所以只需要理解TreeMap就够了

概述

TreeMap实现了SortedMap接口,也就是说会按照顺序对Map中的元素进行排序,可以是自然顺序,也可以使用自定义比较器

TreeMap<Integer, String> treeMap = new TreeMap<>();

treeMap.put(3, "Apple");
treeMap.put(1, "Banana");
treeMap.put(4, "Cherry");
treeMap.put(2, "Date");

//打印顺序
1 => Banana
2 => Date
3 => Apple
4 => Cherry
TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> o2.compareTo(o1));

treeMap.put(3, "Apple");
treeMap.put(1, "Banana");
treeMap.put(4, "Cherry");
treeMap.put(2, "Date");


//打印顺序
4 => Cherry
3 => Apple
2 => Date
1 => Banana

底层原理

TreeMap底层通过红黑树(Red-Black tree)实现,也就意味着containsKey()get()put()remove()都有着log(n)的时间复杂度。

红黑树是一种近似平衡的二叉查找树,左子树的所有节点比根节点小,右子树的所有节点比根节点大

红黑树只能做到近似平衡,确保左右子树的高度差不会超过二者中较低那个的一倍,结构改变时需要调整树

调整过程中包括两个基本操作:

左旋和右旋

由于红黑树是一棵增强版的二叉查找树,红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似,唯一的区别是红黑树在节点删除之后可能需要进行调整

快速失败

TreeMap是一个快速失败的集合,使用modCount记录结构性修改tag

标签:Cherry,treeMap,TreeMap,Date,红黑树,put,解析,TreeSet
From: https://www.cnblogs.com/lilizzyy/p/18377454

相关文章

  • 【全面解析】大模型入门到精通指南:零基础起步,详尽教程一帖收藏!
    大模型的定义大模型是指具有数千万甚至数亿参数的深度学习模型。近年来,随着计算机技术和大数据的快速发展,深度学习在各个领域取得了显著的成果,如自然语言处理,图片生成,工业数字化等。为了提高模型的性能,研究者们不断尝试增加模型的参数数量,从而诞生了大模型这一概念。本文讨......
  • LinkedHashMap&LinkedHashSet源码解析
    LinkedHashMap概述LinkedHashSet使用适配器模式包装了LinkedHashSet一个有序的散列表,允许key为null也允许value为空,从名字上可以看出使用链表维护了有序性在元素存储时,在原来的HashMap的数组+链表的基础上,为每个元素添加了pre和next指针,构成了一个双向链表注意:内部没有使用红......
  • 【漫谈C语言和嵌入式027】探索信号处理的秘密:低通滤波器与高通滤波器的深度解析
            在嵌入式系统和数字信号处理领域,滤波器(Filter)是至关重要的工具。它们是用于处理和优化信号的基础组件,能够有效地控制信号的频率分布。滤波器的类型多种多样,其中最为基础且常用的便是低通滤波器(Low-PassFilter,LPF)和高通滤波器(High-PassFilter,HPF)。本文将......
  • Stable Diffusion 与 DALL·E3 的深度解析
    一、StableDiffusion的全方位解读 StableDiffusion是一款令人瞩目的AI绘画工具,其显著特点之一便是开源免费。这意味着用户无需支付费用即可自由使用和修改,为广大创作者提供了极大的便利。然而,要想充分发挥其功能,对电脑硬件有一定要求。显卡方面,建议使用NVIDIA系列,......
  • 深入解析HarmonyOS中的媒体查询及其高级用法
    在移动应用开发中,响应式设计是一个关键要素。HarmonyOS提供了一整套媒体查询功能,可以让开发者根据设备类型、屏幕尺寸、方向等条件动态调整应用的布局和样式。本文将深入探讨HarmonyOS中的媒体查询功能,展示其高级用法,帮助你构建更灵活的用户界面。媒体查询在HarmonyOS中的......
  • 【boost_search】3.为什么去标签和解析文件的代码框架
    一.什么是标签?我们之前获取的源数据都是html数据,在一个html中我们看到<!DOCTYPEhtmlPUBLIC"-//W3C//DTDHTML4.01Transitional//EN""http://www.w3.org/TR/html4/loose.dtd">2<html>3<head>4<metahttp-equiv="Content......
  • Swift 中的动画魔法:Core Animation 深度解析
    标题:Swift中的动画魔法:CoreAnimation深度解析引言在现代应用程序开发中,动画不仅增加了用户界面的吸引力,还提升了用户体验。Swift语言结合了CoreAnimation框架,为开发者提供了强大的工具来创建平滑和复杂的动画效果。本文将深入探讨如何在Swift中使用CoreAnimati......
  • Objective-C中的字典探秘:NSDictionary与NSMutableDictionary全解析
    标题:Objective-C中的字典探秘:NSDictionary与NSMutableDictionary全解析在Objective-C中,NSDictionary和NSMutableDictionary是两种常用的集合类型,它们用于存储键值对(key-valuepairs)。尽管它们在功能上有许多相似之处,但它们之间的区别对于开发者来说是至关重要的。本文将详......
  • Android开发 - Looper 类处理异步任务和消息解析
    什么是LooperLooper是一个非常重要的概念,它与线程、消息队列和处理异步任务密切相关。是Android中用于管理线程的消息循环的类。它与线程中的MessageQueue结合工作,用于处理异步任务和消息Looper的主要概念消息队列(MessageQueue)一个用于存放要处理的消息和任务的队......
  • Android开发 - BluetoothGattCallback 类处理蓝牙 (BLE) 设备的连接和通信解析
    BluetoothGattCallback是什么BluetoothGattCallback是一个抽象类,用于接收BLE设备的各种回调事件。这些事件包括连接状态的变化、服务的发现、特性的读取和写入等BluetoothGattCallback的主要方法onConnectionStateChange(BluetoothGattgatt,intstatus,intnewStat......