Java TreeMap

TreeMap 是一个基于 key 有序的 key value 散列表。

  • map 根据其键的自然顺序排序,或者根据 map 创建时提供的 Comparator 排序
  • 不是线程安全的
  • key 不可以存入null
  • 底层是基于红黑树实现的

TreeMap 的类结构图:
在这里插入图片描述

  1. 实现了 NavigableMap 接口,NavigableMap 又实现了Map接口,提供了导航相关的方法。
  2. 继承了 AbstractMap,该方法实现 Map 操作的骨干逻辑。
  3. 实现了 Cloneable 接口,标记该类支持 clone 方法复制
  4. 实现了 Serializable 接口,标记该类支持序列化

构造方法

TreeMap() // 使用键的自然排序构造一个新的空树映射。
TreeMap(Comparator<? super K> comparator) // 构造一个新的空树映射,根据给定的比较器排序。
TreeMap(Map<? extends K,? extends V> m) // 构造一个新的树映射,包含与给定映射相同的映射,按照键的自然顺序排序。
TreeMap(SortedMap<K,? extends V> m) // 构造一个新的树映射,包含相同的映射,并使用与指定排序映射相同的顺序。

关键方法

SortedMap 接口:

Comparator<? super K> comparator() // 返回用于排序此映射中的键的比较器,如果此映射使用其键的自然排序,则返回 null。
Set<Map.Entry<K,V>> entrySet() // 返回此映射中包含的映射的 Set 视图。
K firstKey() // 返回当前映射中的第一个(最低)键。
K lastKey() // 返回当前映射中的最后(最高)键。

NavigableMap 接口:

Map.Entry<K,V> ceilingEntry(K key) 返回与大于或等于给定键的最小键相关联的键值映射,如果没有这样的键则返回 nullK ceilingKey(K key) 返回大于或等于给定键的最小键,如果没有这样的键,则返回 nullNavigableMap<K,V> descendingMap() 返回此映射中包含的映射的倒序视图。
Map.Entry<K,V> firstEntry() 返回与该映射中最小的键关联的键值映射,如果映射为空,则返回 nullMap.Entry<K,V> floorEntry(K key) 返回与小于或等于给定键的最大键相关联的键值映射,如果没有这样的键则返回 nullSortedMap<K,V> headMap(K toKey) 返回该映射中键严格小于 toKey 的部分的视图。
Map.Entry<K,V> higherEntry(K key) 返回与严格大于给定键的最小键关联的键值映射,如果没有这样的键,则返回 nullMap.Entry<K,V> lastEntry() 返回与此映射中最大键关联的键值映射,如果映射为空,则返回 nullMap.Entry<K,V> lowerEntry(K key) 返回与严格小于给定键的最大键关联的键值映射,如果没有这样的键,则返回 nullMap.Entry<K,V> pollFirstEntry() 删除并返回与该映射中最小的键关联的键值映射,如果映射为空,则返回 nullMap.Entry<K,V> pollLastEntry() 删除并返回与此映射中最大键关联的键值映射,如果映射为空,则返回 nullSortedMap<K,V> subMap(K fromKey, K toKey) 返回该映射中键范围从 fromKey(包含)toKey(独占)的部分的视图。
SortedMap<K,V> tailMap(K fromKey) 返回该映射中键大于或等于 fromKey 的部分的视图。

验证顺序性

