在 Java 集合框架的浩瀚海洋中，Map 家族占据着举足轻重的地位。而我们今天的主角 TreeMap，则是这个家族中一位独特的“排序大师”。它不仅能高效地存储键值对，还能时刻维持键的有序状态。本文将深入剖析 TreeMap，带你领略其内在魅力和实用场景。

一、什么是 TreeMap？

TreeMap 是 Java 中实现了 Map 接口的一个类，它基于红黑树（Red-Black tree） 这种自平衡的二叉查找树来存储键值对 (key-value pairs)。

它的核心特性非常突出：

1. 键的有序性：这是 TreeMap 最显著的特点。它中的所有 key 默认按照其自然顺序（Natural Ordering）进行排序，或者根据创建时提供的 Comparator 进行定制排序。你可以轻松地获取最大、最小或某个范围内的键。
2. 性能保证：由于基于红黑树，containsKey, get, put, remove 等操作的时间复杂度均为 O(log n)。这意味着即使数据量增大，性能表现也非常稳定和可预测。
3. 不允许 null 键：如果你的业务逻辑需要使用 null 作为键，那么 TreeMap 会抛出 NullPointerException。但 value 可以是 null。
4. 非线程安全：和 HashMap 一样，TreeMap 不是线程安全的。如果需要在多线程环境下使用，必须通过外部同步手段包装它，例如使用 Collections.synchronizedSortedMap(new TreeMap(...))。

二、核心原理：红黑树

TreeMap 的魔力之源在于其底层的红黑树数据结构。红黑树是一种近似平衡的二叉查找树，它通过在插入和删除时执行特定的旋转和变色操作来维持平衡，从而保证了最坏情况下查找、插入、删除的时间复杂度仍为 O(log n)。

你可以简单地将其理解为一颗总是保持“相对平衡”的排序二叉树。这使得 TreeMap 在需要频繁排序和范围查询的场景下，相比 HashMap（平均 O(1)）有着不可替代的优势。

三、如何使用 TreeMap？

1. 构造方法

TreeMap 提供了几个关键的构造方法：

// 1. 默认构造方法：使用键的自然顺序（Key必须实现Comparable接口）
TreeMap<Integer, String> map1 = new TreeMap<>();

// 2. 使用自定义比较器Comparator
TreeMap<String, Integer> map2 = new TreeMap<>(String.CASE_INSENSITIVE_ORDER); // 按键不区分大小写排序

// 3. 从另一个Map构造
Map<Integer, String> existingMap = new HashMap<>();
// ... 向existingMap添加一些数据
TreeMap<Integer, String> map3 = new TreeMap<>(existingMap); // 会按Integer的自然顺序排序

// 4. 从另一个SortedMap构造，继承其排序规则
SortedMap<Integer, String> sortedMap = new TreeMap<>();
TreeMap<Integer, String> map4 = new TreeMap<>(sortedMap);

2. 常用 API 演示

除了标准的 Map 方法（如 put, get, remove, containsKey），TreeMap 因其有序的特性，提供了一系列强大的额外方法：

TreeMap<Integer, String> studentScores = new TreeMap<>();
studentScores.put(95, "Alice");
studentScores.put(87, "Bob");
studentScores.put(92, "Charlie");
studentScores.put(78, "Diana");

// 获取第一个（最低）和最后一个（最高）键的条目
Map.Entry<Integer, String> lowestScore = studentScores.firstEntry(); // 78=Diana
Map.Entry<Integer, String> highestScore = studentScores.lastEntry(); // 95=Alice

// 获取比给定键“小”或“大”的最近条目
Map.Entry<Integer, String> justBelow90 = studentScores.lowerEntry(90); // 87=Bob
Map.Entry<Integer, String> justAbove90 = studentScores.higherEntry(90); // 92=Charlie

// 获取小于等于或大于等于给定键的最近条目
Map.Entry<Integer, String> floor90 = studentScores.floorEntry(90); // 87=Bob
Map.Entry<Integer, String> ceiling90 = studentScores.ceilingEntry(90); // 92=Charlie

