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


相关文章
|
11月前
|
安全
深入解析哈希表、哈希映射和并发哈希映射的区别,以及死锁的成因和解决方案
深入解析哈希表、哈希映射和并发哈希映射的区别,以及死锁的成因和解决方案
|
1月前
|
安全 算法 Java
ConcurrentHashMap并发哈希表的设计与实现
ConcurrentHashMap并发哈希表的设计与实现
|
3月前
|
存储 关系型数据库 MySQL
MySQL索引底层实现原理(B树和B+树)
MySQL索引底层实现原理(B树和B+树)
83 0
MySQL索引底层实现原理(B树和B+树)
|
3月前
|
存储 缓存 Java
java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。
java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。
44 1
|
10月前
|
存储 缓存 安全
【JavaSE专栏55】Java集合类HashTable解析,基于哈希表实现的唯一性键值对存储数据结构
【JavaSE专栏55】Java集合类HashTable解析,基于哈希表实现的唯一性键值对存储数据结构
数据结构(7)树形结构——红黑树(概念、插入过程、删除过程)
7.1.概述 平衡二叉树是要求任意结点的左右子树高度差不超过1,因此在AVL中用旋转来保证树的绝对平衡,但是这些旋转操作步骤繁多很耗时间,所以在面对经常会有数据插入的场景时,AVL不是一个性能优秀的选择。这时候反过来思考一个问题,旋转是为了保证树的绝对平衡,但是树的绝对平衡是必须的吗?显然不是,树的高度差只要不是太高从而退化成斜二叉树其实就能接受。
77 0
|
存储 算法 NoSQL
每日一博 - 如何理解跳表(SkipList)
每日一博 - 如何理解跳表(SkipList)
70 0
趣谈哈希表优化:从规避 Hash 冲突到利⽤ Hash 冲突
导读: 本文从哈希表传统设计与解决思路入手,深入浅出地引出新的设计思路:从尽量规避哈希冲突,转向了利⽤合适的哈希冲突概率来优化计算和存储效率。新的哈希表设计表明 SIMD 指令的并⾏化处理能⼒的有效应⽤能⼤幅度提升哈希表对哈希冲突的容忍能⼒,进⽽提升查询的速度,并且能帮助哈希表进⾏极致的存储空间压缩。
数据结构93-什么是冲突
数据结构93-什么是冲突
59 0
数据结构93-什么是冲突
平衡树是干什么的?底层原理是什么?
平衡树是干什么的?底层原理是什么?
159 0