Java中的TreeMap有什么特点？如何实现按键排序并适配NavigableMap接口？

Java中的TreeMap是集合框架里的重要成员，它基于红黑树数据结构实现，和HashMap的无序存储不同，TreeMap的所有键值对都会按照键的顺序进行排列，同时它实现了NavigableMap接口，提供了很多便于范围操作的方法，在很多需要有序映射的场景下都有广泛应用。

TreeMap的核心特点

1. 有序性

TreeMap的最核心特点就是有序，排序规则有两种配置方式：一是使用键对象的自然顺序，要求键类实现Comparable接口；二是创建TreeMap时传入自定义的Comparator比较器，按照自定义规则排序。如果两种方式都没有配置，且键没有实现Comparable接口，运行时会抛出ClassCastException。

2. 基于红黑树实现

TreeMap的底层是红黑树，这是一种自平衡的二叉查找树，插入、删除、查找操作的时间复杂度都是O(log n)，相比HashMap的O(1)平均复杂度要低，但胜在有序性带来的操作优势。红黑树的特性保证了树的高度不会过高，避免了二叉查找树退化成链表的情况。

3. 非线程安全

TreeMap和HashMap一样，不是线程安全的，如果需要在多线程环境下使用，需要通过Collections.synchronizedSortedMap方法包装，或者考虑使用ConcurrentSkipListMap替代。

4. 不允许null键（自定义比较器允许的情况除外）

如果使用自然排序或者比较器不支持null值比较，往TreeMap中插入null键会抛出NullPointerException。如果使用自定义比较器且比较器可以处理null值，那么可以插入null键。

按键排序的实现方式

要实现TreeMap的按键排序，只需要正确配置排序规则即可，以下是两种常见场景的示例：

自然顺序排序

当键类实现了Comparable接口时，TreeMap默认使用自然顺序排序，比如String、Integer等包装类都已经实现了该接口。

import java.util.TreeMap;

public class TreeMapNaturalSort {
    public static void main(String[] args) {
        // 键为String类型，使用自然字典序排序
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("apple", 3);
        map.put("banana", 1);
        map.put("cherry", 2);
        // 遍历输出会按照键的升序排列
        for (String key : map.keySet()) {
            System.out.println(key + " : " + map.get(key));
        }
    }
}

自定义比较器排序

如果需要按照自定义规则排序，比如按照字符串长度排序，可以在构造TreeMap时传入Comparator：

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapCustomSort {
    public static void main(String[] args) {
        // 自定义比较器：按照键的字符串长度升序排序，长度相同按照字典序排序
        TreeMap<String, Integer> map = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() != o2.length()) {
                    return o1.length() - o2.length();
                }
                return o1.compareTo(o2);
            }
        });
        map.put("a", 1);
        map.put("bb", 2);
        map.put("ccc", 3);
        map.put("ab", 4);
        // 遍历输出顺序为a, ab, bb, ccc
        for (String key : map.keySet()) {
            System.out.println(key + " : " + map.get(key));
        }
    }
}

模拟按键排序的字典树功能

字典树（Trie）的核心特点是按照前缀匹配查询，我们可以利用TreeMap的有序性来模拟简单的字典树前缀查询功能，因为TreeMap的键是有序的，所有相同前缀的键会连续排列在映射中。

以下是使用TreeMap实现前缀查询的示例：

import java.util.NavigableMap;
import java.util.TreeMap;

public class TreeMapTrieDemo {
    public static void main(String[] args) {
        TreeMap<String, String> trieMap = new TreeMap<>();
        // 插入一些单词作为字典树节点
        trieMap.put("app", "应用");
        trieMap.put("apple", "苹果");
        trieMap.put("application", "应用程序");
        trieMap.put("banana", "香蕉");
        trieMap.put("band", "乐队");

        String prefix = "app";
        // 获取所有以prefix为前缀的键：从prefix开始，到prefix+最后一个字符的范围
        NavigableMap<String, String> subMap = trieMap.subMap(prefix, true, prefix + Character.MAX_VALUE, false);
        System.out.println("前缀为" + prefix + "的单词：");
        for (String key : subMap.keySet()) {
            System.out.println(key + " : " + subMap.get(key));
        }
    }
}

上述代码中，subMap方法获取了键在[prefix, prefix + Character.MAX_VALUE)范围内的所有键值对，因为TreeMap有序，所以这个范围刚好是所有以prefix为前缀的键，实现了类似字典树的前缀查询效果。

NavigableMap接口的常用方法

TreeMap实现了NavigableMap接口，该接口提供了一系列导航相关的方法，方便进行范围查询、极值获取、逆序遍历等操作，以下是常用方法的说明和示例：

以下是这些方法的实际使用示例：

import java.util.TreeMap;
import java.util.NavigableMap;

public class NavigableMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "一");
        map.put(3, "三");
        map.put(5, "五");
        map.put(7, "七");
        map.put(9, "九");

        System.out.println("小于5的最大键：" + map.lowerKey(5)); // 输出3
        System.out.println("小于等于5的最大键：" + map.floorKey(5)); // 输出5
        System.out.println("大于等于5的最小键：" + map.ceilingKey(5)); // 输出5
        System.out.println("大于5的最小键：" + map.higherKey(5)); // 输出7
        System.out.println("第一个键：" + map.firstKey()); // 输出1
        System.out.println("最后一个键：" + map.lastKey()); // 输出9

        // 获取键在[3,7]范围内的子映射，包含3和7
        NavigableMap<Integer, String> subMap = map.subMap(3, true, 7, true);
        System.out.println("子映射的键集：" + subMap.keySet()); // 输出[3,5,7]

        // 逆序遍历
        System.out.println("逆序键集：" + map.descendingKeySet()); // 输出[9,7,5,3,1]
    }
}

使用注意事项

• 如果键的类型没有实现Comparable接口，且构造TreeMap时没有传入自定义比较器，运行时会抛出类型转换异常。
• 自定义比较器需要保证比较逻辑的一致性，即如果compare(a,b)==0，那么a.equals(b)最好也为true，否则TreeMap的行为会和Map接口的通用约定不一致。
• TreeMap的迭代顺序是键的排序顺序，如果需要按照插入顺序排序，应该使用LinkedHashMap。
• NavigableMap返回的视图（比如子映射、逆序映射）都是原映射的实时视图，修改视图会影响原映射，修改原映射也会影响视图。

TreeMapNavigableMap按键排序字典树修改时间：2026-06-09 05:15:38