// 获取子映射（视图） - 非常强大！
// 获取成绩在 [80, 93) 区间的学生（包含80，不包含93）
SortedMap<Integer, String> subMap = studentScores.subMap(80, 93); // {87=Bob, 92=Charlie}
// 获取成绩小于90的学生
SortedMap<Integer, String> headMap = studentScores.headMap(90); // {78=Diana, 87=Bob}
// 获取成绩大于等于90的学生
SortedMap<Integer, String> tailMap = studentScores.tailMap(90); // {92=Charlie, 95=Alice}

// 顺序和逆序遍历
// 默认升序迭代
for (Map.Entry<Integer, String> entry : studentScores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 降序迭代
for (Map.Entry<Integer, String> entry : studentScores.descendingMap().entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

四、TreeMap vs. HashMap：如何选择？

这是一个非常常见的问题。它们的核心区别决定了其适用场景。

特性	TreeMap	HashMap
数据结构	红黑树	数组 + 链表/红黑树 (JDK8+)
顺序性	键有序（自然或定制排序）	键无序（遍历顺序不保证）
性能	O(log n) for get, put	平均 O(1) for get, put
null 键	不允许	允许一个 null 键
使用场景	需要有序遍历、范围查询	快速存取、无需排序、频率更高

选择指南：

• 如果你需要键始终处于排序状态，或者需要频繁进行范围查找（如找最近的值、某个区间内的值），请毫不犹豫地选择 TreeMap。
• 如果你的首要目标是高效的存取速度，并且不关心顺序，HashMap 通常是更好的选择，因为它平均情况下的时间复杂度为 O(1)。

五、典型应用场景

1. 排行榜系统：键是分数（Integer），值是用户ID。可以轻松获取 Top N 用户、某用户附近的排名等。
2. 事件调度器：键是时间戳（Long 或 Date），值是事件对象。可以按时间顺序处理事件，或查找下一个要触发的事件。
3. 字典/词汇表：键是单词（String），值是解释。可以按字母顺序遍历所有单词，或者查找某个字母开头的所有单词（使用 tailMap(“c”).headMap(“d”) 来获取所有以 ‘c’ 开头的单词）。
4. 区间查询：例如，在金融应用中，根据价格区间快速查找对应的股票。

六、总结

TreeMap 是 Java 集合框架中一个强大而实用的工具。它用 O(log n) 的性能代价，换来了无与伦比的键有序性和范围操作能力。理解其底层基于红黑树的原理，能帮助你更好地判断其适用性。

下次当你面临一个需要数据自动排序或者复杂范围查询的需求时，不妨想想这位“排序大师”——TreeMap，它很可能就是你的最优解。

–

附录

基于TreeMap的排行榜系统设计

实现说明

这个排行榜数据结构的核心特点：

1. 双排序规则：支持第一排序（主排序）和第二排序（次要排序），当主排序关键字相同时，使用次要排序关键字

2. 排序方向控制：通过Order枚举可以为每个排序规则单独指定正序（ASCENDING）或逆序（DESCENDING）

3. 高效操作：基于 TreeMap 实现，添加、删除和查询操作都具有 O (log n) 的时间复杂度

4. 丰富的功能：

   • 添加 / 删除元素
   • 获取所有元素（按排名顺序）
   • 获取指定排名范围的元素
   • 查询特定元素的排名
   • 获取元素总数和清空排行榜

5. 灵活性：使用函数式接口Function提取排序关键字，可以适应任何类型的元素

6. 最低分限制：

   • 通过scoreExtractor函数提取元素的分数值
   • 只有分数大于等于minimumScore的元素才能被添加到排行榜
   • 可以通过getMinimumScore()方法获取当前最低分限制

7. 最大数量限制：

   • 通过maxSize参数指定排行榜最多可容纳的元素数量
   • 当maxSize为 - 1 时表示无限制
   • 添加元素后会自动检查并截断超出限制的元素（从最低排名开始移除）
   • 可以通过getMaxSize()方法获取当前最大数量限制

import java.util.*;
import java.util.function.Function;

/**
 * 基于TreeMap的排行榜数据结构
 * 支持指定第一排序和第二排序规则、排序方向、最低分限制和最大数量限制
 * @param <T> 排行榜中元素的类型
 */
public class RankingBoard<T> {
    // 底层使用TreeMap存储排名数据，键为排序关键字组合，值为元素列表
    private final TreeMap<SortingKey, List<T>> board;
    
    // 排序关键字生成器
    private final Function<T, Comparable> primaryKeyExtractor;
    private final Function<T, Comparable> secondaryKeyExtractor;
    private final Function<T, Number> scoreExtractor;  // 用于提取分数的函数
    
    // 排行榜配置参数
    private final Number minimumScore;  // 进入排名的最低分
    private final int maxSize;  // 排行榜最大数量，-1表示无限制
    
    /**
     * 排序方向枚举
     */
    public enum Order {
        ASCENDING,  // 正序
        DESCENDING  // 逆序
    }
    
    /**
     * 内部类，用于存储组合排序关键字
     */
    private static class SortingKey {
        private final Comparable primaryKey;
        private final Comparable secondaryKey;
        
        public SortingKey(Comparable primaryKey, Comparable secondaryKey) {
            this.primaryKey = primaryKey;
            this.secondaryKey = secondaryKey;
        }
    }
    
    /**
     * 自定义比较器，支持主次要排序和排序方向
     */
    private static class RankingComparator implements Comparator<SortingKey> {
        private final Order primaryOrder;
        private final Order secondaryOrder;
        
        public RankingComparator(Order primaryOrder, Order secondaryOrder) {
            this.primaryOrder = primaryOrder;
            this.secondaryOrder = secondaryOrder;
        }
        
        @Override
        public int compare(SortingKey key1, SortingKey key2) {
            // 先按主要关键字排序
            int primaryCompare = key1.primaryKey.compareTo(key2.primaryKey);
            // 根据排序方向调整比较结果
            if (primaryOrder == Order.DESCENDING) {
                primaryCompare = -primaryCompare;
            }
            
            // 如果主要关键字相同，再按次要关键字排序
            if (primaryCompare == 0) {
                int secondaryCompare = key1.secondaryKey.compareTo(key2.secondaryKey);
                if (secondaryOrder == Order.DESCENDING) {
                    secondaryCompare = -secondaryCompare;
                }
                return secondaryCompare;
            }
            
            return primaryCompare;
        }
    }
    
    /**
     * 构造函数
     * @param primaryKeyExtractor 第一排序关键字提取器
     * @param primaryOrder 第一排序方向
     * @param secondaryKeyExtractor 第二排序关键字提取器
     * @param secondaryOrder 第二排序方向
     * @param scoreExtractor 分数提取器（用于最低分限制）
     * @param minimumScore 进入排名的最低分数
     * @param maxSize 排行榜最大数量（-1表示无限制）
     */
    public RankingBoard(Function<T, Comparable> primaryKeyExtractor, Order primaryOrder,
                       Function<T, Comparable> secondaryKeyExtractor, Order secondaryOrder,
                       Function<T, Number> scoreExtractor, Number minimumScore, int maxSize) {
        this.primaryKeyExtractor = primaryKeyExtractor;
        this.secondaryKeyExtractor = secondaryKeyExtractor;
        this.scoreExtractor = scoreExtractor;
        this.minimumScore = minimumScore != null ? minimumScore : 0;
        this.maxSize = maxSize;
        this.board = new TreeMap<>(new RankingComparator(primaryOrder, secondaryOrder));
    }

        /**
     * 更新排行榜中的元素数据
     * @param oldElement 旧的元素（更新前的版本）
     * @param newElement 新的元素（更新后的版本）
     * @return 如果更新成功返回true，否则返回false
     */
    public boolean update(T oldElement, T newElement) {
        // 参数校验
        if (oldElement == null || newElement == null) {
            return false;
        }
        
        // 1. 先移除旧元素
        boolean removed = remove(oldElement);
        if (!removed) {
            return false; // 旧元素不在排行榜中，无法更新
        }
        
        // 2. 检查新元素是否符合最低分要求
        Number newScore = scoreExtractor.apply(newElement);
        if (newScore.doubleValue() < minimumScore.doubleValue()) {
            return false; // 新元素不符合最低分要求，不添加
        }
        
        // 3. 添加新元素
        boolean added = add(newElement);
        return added;
    }
    
    /**
     * 批量更新排行榜中的元素数据
     * @param updates 包含新旧元素对的映射
     * @return 成功更新的元素数量
     */
    public int batchUpdate(Map<T, T> updates) {
        if (updates == null || updates.isEmpty()) {
            return 0;
        }
        
        int successCount = 0;
        for (Map.Entry<T, T> entry : updates.entrySet()) {
            if (update(entry.getKey(), entry.getValue())) {
                successCount++;
            }
        }
        return successCount;
    }
    
    /**
     * 添加元素到排行榜
     * 只有符合最低分要求的元素才会被添加
     * @param element 要添加的元素
     * @return 如果元素被成功添加，返回true
     */
    public boolean add(T element) {
        if (element == null) {
            return false;
        }
        
        // 检查是否达到最低分要求
        Number score = scoreExtractor.apply(element);
        if (score.doubleValue() < minimumScore.doubleValue()) {
            return false;
        }
        
        Comparable primaryKey = primaryKeyExtractor.apply(element);
        Comparable secondaryKey = secondaryKeyExtractor.apply(element);
        SortingKey key = new SortingKey(primaryKey, secondaryKey);
        
        // 添加元素
        board.computeIfAbsent(key, k -> new ArrayList<>()).add(element);
        
        // 检查是否需要截断排行榜以满足最大数量限制
        trimToMaxSize();
        
        return true;
    }
    
    /**
     * 从排行榜中移除元素
     * @param element 要移除的元素
     * @return 如果元素存在且被移除，返回true
     */
    public boolean remove(T element) {
        if (element == null) {
            return false;
        }
        
        Comparable primaryKey = primaryKeyExtractor.apply(element);
        Comparable secondaryKey = secondaryKeyExtractor.apply(element);
        SortingKey key = new SortingKey(primaryKey, secondaryKey);
        
        List<T> elements = board.get(key);
        if (elements != null) {
            boolean removed = elements.remove(element);
            // 如果列表为空，移除整个键
            if (elements.isEmpty()) {
                board.remove(key);
            }
            return removed;
        }
        return false;
    }
    
    /**
     * 确保排行榜不超过最大数量限制
     */
    private void trimToMaxSize() {
        if (maxSize <= 0 || size() <= maxSize) {
            return;
        }
        
        // 计算需要移除的元素数量
        int excess = size() - maxSize;
        List<T> allElements = getAllElements();
        
        // 从末尾开始移除多余的元素
        for (int i = allElements.size() - 1; i >= 0 && excess > 0; i--) {
            remove(allElements.get(i));
            excess--;
        }
    }
    
    /**
     * 获取排行榜中的所有元素，按排序规则排序
     * @return 排序后的元素列表
     */
    public List<T> getAllElements() {
        List<T> result = new ArrayList<>();
        for (List<T> elements : board.values()) {
            result.addAll(elements);
        }
        return result;
    }
    
    /**
     * 获取排行榜中指定排名范围的元素
     * @param startRank 起始排名（从1开始）
     * @param endRank 结束排名（包含）
     * @return 指定排名范围内的元素列表
     */
    public List<T> getElementsInRankRange(int startRank, int endRank) {
        if (startRank < 1 || endRank < startRank) {
            throw new IllegalArgumentException("无效的排名范围");
        }
        
        List<T> result = new ArrayList<>();
        int currentRank = 1;
        
        for (List<T> elements : board.values()) {
            for (T element : elements) {
                if (currentRank >= startRank && currentRank <= endRank) {
                    result.add(element);
                } else if (currentRank > endRank) {
                    return result;
                }
                currentRank++;
            }
        }
        
        return result;
    }
    
    /**
     * 获取元素在排行榜中的排名
     * @param element 要查询的元素
     * @return 元素的排名（从1开始），如果元素不在排行榜中，返回-1
     */
    public int getRank(T element) {
        if (element == null) {
            return -1;
        }
        
        Comparable primaryKey = primaryKeyExtractor.apply(element);
        Comparable secondaryKey = secondaryKeyExtractor.apply(element);
        SortingKey targetKey = new SortingKey(primaryKey, secondaryKey);
        
        int rank = 1;
        boolean foundInCurrentKey = false;
        
        // 遍历所有键，计算排名
        for (Map.Entry<SortingKey, List<T>> entry : board.entrySet()) {
            SortingKey key = entry.getKey();
            List<T> elements = entry.getValue();
            
            // 比较当前键和目标键
            int comparison = board.comparator().compare(key, targetKey);
            
            if (comparison < 0) {
                // 当前键排在目标键前面，累加排名
                rank += elements.size();
            } else if (comparison == 0) {
                // 找到目标键，检查元素是否在列表中
                int index = elements.indexOf(element);
                if (index != -1) {
                    rank += index;
                    foundInCurrentKey = true;
                    break;
                }
            } else {
                // 当前键排在目标键后面，无需继续查找
                break;
            }
        }
        
        return foundInCurrentKey ? rank : -1;
    }
    
    /**
     * 获取排行榜中的元素总数
     * @return 元素总数
     */
    public int size() {
        int total = 0;
        for (List<T> elements : board.values()) {
            total += elements.size();
        }
        return total;
    }
    
    /**
     * 清空排行榜
     */
    public void clear() {
        board.clear();
    }
    
    /**
     * 获取当前排行榜的最低分限制
     * @return 最低分限制
     */
    public Number getMinimumScore() {
        return minimumScore;
    }
    
    /**
     * 获取当前排行榜的最大数量限制
     * @return 最大数量限制，-1表示无限制
     */
    public int getMaxSize() {
        return maxSize;
    }
}

使用

        class Player {
            private final String name;
            private final int score;
            private final long playTime;
            
            public Player(String name, int score, long playTime) {
                this.name = name;
                this.score = score;
                this.playTime = playTime;
            }
            
            public String getName() { return name; }
            public int getScore() { return score; }
            public long getPlayTime() { return playTime; }
            
            @Override
            public String toString() {
                return name + " (分数: " + score + ", 游戏时间: " + playTime + ")";
            }
            
            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Player player = (Player) o;
                return score == player.score && 
                       playTime == player.playTime && 
                       Objects.equals(name, player.name);
            }
            
            @Override
            public int hashCode() {
                return Objects.hash(name, score, playTime);
            }
        }
        

public class Example {
    public static void main(String[] args) {
       
        // 创建排行榜：
        // 第一排序：分数（降序）
        // 第二排序：游戏时间（升序）
        // 最低分限制：800分
        // 最大数量限制：3人
        RankingBoard<Player> playerRanking = new RankingBoard<>(
            Player::getScore, RankingBoard.Order.DESCENDING,
            Player::getPlayTime, RankingBoard.Order.ASCENDING,
            Player::getScore, 800, 3  // 分数提取器、最低分、最大数量
        );
        
        // 添加玩家
        System.out.println("添加玩家结果：");
        System.out.println("添加张三(700分): " + playerRanking.add(new Player("张三", 700, 3600))); // 低于最低分
        System.out.println("添加李四(1500分): " + playerRanking.add(new Player("李四", 1500, 4200)));
        System.out.println("添加王五(1200分): " + playerRanking.add(new Player("王五", 1200, 3800)));
        System.out.println("添加赵六(1500分): " + playerRanking.add(new Player("赵六", 1500, 3500)));
        System.out.println("添加钱七(900分): " + playerRanking.add(new Player("钱七", 900, 5000))); // 会导致排行榜超过最大限制
        
        // 显示当前排行榜（最多3人）
        System.out.println("\n当前排行榜(" + playerRanking.size() + "人):");
        List<Player> allPlayers = playerRanking.getAllElements();
        for (int i = 0; i < allPlayers.size(); i++) {
            System.out.println((i + 1) + ". " + allPlayers.get(i));
        }
        
        // 尝试添加一个高分玩家，看是否会挤掉低分玩家
        System.out.println("\n添加孙八(1600分): " + playerRanking.add(new Player("孙八", 1600, 3000)));
        
        // 显示更新后的排行榜
        System.out.println("\n更新后的排行榜(" + playerRanking.size() + "人):");
        allPlayers = playerRanking.getAllElements();
        for (int i = 0; i < allPlayers.size(); i++) {
            System.out.println((i + 1) + ". " + allPlayers.get(i));
        }
    }
}

操作性能：TreeMap 的添加、删除、查询等操作时间复杂度是 O (log n)，这意味着：

• 当元素数量为 1000 时，操作需要约 10 次比较
• 当元素数量为 100 万时，操作需要约 20 次比较
• 当元素数量为 10 亿时，操作需要约 30 次比较

适用场景：

• 对于中小规模数据（10 万以内）：性能非常出色，操作响应迅速
• 对于大规模数据（100 万 - 1 亿）：仍能保持可接受的性能，但需要更多内存

该实现适合中小规模排行榜场景（<10万条目），对于高频更新/大规模数据场景，建议结合Redis的SortedSet或专业排行榜服务实现分布式方案。