TreeMap实现排序键值对原理

TreeMap实现排序键值对的原理

TreeMap是Java中基于红黑树（Red-Black Tree）实现的有序键值对集合，其核心原理如下：

底层数据结构：红黑树

TreeMap的底层使用红黑树,这是一种自平衡的二叉查找树，具有以下特性：

• 每个节点是红色或黑色
• 根节点必须是黑色
• 叶子节点（NIL）是黑色
• 红色节点的子节点必须是黑色
• 从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点

排序机制

TreeMap通过两种方式实现键的排序：

自然排序（Comparable）

TreeMap<Integer, String> map = new TreeMap<>();

自定义排序（Comparator）

TreeMap<Integer, String> map = new TreeMap<>((a, b) -> b - a);  // 降序

插入过程示例

TreeMap<Integer, String> map = new TreeMap<>();
map.put(50, "A");
map.put(30, "B");
map.put(80, "C");
map.put(20, "D");
map.put(40, "E");

插入过程：

1. 插入50：成为根节点（黑色）
2. 插入30：比50小，成为左子节点（红色）
3. 插入80：比50大，成为右子节点（红色）
4. 插入20：比30小，成为30的左子节点（红色）
5. 插入40：比30大，成为30的右子节点（红色）

红色节点检测到违反规则时触发平衡操作：

• 左旋
• 右旋
• 颜色翻转

关键操作的时间复杂度

核心源码分析

// TreeMap.put()方法的核心逻辑
private V put(K key, V value, boolean replaceOld) {
    // 1. 查找插入位置
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 2. 创建新节点并插入
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    // 3. 修正红黑树平衡
    fixAfterInsertion(e);
}

实际应用示例

// 有序存储用户年龄和姓名
TreeMap<Integer, String> ageMap = new TreeMap<>();
ageMap.put(25, "张三");
ageMap.put(30, "李四");
ageMap.put(20, "王五");
// 自动按键排序输出
ageMap.forEach((age, name) -> 
    System.out.println(age + " -> " + name));
// 输出：
// 20 -> 王五
// 25 -> 张三
// 30 -> 李四
// 获取范围数据
SortedMap<Integer, String> subMap = ageMap.subMap(20, 30);

性能特点

TreeMap通过红黑树实现,在插入、删除、查找时自动维护键的顺序，每次操作后都会通过旋转和颜色调整保持树的平衡，确保所有操作都能在对数时间内完成，这使得TreeMap特别适合需要保持键有序的场景，如范围查询、有序遍历等。