Day1-TreeMap集合怎样保证有序性

简介: 笔记

TreeMap集合怎样保证有序性


首先看一下TreeMap集合的使用,TreeMap集合也是键值对的,我们添加下面四个元素

package com.tset.one;
import java.util.TreeMap;
/**
 * @author :caizhengjie
 * @description:TODO
 * @date :2021/7/21 10:48 下午
 */
public class TestTreeMap {
    public static void main(String[] args) {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("tom",99);
        treeMap.put("jack",73);
        treeMap.put("bob",85);
        treeMap.put("jery",62);
        // 通过lambada表达式输出key,value
        treeMap.forEach((k,v) -> System.out.println(k + ": " + v));      
    }
}
// 运行结果
bob: 85
jack: 73
jery: 62
tom: 99

发现遍历出来的结果是有序的,按照key的升序依次遍历,联想到Hash Map,它遍历出来的结果是无序的,它是按照key的hash进行散列的,那TreeMap是怎么样保证节点遍历出来是有序的呢?我们需要看一下源代码

8.png

它是一个红黑树,我们知道红黑树是一个平衡树,可以保证我们的节点有序,显然TreeMap底层用红黑树来保证节点的有序性,通过查看TreeMap的成员变量9.png


我们可以发现root是红黑树的根节点


TreeMap底层

TreeMap实现了SotredMap接口,它是有序的集合。

TreeMap底层数据结构是一个红黑树,每个key-value都作为一个红黑树的节点。

如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序。

10.png


目录
打赏
0
0
0
0
12
分享
相关文章
深入解析哈希表、哈希映射和并发哈希映射的区别,以及死锁的成因和解决方案
深入解析哈希表、哈希映射和并发哈希映射的区别,以及死锁的成因和解决方案
|
3月前
|
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
57 3
|
3月前
|
TreeMap基于红黑树实现,保证键的有序性,支持范围查询
【10月更文挑战第19天】在Java集合框架中,Map接口是存储键值对的重要工具,HashMap和TreeMap是最常用的两个实现类。HashMap基于哈希表实现,支持null键和值,查找、插入和删除操作平均时间复杂度接近O(1)。TreeMap基于红黑树实现,保证键的有序性,支持范围查询。两者各具特色,深入了解它们的设计思想有助于更好地应用。
42 4
|
3月前
|
Java集合框架中的HashSet和TreeSet,解释了它们如何分别实现无序和有序存储。
【10月更文挑战第13天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解释了它们如何分别实现无序和有序存储。通过解析内部机制和示例代码,帮助读者理解这两种集合的特点和应用场景,从而更好地选择合适的集合类型满足实际需求。
41 3
|
8月前
|
数据结构 模拟实现LinkedList单向不循环链表
数据结构 模拟实现LinkedList单向不循环链表
55 0
MySQL索引底层实现原理(B树和B+树)
MySQL索引底层实现原理(B树和B+树)
131 0
MySQL索引底层实现原理(B树和B+树)
java数据结构21:按大小顺序建立单链表并按要求删除节点
输入的每一行是姓名和年龄。读入每个人的信息,按年龄从小到大建立一个单链表。 按示例格式输出这个单链表。 删除链表中所有年龄是偶数的节 点,按示例格式输出剩下的所有节点。 要求:必须删除节点,不能只是跳过节点不输出。
87 0
【数据结构】顺序表的有序插入、扩容以及排序
【数据结构】顺序表的有序插入、扩容以及排序
190 0
数据结构(7)树形结构——红黑树(概念、插入过程、删除过程)
7.1.概述 平衡二叉树是要求任意结点的左右子树高度差不超过1,因此在AVL中用旋转来保证树的绝对平衡,但是这些旋转操作步骤繁多很耗时间,所以在面对经常会有数据插入的场景时,AVL不是一个性能优秀的选择。这时候反过来思考一个问题,旋转是为了保证树的绝对平衡,但是树的绝对平衡是必须的吗?显然不是,树的高度差只要不是太高从而退化成斜二叉树其实就能接受。
108 0
Java数据结构与算法分析(十一)散列表(哈希表)
散列表(Hash Table)也叫哈希表,是根据给定关键字(Key)来计算出该关键字在表中存储地址的数据结构。也就是说,散列表建立了关键字与存储地址之间的一种直接映射关系,将关键字映射到表中记录的地址,这加快了查找速度。
212 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等