今天尝试刨一下TreeMap的祖坟。

底层结构对比

先来看一下与HashMap、LinkedHashMap和TreeMap的对比，同时就当是复习一下：

  1. HashMap使用数组存储数据，并使用单向链表结构存储hash冲突数据，同一个冲突桶中数据量大的时候（默认超过8）则使用红黑树存储冲突数据。
  2. LinkedHashMap使用数组+双向链表存储数据，冲突数据存储方式同HashMap。
  3. TreeMap使用红黑树存储数据，注意是直接使用红黑树，不使用table数组。

关于排序特性

  1. HashMap无顺序，不能保持顺序。
  2. LinkedHashMap能保持写入的顺序，遍历的时候可以按照写入顺序获取数据。
  3. TreeMap是有序的Map，自动按照key值排序存储，遍历时获取到的是有序数据。

需要注意LinkedHashMap和TreeMap在顺序方面的区别，LinkedHashMap只能保持写入顺序，从“排序”的角度讲，他实际是无序的。

只有TreeMap是可以实现自动排序的。

TreeMap按照什么排序？

TreeMap底层支持两种排序方式：

  1. TreeMap对象实例化时传入comparator对象。
  2. key值对象实现Comparable接口。

如果以上两点都不能满足的话，向TreeMap对象put数据的时候会抛出运行时异常。

比如TreeMap<String,Object>，由于String实现了Comparable接口，所以是没有问题的。

但是如果自定义的对象，没有实现Comparable接口，同时在TreeMap实例化的时候没有设置comparator对象，则该TreeMap对象实际是不可用的。

TreeMap是否可以存储null？

指的是，是否可以存储key为空的数据？我们知道HashMap是可以支持唯一一个null对象的。

很多人都说不可以，但是我觉得有条件可以，但是没做测试（因为感觉则个问题其实有点扯）。

条件是实例化TreeMap对象的时候指定comparator对象，同时，该comparator对象的compare方法可以支持null。

研究TreeMap的put源码，也可以发现对以上说法的支持：

Comparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {if (key == null)throw new NullPointerException();...省略若干代码

可以发现如果有comparator的话，put方法不会立即抛出异常。但是如果comparator对象的compare方法不能支持null的话，一样会抛出异常。

put方法

由于TreeMap支持自动排序，所以put方法会检查是否满足规则。

不满足排序规则，抛出异常。

否则，按照红黑树算法规则要求，创建红黑树，存储数据。

所以这里就涉及到一个重要的数据结构：红黑树。

二叉树BST & 平衡二叉树AVL

红黑树是树结构的一种，是比二叉树和平衡二叉树更加复杂的一种数据结构。所以我们先从简单的入手，了解一下二叉树。

树结构其实是实现了子排序的一种数据结构，我们说到的树结构一般指的是二叉树、也叫二叉搜索树（BST - Binary Search Tree），定义：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

二叉搜索树的插入、搜索操作所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要O(logn)的时间。

二叉搜索树的特性并不能保证他是平衡的，也就是说，极端情况下，一颗二叉搜索树从根节点开始，只有左节点、没有右节点（比如一直按照从大到小或者相反顺序插入二叉树），这种情况下，二叉树就蜕变成了链表，查询时间复杂度就会下降为O(n)。

改善二叉树这一缺点的经典数据结构是平衡二叉树AVL（Adelson-Velsky and Landis Tree，以两位发明者命名）。平衡二叉树的特性：

1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

一颗平衡二叉树在新节点插入之后可能会失衡，包括以下四种场景：

左左失衡LL

插入的数据在左侧不平衡树的左侧，这种情况下需要进行右旋操作再次平衡：
在这里插入图片描述
我们需要记住一个概念：平衡二叉树失衡之后通过旋转动作使得它再次平衡的处理，只是针对失衡的子树、不需要对整个树进行操作。比如上图新的节点1加入之后，导致pivot节点7一侧的树失衡，我们需要处理的是包含pivot节点的root节点的左侧树这一部分子树，右侧节点18下即使有再多的节点，也不需要处理。

右旋操作的实质是：以pivot节点7为支点做顺时针旋转，旋转之后7变为自己原来父节点的父节点、7的左节点不变，7的右节点变为7原来的父节点的左节点。

右右失衡RR

插入的节点在右侧不平衡树的右侧，这种情况下需要左旋：
在这里插入图片描述
左旋操作的实质是：以pivot节点18为支点做逆时针旋转，旋转之后18变为自己原来父节点的父节点、18的右节点不变，18的左节点变为18原来的父节点的右节点。

左右失衡LR

插入的新节点在左侧不平衡树的右侧。先左旋再右旋
在这里插入图片描述

右左失衡LR

插入的节点在右侧不平衡树的左侧，先右旋再左旋：
在这里插入图片描述
平衡二叉树具有：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1 这一特性，这一严格条件会导致每次插入新节点之后总会大概率破坏平衡、从而必须要通过上述的旋转操作使其再次达到平衡，旋转操作会影响数据插入的效率。

红黑树可以解决这一问题。

红黑树

红黑树是一种带颜色（节点是红色或者黑色）的平衡二叉树，具有以下特性：
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

红黑树新加入节点的颜色默认为黑色，因为根据红黑树性质4，每个红色节点的两个子节点都是黑色。所以，新加入节点如果是黑色的话，可以检查其父节点如果是红色的话，可以自动满足性质4从而减少再平衡操作、提高数据加入的效率。这一点可以通过TreeMap的put方法源码得到验证：

public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {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;}

put方法前半部分逻辑比较简单，为新节点找到合适的位置加入，之后会调用fixAfterInsertion检查是否破坏了红黑树的规则从而需要执行再平衡操作：

private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(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 == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {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;}

fixAfterInsertion方法首先判断其父节点是红色的话，则不做任何操作。

get方法

根据红黑树查找算法查找并返回数据，红黑树是平衡二叉树，查询时间复杂度为O(log(n))。

key遍历

比如调用TreeMap.keySet方法，采用遍历二叉树算法，按照从小到大的顺序返回所有key值组成的循环器。

我该使用哪一个？

需要用到Map的时候，到底该使用哪一个的问题：

  1. 我只需要一个存储数据的容器，没有具体要求的话，用HashMap。
  2. 存储数据后，有按照存储顺序获取数据的需求，采用LinkedHashMap。
  3. 希望存储数据的同时，帮助实现自动排序，采用TreeMap。

性能的问题，其实几乎不需要考虑，不过我们还是需要知道：

  1. HashMap和LinkedHashMap查询速度快，理想情况下时间复杂度几乎是O(1)。
  2. HashMap写入速度最快，LinkedHashMap写入速度与HashMap几乎相同，TreeMap写入速度最慢（理论上，实际数据量小的情况下未必慢）。
  3. 遍历速度相差无几，理论上HashMap会慢一点，因为需要遍历空桶。

并发问题尚待研究，但是我们清楚地知道，以上三种均不具备线程安全性。

好梦！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/diannao/89033.shtml
繁体地址，请注明出处：http://hk.pswp.cn/diannao/89033.shtml
英文地址，请注明出处：http://en.pswp.cn/diannao/89033.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

华为云Flexus+DeepSeek征文｜基于Dify构建拍照识题智能学习助手

华为云Flexus+DeepSeek征文｜基于Dify构建拍照识题智能学习助手

华为云FlexusDeepSeek征文&#xff5c;基于Dify构建拍照识题智能学习助手 一、构建拍照识题智能学习助手前言二、构建拍照识题智能学习助手环境2.1 基于FlexusX实例的Dify平台2.2 基于MaaS的模型API商用服务 三、构建拍照识题智能学习助手实战3.1 配置Dify环境3.2 配置Dify工具…
阅读更多...
题解：CF2120E Lanes of Cars

题解：CF2120E Lanes of Cars

根据贪心&#xff0c;不难想到每次会把最长队伍末尾的那辆车移动到最短队伍的末尾。但由于 k k k 的存在&#xff0c;会导致一些冗余移动的存在。设需要挪动 C C C 辆车&#xff0c;则怒气值可以表示为 f ( C ) k C f(C) kC f(C)kC&#xff0c;其中 f ( C ) f(C) f(C) 是…
阅读更多...
Excel基础：选择和移动

Excel基础：选择和移动

本文演示Excel中基础的选择和移动操作&#xff0c;并在最后提供了一张思维导图&#xff0c;方便记忆。 文章目录 一、选择1.1 基础选择1.1.1 选择单个单元格1.1.2 选择连续范围 1.2 行列选择1.2.1 选择整行整列1.2.2 选择多行多列 1.3 全选1.3.1 全选所有单元格1.3.2 智能选择…
阅读更多...
Java面试宝典：基础四

Java面试宝典：基础四

80. int vs Integer 维度intInteger类型基本数据类型（8种之一）包装类默认值0null应用场景性能敏感场景（计算密集）Web表单、ORM框架（区分null和0）特殊能力无提供工具方法（如parseInt()）和常量（如MAX_VALUE）示例：
阅读更多...
RabbitMQ + JMeter 深度集成指南：中间件性能优化全流程解析！

RabbitMQ + JMeter 深度集成指南：中间件性能优化全流程解析！

在 2025 年的数字化浪潮中&#xff0c;中间件性能直接决定系统的稳定性和用户体验&#xff0c;而 RabbitMQ 作为消息队列的“老大哥”&#xff0c;在分布式系统中扮演着关键角色。然而&#xff0c;高并发场景下&#xff0c;消息堆积、延迟激增等问题可能让系统不堪重负&#xf…
阅读更多...
uniapp image引用本地图片不显示问题

uniapp image引用本地图片不显示问题

1. uniapp image引用本地图片不显示问题 在uniapp 开发过程中采用image引入本地资源图片。 1.1. 相对路径和绝对路径问题 在UniApp中开发微信小程序时&#xff0c;引入图片时&#xff0c;相对路径和绝对路径可能会有一些差异。这差异主要涉及到小程序和UniApp框架的文件结构、…
阅读更多...
论文阅读：arxiv 2025 ThinkSwitcher: When to Think Hard, When to Think Fast

论文阅读：arxiv 2025 ThinkSwitcher: When to Think Hard, When to Think Fast

总目录 大模型安全相关研究&#xff1a;https://blog.csdn.net/WhiffeYF/article/details/142132328 ThinkSwitcher: When to Think Hard, When to Think Fast https://arxiv.org/pdf/2505.14183#page2.08 https://www.doubao.com/chat/10031179784579842 文章目录 速览一、…
阅读更多...
智能体记忆原理-prompt设计

智能体记忆原理-prompt设计

智能体记忆的管理与设计开发分为以下几步&#xff1a; 1.记忆的抽取&#xff1b; 2.记忆的存储&#xff1b; 3.记忆的搜索&#xff1b; 一、记忆抽取一&#xff1a; FACT_RETRIEVAL_PROMPT f"""你是一位个人信息整理助手&#xff0c;专门负责准确存储事实、用…
阅读更多...
026 在线文档管理系统技术架构解析：基于 Spring Boot 的企业级文档管理平台

026 在线文档管理系统技术架构解析：基于 Spring Boot 的企业级文档管理平台

在线文档管理系统技术架构解析&#xff1a;基于Spring Boot的企业级文档管理平台 在企业数字化转型的进程中&#xff0c;高效的文档管理系统已成为提升协作效率的核心基础设施。本文将深入解析基于Spring Boot框架构建的在线文档管理系统&#xff0c;该系统整合公告信息管理、…
阅读更多...
AWTK-MVVM的一些使用技巧总结（1）

AWTK-MVVM的一些使用技巧总结（1）

在项目中用了一段时间的AWTK-MVVM框架&#xff0c;由于AWTK-MVVM本身的文档十分欠缺&#xff0c;自己经过一段时间的研究折腾出了几个技巧&#xff0c;在此记录总结。 用fscript启用传统UI代码 AWTK-MVVM里面重新设计了navigator机制&#xff0c;重定位了navigator_to的调用方…
阅读更多...
openwrt使用quilt工具制作补丁

openwrt使用quilt工具制作补丁

前言&#xff1a;简单聊一下为什么需要制作补丁&#xff0c;因为openwrt的编译是去下载很多组件放到dl目录下面&#xff0c;这些组件都是压缩包。如果我们要修改这些组件里面的源码&#xff0c;就需要对这些组件打pacth&#xff0c;也就是把我们的差异点在编译的时候合入到对应…
阅读更多...
强化学习 （1）基本概念

强化学习 （1）基本概念

grid-world example 一个由多个格子组成的二维网格 三种格子&#xff1a;accessible可通行的&#xff1b; forbidden禁止通行的&#xff1b; target目标 state状态 state是智能体相对于环境的状态&#xff08;情况&#xff09; 在grid-world example里&#xff0c;state指的…
阅读更多...
【Typst】纵向时间轴

【Typst】纵向时间轴

概述 6月10日实验了一个纵向时间轴排版效果&#xff0c;当时没有做成单独的模块&#xff0c;也存在一些Bug。 今天(6月29日)在原基础上进行了一些改进&#xff0c;并总结为模块。 目前暂时发布出来&#xff0c;可用&#xff0c;后续可能会进行大改。 使用案例 导入模块使用…
阅读更多...
【Visual Studio Code上传文件到服务器】

【Visual Studio Code上传文件到服务器】

在 Visual Studio Code (VS Code) 中上传文件到 Linux 系统主要通过 SSH 协议实现&#xff0c;结合图形界面&#xff08;GUI&#xff09;或命令行工具操作。以下是具体说明及进度查看、断点续传的实现方法&#xff1a; ⚙️ 一、VS Code 上传文件到 Linux 的机制 SSH 远程连接 …
阅读更多...
手机控车一键启动汽车智能钥匙

手机控车一键启动汽车智能钥匙

手机一键启动车辆的方法 手机一键启动车辆是一种便捷的汽车启动方式&#xff0c;它通过智能手机应用程序实现对车辆的远程控制。以下是详细的步骤&#xff1a; 完成必要的认证与激活步骤。打开手机上的相关移动管家手机控车APP&#xff0c;并与车载蓝牙建立连接。在APP的主界面…
阅读更多...
基于深度学习的语音增强技术：时间增强多尺度频域卷积网络模型解析

基于深度学习的语音增强技术：时间增强多尺度频域卷积网络模型解析

基于深度学习的语音增强技术&#xff1a;时间增强多尺度频域卷积网络模型解析 近年来&#xff0c;随着语音处理技术的不断发展&#xff0c;语音增强&#xff08;Speech Enhancement&#xff09;逐渐成为研究热点。语音增强的主要目标是通过消除噪声和改善信噪比来提高语音质量…
阅读更多...
计算机组成原理-数据表示与运算（三）

计算机组成原理-数据表示与运算（三）

### 文字提取结果&#xff1a; #### 题目内容&#xff1a; 34. 【2009 统考真题】浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示&#xff0c;且位数分别为 5 和 7&#xff08;均含 2 位符号位&#xff09;。…
阅读更多...
Learning Fully Convolutional Networks for Iterative Non-blind Deconvolution论文阅读

Learning Fully Convolutional Networks for Iterative Non-blind Deconvolution论文阅读

Learning Fully Convolutional Networks for Iterative Non-blind Deconvolution 1. 研究目标与实际问题1.1 研究目标1.2 实际意义2. 创新方法与模型设计2.1 核心框架：迭代式梯度域处理2.1.1 模型架构2.2 关键技术实现2.2.1 梯度域去噪网络2.2.2 解卷积模块（核心公式实现）2.…
阅读更多...
Vue3——组件传值

Vue3——组件传值

父传子 props ——最推荐的方法&#xff08;TOP1级别&#xff09; 父组件文件 <sidebar :text"textname" ></sidebar> //父组件通过 :text 将父组件的数据textname传递给子组件 const textname:Ref<dataFather[]> ref([{name:刘亦菲,age:18 },…
阅读更多...
DOP数据开放平台(真实线上项目)

DOP数据开放平台(真实线上项目)

什么是数据开放平台&#xff1f; 数据开放平台是一种通过公开应用程序编程接口&#xff08;API&#xff09;或结构化数据&#xff0c;允许第三方开发者或机构访问、使用和共享数据的平台‌&#xff0c;旨在促进数据流通、打破信息孤岛并激发创新应用。 DOP数据开放平台简单演示…
阅读更多...
最新文章

Copyright @ 2022~2023