Java TreeMap:基于红黑树的排序映射解析

简介: Java TreeMap:基于红黑树的排序映射解析

在Java的集合框架中,TreeMap是一个非常重要的成员,它实现了SortedMap接口,为键(Key)提供了一个有序的映射。这种有序性是通过红黑树数据结构来实现的,红黑树是一种自平衡的二叉查找树,它能够在最坏的情况下保证基本的动态集合操作(如查找、插入和删除)的时间复杂度仍然是对数的。


1. TreeMap概述


TreeMap存储的键值对默认是按照键的自然顺序进行排序的,也可以根据创建TreeMap时提供的Comparator进行排序。这意味着当你遍历TreeMap时,你会得到一个按键排序的键值对序列。


2. TreeMap的内部结构


红黑树TreeMap实现有序性的关键。红黑树的特性确保了树的平衡,从而在插入、删除和查找操作时都能保持对数级别的时间复杂度。红黑树的每个节点都有一个颜色属性——红色或黑色,并且满足以下性质:

  • 每个节点或是红色,或是黑色。
  • 根节点是黑色。
  • 每个叶子节点(NIL节点,空节点)是黑色。
  • 如果一个节点是红色的,则它的两个子节点都是黑色的。
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些性质确保了树的高度相对较低,从而优化了性能。


3. TreeMap的使用场景


  • 当你需要一个有序的键值对集合时。
  • 当你需要对键进行范围查询时(例如查找所有键在指定范围内的元素)。
  • 当你需要一个能够在插入和删除时保持高效性能的数据结构时。


4. 示例代码


下面是一个简单的示例,展示了如何使用TreeMap

import java.util.TreeMap;
public class TreeMapExample {
    public static void main(String[] args) {
        // 创建一个TreeMap实例,按照键的自然顺序排序
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        
        // 向TreeMap中添加元素
        treeMap.put("apple", 1);
        treeMap.put("orange", 2);
        treeMap.put("banana", 3);
        treeMap.put("pear", 4);
        
        // 遍历并打印TreeMap中的元素(按键的顺序)
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        
        // 根据键的范围查询元素(包含起始键,不包含结束键)
        TreeMap<String, Integer> subMap = (TreeMap<String, Integer>) treeMap.subMap("apple", "pear");
        System.out.println("Elements between 'apple' and 'pear':");
        for (Map.Entry<String, Integer> entry : subMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

输出:

apple: 1
banana: 3
orange: 2  # 注意这里的顺序,因为按照字母顺序排序了键
pear: 4    # 同上,尽管在插入时pear是在orange后面的,但在排序后它的顺序改变了
Elements between 'apple' and 'pear':  # 范围查询结果不包括'pear'键对应的元素
apple: 1
banana: 3  # 注意这里只有banana是因为orange不在apple和pear之间(按照字母顺序)

注意:在上面的输出中,你可能会注意到“orange”和“banana”的顺序似乎与插入顺序不同。这是因为TreeMap默认按键的自然顺序(这里是字母顺序)对键进行排序,而不是按照插入顺序。此外,范围查询的结果也是有序的,并且不包括结束键对应的元素。如果你想按照特定的顺序对键进行排序,可以在创建TreeMap时提供一个自定义的Comparator


5. 自定义排序


为了按照自定义的顺序对TreeMap中的键进行排序,可以在创建时传入一个Comparator对象:

import java.util.Comparator;
import java.util.TreeMap;
public class CustomSortedTreeMap {
    public static void main(String[] args) {
        // 创建一个自定义排序的TreeMap实例(按照字符串长度排序)
        TreeMap<String, Integer> treeMap = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return Integer.compare(o1.length(), o2.length());
            }
        });
        
        // 向TreeMap中添加元素并打印(按键的长度顺序)
        treeMap.put("apple", 1);  // 长度为5的键
        treeMap.put("kiwi", 2);   // 长度为4的键
        treeMap.put("pear", 3);   // 长度为4的键
        treeMap.put("banana", 4); // 长度为6的键,会被放在最后面即使它是先被插入的
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

在这个例子中,我们提供了一个自定义的Comparator来按照字符串的长度对键进行排序。因此,“kiwi”和“pear”(长度为4)将出现在“apple”(长度为5)之前,“banana”(长度为6)将出现在最后,即使它是第一个被插入的元素。

相关文章
|
3天前
|
Java
Java中ReentrantLock释放锁代码解析
Java中ReentrantLock释放锁代码解析
21 8
|
24天前
|
Java
java实现遍历树形菜单方法——映射文件VoteTree.hbm.xml
java实现遍历树形菜单方法——映射文件VoteTree.hbm.xml
9 0
|
1天前
|
Java
Java 15 神秘登场:隐藏类解析未知领域
Java 15 神秘登场:隐藏类解析未知领域
8 0
|
1天前
|
安全 Java 编译器
接口之美,内部之妙:深入解析Java的接口与内部类
接口之美,内部之妙:深入解析Java的接口与内部类
6 0
接口之美,内部之妙:深入解析Java的接口与内部类
|
19天前
|
Java 程序员 C#
静态构造方法解析,Java新手必看技能
静态构造方法解析,Java新手必看技能
7 0
|
23天前
|
XML Java 数据格式
使用java解析XML文件的步骤
使用java解析XML文件的步骤
10 0
|
24天前
最全三大框架整合(使用映射)——DeptAction.java
最全三大框架整合(使用映射)——DeptAction.java
3 0
|
24天前
最全三大框架整合(使用映射)——DeptServiceImpl.java
最全三大框架整合(使用映射)——DeptServiceImpl.java
11 0
|
24天前
最全三大框架整合(使用映射)——IDeptService.java
最全三大框架整合(使用映射)——IDeptService.java
5 0
|
24天前
最全三大框架整合(使用映射)——DeptDaoImpl.java
最全三大框架整合(使用映射)——DeptDaoImpl.java
8 0

推荐镜像

更多