@Testpublic void test1() {Map<Integer, String> treeMap = new TreeMap<>();treeMap.put(16, "a");treeMap.put(1, "b");treeMap.put(4, "c");treeMap.put(3, "d");treeMap.put(8, "e");// 遍历System.out.println("默认排序:");treeMap.forEach((key, value) -> {System.out.println("key: " + key + ", value: " + value);});// 构造方法传入比较器Map<Integer, String> tree2Map = new TreeMap<>((o1, o2) -> o2 - o1);tree2Map.put(16, "a");tree2Map.put(1, "b");tree2Map.put(4, "c");tree2Map.put(3, "d");tree2Map.put(8, "e");// 遍历System.out.println("倒序排序:");tree2Map.forEach((key, value) -> {System.out.println("key: " + key + ", value: " + value);});}

验证不能存储 null

@Testpublic void test2() {Map<Integer, String> treeMap = new TreeMap<>();treeMap.put(null, "a");}

验证 NavigableMap 相关方法

@Testpublic void test3() {NavigableMap<Integer, String> treeMap = new TreeMap<>();treeMap.put(16, "a");treeMap.put(1, "b");treeMap.put(4, "c");treeMap.put(3, "d");treeMap.put(8, "e");// 获取大于等于 5 的 keyInteger ceilingKey = treeMap.ceilingKey(5);System.out.println("ceilingKey 5 is " + ceilingKey);// 获取最大的 keyInteger lastKey = treeMap.lastKey();System.out.println("lastKey is " + lastKey);}

核心机制

实现原理
TreeMap 的底层是如何维护 key 的顺序呢?答案就是基于红黑树实现的。

红黑树是一颗 自平衡排序二叉树
二叉树 很容易理解,就是一棵树分俩叉。
在这里插入图片描述
上面这颗就是一颗最普通的二叉树。但是你会发现看起来不那么美观,因为你以 H 为根节点,发现左右两边高低不平衡,高度相差达到了 2。于是出现了平衡二叉树,使得左右两边高低差不多。

平衡二叉树
在这里插入图片描述
不管是从任何一个字母为根节点,左右两边的深度差不了 2,最多是 1。这就是平衡二叉树。把字母变成数字,还要保持这种特性怎么办呢?于是又出现了平衡二叉排序树。

平衡二叉排序树
在这里插入图片描述

不管是从长相(平衡),还是从规律(排序)感觉这棵树超级完美。但是有一个问题,那就是在增加删除节点的时候,你要时刻去让这棵树保持平衡,需要做太多的工作了,旋转的次数超级多,于是乎出现了红黑树。

红黑树
在这里插入图片描述
这就是传说中的红黑树,和平衡二叉排序树的区别就是每个节点涂上了颜色,他有下列五条性质:

每个节点都只能是红色或者黑色
根节点是黑色
每个叶节点(NIL节点,空节点)是黑色的。
如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质有什么优点呢?就是插入效率超级高。因为在插入一个元素的时候,最多只需三次旋转,O(1)的复杂度,但是有一点需要说明他的查询效率略微逊色于平衡二叉树,因为他比平衡二叉树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较。如何去旋转呢?如下图所示。

首先是左旋:

在这里插入图片描述

然后是右旋:
在这里插入图片描述

红黑树更详细的内容可以参考这篇文章:segmentfault.com/a/119000001…

源码解析
成员变量

//这是一个比较器,方便插入查找元素等操作
private final Comparator<? super K> comparator;
//红黑树的根节点:每个节点是一个Entry
private transient Entry<K,V> root;
//集合元素数量
private transient int size = 0;
//集合修改的记录
private transient int modCount = 0;
comparator是一个排序器,作为key的排序规则
root是红黑树的根节点,说明的确底层用的红黑树作为数据结构。
static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;//左子树Entry<K,V> left;//右子树Entry<K,V> right;//父节点Entry<K,V> parent;//每个节点的颜色:红黑树属性。boolean color = BLACK;Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}public K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {V oldValue = this.value;this.value = value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>)o;return valEquals(key,e.getKey()) && valEquals(value,e.getValue());}public int hashCode() {int keyHash = (key==null ? 0 : key.hashCode());int valueHash = (value==null ? 0 : value.hashCode());return keyHash ^ valueHash;}public String toString() {return key + "=" + value;}}

查找get方法
TreeMap基于红黑树实现,而红黑树是一种自平衡二叉查找树,所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的,先将目标值和根节点的值进行比较,如果目标值小于根节点的值,则再和根节点的左孩子进行比较。如果目标值大于根节点的值,则继续和根节点的右孩子比较。在查找过程中,如果目标值和二叉树中的某个节点值相等,则返回 true,否则返回 false。TreeMap 查找和此类似,只不过在 TreeMap 中,节点(Entry)存储的是键值对<k,v>。在查找过程中,比较的是键的大小,返回的是值,如果没找到,则返回null。TreeMap 中的查找方法是get。

public V get(Object key) {//调用 getEntry方法查找Entry<K,V> p = getEntry(key);return (p==null ? null : p. value);
}final Entry<K,V> getEntry(Object key) {/ 如果比较器为空,只是用key作为比较器查询if (comparator != null) return getEntryUsingComparator(key);if (key == null)throw new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;// 取得root节点Entry<K,V> p = root;//核心来了:从root节点开始查找,根据比较器判断是在左子树还是右子树while (p != null) {int cmp = k.compareTo(p.key );if (cmp < 0)p = p. left;else if (cmp > 0)p = p. right;elsereturn p;}

插入put方法
我们来看下关键的插入方法,在插入时候是如何维护key的。

public V put(K key, V value) {Entry<K,V> t = root;// 1.如果根节点为 null,将新节点设为根节点if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}//如果root不为null,说明已存在元素 int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;//如果比较器不为null 则使用比较器if (cpr != null) {//找到元素的插入位置do {parent = t;cmp = cpr.compare(key, t.key);//当前key小于节点key 向左子树查找if (cmp < 0)t = t.left;//当前key大于节点key 向右子树查找else if (cmp > 0)t = t.right;else//相等的情况下 直接更新节点值return t.setValue(value);} while (t != null);}//如果比较器为null 则使用默认比较器else {//如果key为null  则抛出异常if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;//找到元素的插入位置do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);//根据比较结果决定插入到左子树还是右子树if (cmp < 0)parent.left = e;elseparent.right = e;//保持红黑树性质,进行红黑树的旋转等操作fixAfterInsertion(e);size++;modCount++;return null;}

比较关键的就是fixAfterInsertion方法, 看懂这个方法需要你对红黑树的机制比较了解。

private void fixAfterInsertion(Entry<K,V> x) {// 将新插入节点的颜色设置为红色x. color = RED;// while循环,保证新插入节点x不是根节点或者新插入节点x的父节点不是红色(这两种情况不需要调整)while (x != null && x != root && x. parent.color == RED) {// 如果新插入节点x的父节点是祖父节点的左孩子if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {// 取得新插入节点x的叔叔节点Entry<K,V> y = rightOf(parentOf (parentOf(x)));// 如果新插入x的父节点是红色if (colorOf(y) == RED) {// 将x的父节点设置为黑色setColor(parentOf (x), BLACK);// 将x的叔叔节点设置为黑色setColor(y, BLACK);// 将x的祖父节点设置为红色setColor(parentOf (parentOf(x)), RED);// 将x指向祖父节点,如果x的祖父节点的父节点是红色,按照上面的步奏继续循环x = parentOf(parentOf (x));} else {// 如果新插入x的叔叔节点是黑色或缺少,且x的父节点是祖父节点的右孩子if (x == rightOf( parentOf(x))) {// 左旋父节点x = parentOf(x);rotateLeft(x);}// 如果新插入x的叔叔节点是黑色或缺少,且x的父节点是祖父节点的左孩子// 将x的父节点设置为黑色setColor(parentOf (x), BLACK);// 将x的祖父节点设置为红色setColor(parentOf (parentOf(x)), RED);// 右旋x的祖父节点rotateRight( parentOf(parentOf (x)));}} else { // 如果新插入节点x的父节点是祖父节点的右孩子和上面的相似Entry<K,V> y = leftOf(parentOf (parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf (x), BLACK);setColor(y, BLACK);setColor(parentOf (parentOf(x)), RED);x = parentOf(parentOf (x));} else {if (x == leftOf( parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf (x), BLACK);setColor(parentOf (parentOf(x)), RED);rotateLeft( parentOf(parentOf (x)));}}}// 最后将根节点设置为黑色root.color = BLACK;
}

删除remove方法
删除remove是最复杂的方法。

public V remove(Object key) {// 根据key查找到对应的节点对象Entry<K,V> p = getEntry(key);if (p == null)return null;// 记录key对应的value,供返回使用V oldValue = p. value;// 删除节点deleteEntry(p);return oldValue;
}
private void deleteEntry(Entry<K,V> p) {modCount++;//元素个数减一size--;// 如果被删除的节点p的左孩子和右孩子都不为空,则查找其替代节if (p.left != null && p. right != null) {// 查找p的替代节点Entry<K,V> s = successor (p);p. key = s.key ;p. value = s.value ;p = s;}Entry<K,V> replacement = (p. left != null ? p.left : p. right);if (replacement != null) { // 将p的父节点拷贝给替代节点replacement. parent = p.parent ;// 如果替代节点p的父节点为空,也就是p为跟节点,则将replacement设置为根节点if (p.parent == null)root = replacement;// 如果替代节点p是其父节点的左孩子,则将replacement设置为其父节点的左孩子else if (p == p.parent. left)p. parent.left   = replacement;// 如果替代节点p是其父节点的左孩子,则将replacement设置为其父节点的右孩子elsep. parent.right = replacement;// 将替代节点p的left、right、parent的指针都指向空p. left = p.right = p.parent = null;// 如果替代节点p的颜色是黑色,则需要调整红黑树以保持其平衡if (p.color == BLACK)fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.// 如果要替代节点p没有父节点,代表p为根节点,直接删除即可root = null;} else {// 如果p的颜色是黑色,则调整红黑树if (p.color == BLACK)fixAfterDeletion(p);// 下面删除替代节点pif (p.parent != null) {// 解除p的父节点对p的引用if (p == p.parent .left)p. parent.left = null;else if (p == p.parent. right)p. parent.right = null;// 解除p对p父节点的引用p. parent = null;}}}

最终还是落到了对红黑树节点的删除上,需要维持红黑树的特性,做一系列的工作。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MATLAB的编程与应用,匿名函数、嵌套函数、蒙特卡洛法的掌握与使用

目录 1.匿名函数 1.1.匿名函数的定义与分类 1.2.匿名函数在积分和优化中应用 2.嵌套函数 2.1.嵌套函数的定义与分类 2.2.嵌套函数彼此调用关系 2.3.嵌套函数在积分和微分中应用 3.微分和积分 4.蒙特卡洛法 4.1.圆周率的模拟 4.2.计算N重积分&#xff08;均匀分布&am…

20道高频JavaScript面试题快问快答

※其他的快问快答&#xff0c;看这里&#xff01; 10道高频Qiankun微前端面试题快问快答 10道高频webpack面试题快问快答 20道高频CSS面试题快问快答 20道高频JavaScript面试题快问快答 30道高频Vue面试题快问快答 面试中的快问快答 快问快答的情景在面试中非常常见。 在面试过…

竞赛选题 深度学习疲劳驾驶检测 opencv python

文章目录 0 前言1 课题背景2 实现目标3 当前市面上疲劳驾驶检测的方法4 相关数据集5 基于头部姿态的驾驶疲劳检测5.1 如何确定疲劳状态5.2 算法步骤5.3 打瞌睡判断 6 基于CNN与SVM的疲劳检测方法6.1 网络结构6.2 疲劳图像分类训练6.3 训练结果 7 最后 0 前言 &#x1f525; 优…

idea 2023 设置启动参数、单元测试启动参数

找到上方的editconfigration&#xff0c; 如下图&#xff0c;如果想在启动类上加&#xff0c;就选择springboot&#xff0c;如果想在单元测试加&#xff0c;就选择junit 在参数栏设置参数&#xff0c;多个参数以空格隔开 如果没有这一栏&#xff0c;就选择就可以了。 然后&…

数字马力笔试面试复盘

笔试——10月9日19&#xff1a;00 单选&#xff1a;30题 16.如何获取AJAX 请求的响应状态码? A通过AJAX对象的 statusCode 属性获取 B通过AJAX对象的responseText 属性获取C通过AJAX对象的status 属性获取 D通过AJAX对象的responseCode属性获取 答案&#xff1a;可以通过AJAX…

回收站清空了怎么恢复?数据恢复的 6 种方法

众所周知&#xff0c;计算机中的回收站是一个存储空间&#xff0c;用于存储从计算机系统中删除的所有文件、文件夹或数据。它是大多数计算机系统&#xff08;包括Windows、Mac等&#xff09;上的必备功能。当从计算机中删除文件或文件夹时&#xff0c;它会在回收站中存储指定的…

京东数据分析:2023年Q3户外鞋服市场分析报告(冲锋衣行业销售数据分析)

从露营、骑行、徒步、桨板、垂钓、飞盘、滑雪到如今的city walk&#xff0c;近两年户外运动已经成为了年轻人新的生活方式。户外运动的爆发也刺激了人们对于鞋服在穿搭、场景化、专业性功能等方向的需求&#xff0c;户外鞋服市场迎来增长。 而全国性的降温则带给目前的户外鞋服…

七个优秀微服务跟踪工具

随着微服务架构复杂性的增加&#xff0c;在问题出现时确定问题的根本原因变得更具挑战性。日志和指标为我们提供了有用的信息&#xff0c;但并不能提供系统的完整概况。这就是跟踪的用武之地。通过跟踪&#xff0c;开发人员可以监控微服务之间的请求进度&#xff0c;从而使他们…

关于Android Studio 同步Gradle失败的解决方案

&#xff08;1&#xff09;打开Android Studio的Settings找到Gradle的目录 &#xff08;2&#xff09;打开本地文件目录&#xff0c;找到对应的gradle版本&#xff0c;可以通过Index of /gradle/ 下载gradle压缩包。把目录中gradle-7.0.2-bin\一堆字符\ 下 的.lck 和.part文…

MATLAB中Arrow 属性说明

目录 颜色和样式 位置 Arrow 属性是箭头的外观和行为。 Arrow 属性控制 Arrow 对象的外观和行为。通过更改属性值&#xff0c;可以修改箭头的特定方面。使用圆点表示法查询和设置属性。 ar annotation("arrow"); c ar.Color; ar.Color "red"; 颜色和…

SpringCloudGateway--Sentinel限流、熔断降级

目录 一、概览 二、安装Sentinel 三、微服务整合sentinel 四、限流 1、流控模式 ①直接 ②关联 ③链路 2、流控效果 ①快速失败 ②Warm Up ③排队等待 五、熔断降级 1、慢调用比例 2、异常比例 3、异常数 一、概览 SpringCloudGateway是一个基于SpringBoot2.x的…

react 修改less文件后保存,内存溢出,项目崩溃问题解决

一、完整报错 一个很老的react项目&#xff0c;因为没有package-lock.json版本锁&#xff0c;导致拉下来的时候&#xff0c;安装的依赖版本冲突&#xff0c;好不容易启动起来&#xff0c;修改less文件后只要一保存&#xff0c;项目就会崩溃&#xff0c;需要重启&#xff0c;报…

一分钟秒懂人工智能对齐

文章目录 1.什么是人工智能对齐2.为什么要研究人工智能对齐3.人工智能对齐的常见方法 1.什么是人工智能对齐 人工智能对齐&#xff08;AI Alignment&#xff09;指让人工智能的行为符合人的意图和价值观。 人工智能系统可能会出现“不对齐”&#xff08;misalign&#xff09;的…

webpack提升构建速度

目录 配置优化减少 resolve 的解析把 loader 应用的文件范围缩小减少 plugin 的消耗选择合适的 devtool 使用工具thread-loaderDLLPlugin 流程优化拆分构建步骤拆分项目代码 版本更新总结 前端项目随着时间推移和业务发展&#xff0c;页面可能会越来越多&#xff0c;或者功能和…

Redis之哨兵模式

文章目录 前言什么是哨兵模式&#xff1f;1.概述2.作用3.测试4.优点5.缺点6.哨兵模式的全部配置 总结 前言 哨兵模式说白点就是&#xff1a;自动选举老大的模式。 什么是哨兵模式&#xff1f; 1.概述 主从切换技术的方法是∶当主服务器宕机后&#xff0c;需要手动把一台从服…

线性代数-Python-04:线性系统+高斯消元的实现

文章目录 1 线性系统2 高斯-jordon消元法的实现2.1 Matrix2.2 Vector2.3 线性系统 3 行最简形式4 线性方程组的结构5 线性方程组-通用高斯消元的实现5.1 global5.2 Vector-引入is_zero5.3 LinearSystem5.4 main 1 线性系统 2 高斯-jordon消元法的实现 2.1 Matrix from .Vecto…

Mac安装与配置eclipse

目录 一、安装Java&#xff1a;Mac环境配置&#xff08;Java&#xff09;----使用bash_profile进行配置&#xff08;附下载地址&#xff09; 二、下载和安装eclipse 1、进入eclipse的官网 (1)、点击“Download Packages ”​编辑 (2)、找到macOS选择符合自己电脑的框架选项…

Python之函数进阶-闭包原理

Python之函数进阶-闭包原理 闭包 自由变量&#xff1a;未在本地作用域中定义的变量&#xff0c;例如定义在内层函数外的外层函数的作用域中的变量闭包&#xff1a;就是一个概念&#xff0c;出现在嵌套函数中&#xff0c;指的是内层函数引用到了外层函数的自由变量&#xff0c…

【已解决】ModuleNotFoundError: No module named ‘sklearn‘

问题描述 Traceback (most recent call last): File "/home/visionx/nickle/temp/SimCLR/linear_evaluation.py", line 210, in <module> from sklearn.manifold import TSNE ModuleNotFoundError: No module named sklearn 解决办法 pip install numpy…