java TreeMap 详解

Java TreeMap 详解

TreeMap 是 Java 中的一个基于红黑树实现的 NavigableMap，它提供了键值对的按键自然顺序（或用户自定义顺序）排序的映射表。它是 Map 接口的一个实现类，属于 java.util 包。

1. TreeMap 的特点

1. 有序性

   • TreeMap 按键的自然顺序 (Comparable) 或自定义顺序 (Comparator) 排序。
   • 默认按键的升序排列。

2. 基于红黑树实现

   • TreeMap 底层是红黑树，保证插入、删除、查询操作的时间复杂度为 O(log n)。

3. 不允许键为 null

   • 键必须实现 Comparable 或提供 Comparator，否则会抛出 NullPointerException。
   • 值可以为 null。

4. 线程不安全

   • TreeMap 是非同步的，如果需要线程安全，可以使用 Collections.synchronizedSortedMap() 方法。

5. 实现接口

   • NavigableMap
   • SortedMap
   • Map
   • Cloneable
   • Serializable

2. TreeMap 的常用构造方法

TreeMap<K, V> map = new TreeMap<>();

3. TreeMap 的常用方法

4. TreeMap 使用示例

基本操作

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        // 创建 TreeMap
        TreeMap<Integer, String> map = new TreeMap<>();

        // 添加键值对
        map.put(3, "Three");
        map.put(1, "One");
        map.put(2, "Two");
        map.put(5, "Five");
        map.put(4, "Four");

        // 按照键的自然顺序输出
        System.out.println("TreeMap: " + map);

        // 获取元素
        System.out.println("Key 3 maps to: " + map.get(3));

        // 删除元素
        map.remove(2);
        System.out.println("After removing key 2: " + map);

        // 遍历键值对
        System.out.println("Keys:");
        for (Integer key : map.keySet()) {
            System.out.println(key + " -> " + map.get(key));
        }

        // 获取子映射
        System.out.println("HeadMap (keys < 4): " + map.headMap(4));
        System.out.println("TailMap (keys >= 4): " + map.tailMap(4));
        System.out.println("SubMap (2 <= keys < 5): " + map.subMap(2, 5));
    }
}

输出：

TreeMap: {1=One, 2=Two, 3=Three, 4=Four, 5=Five}
Key 3 maps to: Three
After removing key 2: {1=One, 3=Three, 4=Four, 5=Five}
Keys:
1 -> One
3 -> Three
4 -> Four
5 -> Five
HeadMap (keys < 4): {1=One, 3=Three}
TailMap (keys >= 4): {4=Four, 5=Five}
SubMap (2 <= keys < 5): {3=Three, 4=Four}

自定义排序

通过 Comparator 自定义键的排序规则。

import java.util.*;

public class TreeMapCustomSort {
    public static void main(String[] args) {
        // 按键的降序排序
        TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());

        // 添加键值对
        map.put(3, "Three");
        map.put(1, "One");
        map.put(2, "Two");
        map.put(5, "Five");
        map.put(4, "Four");

        // 输出 TreeMap
        System.out.println("TreeMap with custom order: " + map);
    }
}

输出：

TreeMap with custom order: {5=Five, 4=Four, 3=Three, 2=Two, 1=One}

NavigableMap 的操作

TreeMap 实现了 NavigableMap，支持范围查询、边界查询等高级功能。

import java.util.*;

public class TreeMapNavigable {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();

        map.put(10, "Ten");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");

        // 边界查询
        System.out.println("Lower than 30: " + map.lowerKey(30));
        System.out.println("Floor of 30: " + map.floorKey(30));
        System.out.println("Higher than 30: " + map.higherKey(30));
        System.out.println("Ceiling of 30: " + map.ceilingKey(30));

        // 获取并移除最小和最大元素
        System.out.println("Poll first entry: " + map.pollFirstEntry());
        System.out.println("Poll last entry: " + map.pollLastEntry());

        // 输出最终的 TreeMap
        System.out.println("Remaining TreeMap: " + map);
    }
}

输出：

Lower than 30: 20
Floor of 30: 30
Higher than 30: 40
Ceiling of 30: 30
Poll first entry: 10=Ten
Poll last entry: 40=Forty
Remaining TreeMap: {20=Twenty, 30=Thirty}

线程安全的 TreeMap

如果需要线程安全的 TreeMap，可以使用以下方法：

Map<Integer, String> synchronizedMap = Collections.synchronizedMap(new TreeMap<>());

5. TreeMap 与 HashMap 对比

6. TreeMap 的应用场景

1. 排序数据

• 需要对键按自然顺序或自定义规则排序时使用。
• 示例：学生成绩单按学号或分数排序。

2. 范围查询

• TreeMap 提供 headMap、tailMap 和 subMap 方法，便于实现范围查询。
• 示例：获取某个范围内的日期或价格区间的值。

3. 边界操作

• 支持 higherKey、lowerKey、ceilingKey 和 floorKey 方法，适合边界查询。
• 示例：实现一个简易的日程安排系统，快速查询最近的空闲时间段。

4. 有序数据统计

• 红黑树底层实现，适合需要动态更新并保持有序的数据。
• 示例：股票交易记录，随时按时间戳查询最低或最高价格。

7. 常见问题

1. 为什么 TreeMap 的键不能为 null？

• 因为 TreeMap 的键需要进行排序（依赖 compareTo 方法或 Comparator），而 null 无法参与比较操作，会抛出 NullPointerException。

2. TreeMap 和 LinkedHashMap 有什么区别？

• TreeMap 按键的自然顺序或自定义顺序排序。
• LinkedHashMap 按插入顺序或访问顺序排列键值对。

8. TreeMap 的底层原理

1. 红黑树结构

• TreeMap 使用红黑树实现。
• 红黑树是一种自平衡二叉搜索树，保证树的高度为 $O(\log n)$。
• 节点的插入、删除、查询均保持 $O(\log n)$ 的时间复杂度。

2. 操作过程

• 插入：新键插入到树中后，红黑树可能失衡，会通过旋转和颜色调整重新平衡。
• 删除：删除节点后，红黑树通过调整保持平衡。
• 查找：通过键值的比较递归查找对应节点。

9. 总结

优势

1. 键值对按键排序，支持范围查询、边界操作。
2. 高效：插入、删除、查找操作的时间复杂度为 $O(\log n)$。
3. 灵活：支持自定义比较规则，满足复杂排序需求。

劣势

1. 键不允许为 null。
2. 与 HashMap 相比，插入、查询性能较慢。
3. 线程不安全，需要额外同步处理。

适用场景

• 数据需要按键排序。
• 需要快速实现范围查询或边界查询。
• 动态数据的统计和更新。

如果数据不需要排序，可以优先选择 HashMap，它的性能更优。