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


相关文章
|
19天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
|
7月前
|
安全
深入解析哈希表、哈希映射和并发哈希映射的区别,以及死锁的成因和解决方案
深入解析哈希表、哈希映射和并发哈希映射的区别,以及死锁的成因和解决方案
|
4月前
|
安全 容器
线程安全的集合类(多线程环境下使用ArrayList、队列及哈希表)
线程安全的集合类(多线程环境下使用ArrayList、队列及哈希表)
|
4月前
|
存储 缓存 Java
java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。
java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。
28 1
|
10月前
数据结构(7)树形结构——红黑树(概念、插入过程、删除过程)
7.1.概述 平衡二叉树是要求任意结点的左右子树高度差不超过1,因此在AVL中用旋转来保证树的绝对平衡,但是这些旋转操作步骤繁多很耗时间,所以在面对经常会有数据插入的场景时,AVL不是一个性能优秀的选择。这时候反过来思考一个问题,旋转是为了保证树的绝对平衡,但是树的绝对平衡是必须的吗?显然不是,树的高度差只要不是太高从而退化成斜二叉树其实就能接受。
57 0
|
10月前
数据结构— —哈希表顺序实现
数据结构— —哈希表顺序实现
HashMap,你是怎么做到的Key重复?
HashMap,你是怎么做到的Key重复?
数据结构93-什么是冲突
数据结构93-什么是冲突
47 0
数据结构93-什么是冲突
数据结构21-队列常见操作
数据结构21-队列常见操作
33 0
数据结构109-哈希表删除操作代码
数据结构109-哈希表删除操作代码
63 0