TreeMap详解：Java 有序 Map 原理与实现

TreeMap详解：Java 有序 Map 原理与实现

TreeMap 是 Java 集合框架中的一个重要类，它实现了 NavigableMap 接口，同时也是 SortedMap 接口的实现。与 HashMap 不同的是，TreeMap 按照键的自然顺序（或者通过构造方法提供的 Comparator）对键进行排序，因此它是一个有序的 Map。

1. 核心特性

• 有序性：TreeMap 中的键是有序的，可以通过 firstKey(), lastKey(), nextKey() 等方法便捷地获取顺序元素。
• 基于红黑树：TreeMap 的底层数据结构是红黑树，这是一种自平衡的二叉查找树，保证在增加、删除或查找元素时都能保持 O(log n) 的时间复杂度。
• 允许 null 值：虽然 TreeMap 允许存储 null 值，但不允许有 null 的键（因为没有自然顺序）。

2. 主要方法

• put(K key, V value)：将指定值与指定的键关联，并返回之前与该键关联的值。
• get(Object key)：返回指定键所映射的值，如果映射不存在则返回 null。
• remove(Object key)：删除指定键及其对应的值。
• firstKey()、lastKey()：返回第一个和最后一个键。
• ceilingKey(K key)、floorKey(K key)：返回大于等于或小于等于指定键的最小键。

3. 使用示例

以下是一个简单的程序示例，展示了 TreeMap 的基本用法：

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

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

        // 添加元素
        map.put("apple", 3);
        map.put("banana", 2);
        map.put("orange", 5);
        map.put("grape", 4);

        // 打印所有键值对
        System.out.println("原始 TreeMap：");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 获取特定键的值
        System.out.println("\n获取 'banana' 的值: " + map.get("banana"));

        // 获取第一个和最后一个键
        System.out.println("第一个键: " + map.firstKey());
        System.out.println("最后一个键: " + map.lastKey());

        // 移除一个键
        map.remove("orange");
        System.out.println("\n删除 'orange' 后的 TreeMap：");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 通过 Comparator 创建一个自定义排序的 TreeMap
        TreeMap<Integer, String> reverseMap = new TreeMap<>(Comparator.reverseOrder());
        reverseMap.put(1, "one");
        reverseMap.put(2, "two");
        reverseMap.put(3, "three");

        System.out.println("\n反向排序的 TreeMap：");
        for (Map.Entry<Integer, String> entry : reverseMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

4. 运行结果

以上代码的输出结果如下：

原始 TreeMap：
apple: 3
banana: 2
grape: 4
orange: 5

获取 'banana' 的值: 2
第一个键: apple
最后一个键: orange

删除 'orange' 后的 TreeMap：
apple: 3
banana: 2
grape: 4

反向排序的 TreeMap：
3: three
2: two
1: one

5. 总结

TreeMap 提供了一种基于键的有序存储方式，适用于需要按顺序访问键值对的场景。虽然插入和删除的效率不及 HashMap，但它强大的有序特性和基于红黑树的数据结构使其在特定的应用场景下非常有用。在实际开发中，开发者可以根据需求，选择合适的 Map 实现。