JAVA集合知识总结(三)

JAVA集合知识总结(三)

TreeMap

TreeMap 是 Java 集合框架中基于红黑树实现的有序 Map 接口的实现类，能够保证键的有序性。

1. 什么是TreeMap

• TreeMap 实现了NavigableMap接口。
• TreeMap 是基于红黑树的数据结构，每次插入、删除操作都保持红黑树的平衡性。
• 键值对按键的自然顺序（即键类实现了 Comparable 接口）或通过自定义比较器（Comparator）进行排序。
• TreeMap 不允许 null 键，但允许 null 值。

2. 红黑树简介

• 红黑树是平衡二叉搜索树的一种，每个节点有红色或黑色属性，满足特定的平衡条件，确保插入、删除、查找的时间复杂度为 O(log n)。

• 特性包括：

  • 每个节点是红色或黑色。
  • 根节点是黑色。
  • 红色节点的子节点必为黑色（不能有连续的红色节点）。
  • 从根到每个叶节点的所有路径都包含相同数量的黑色节点。

• 插入、删除、查找操作的时间复杂度均为 O(log n)。

• 有序性使得 TreeMap 特别适合需要按键排序输出或范围查询的情况。

3. 构造方法

• 默认构造方法：使用键的自然排序：

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

• 自定义比较器：使用指定的 Comparator 对键排序：

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

4. 常用方法

• 插入元素：put(K key, V value)，如果键已存在，则更新值。
• 获取元素：get(Object key)，返回键对应的值。
• 删除元素：remove(Object key)，根据键删除对应的键值对。
• 获取第一个/最后一个键：firstKey() 和 lastKey()。
• 获取子映射：
  • subMap(K fromKey, K toKey)：获取指定范围内的子映射，fromKey 是包含的，toKey 是不包含的。
  • headMap(K toKey)：返回小于 toKey 的所有键值对。
  • tailMap(K fromKey)：返回大于等于 fromKey 的所有键值对。

5. 键的排序规则

TreeMap 的排序规则取决于键类型的 compareTo() 方法（如果键实现了 Comparable），或者是创建 TreeMap 时传入的 Comparator。两者不能同时存在，否则会抛出 ClassCastException。

自然排序

• 键类型实现 Comparable 接口（如 String、Integer 等），则按键的自然顺序排序。

自定义排序

• 通过构造 TreeMap 时传入 Comparator 实现自定义排序。

6. TreeMap 与 HashMap 的区别

7. 使用场景

• 需要按键排序时：TreeMap 自动按键排序，适用于需要有序输出的场景。
• 范围查询：subMap、headMap 和 tailMap 等方法使得 TreeMap 对于范围查找特别高效。

示例：按键排序的输出

TreeMap<String, Integer> map = new TreeMap<>();
map.put("apple", 2);
map.put("banana", 1);
map.put("cherry", 3);
System.out.println(map); // 按字母顺序输出 {apple=2, banana=1, cherry=3}

示例：范围查询

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
System.out.println(map.subMap(1, 3)); // 输出 {1=one, 2=two}

8. 注意事项

• 不允许 null 键，因为 null 会导致 Comparator 或 compareTo() 方法中无法比较。
• TreeMap 的性能在较大的数据量下相对 HashMap 略低，但能提供有序性和范围查询。

总结

• TreeMap 是基于红黑树实现的有序 Map，适用于需要排序和范围查询的场景。
• 插入、删除、查找操作的时间复杂度为 O(log n)。
• 提供键的自然排序或自定义排序方式，不支持 null 键。