1. 概述
本文将深入探讨 Java 集合框架(JCF)中 Map 接口的 TreeMap 实现类。
TreeMap 是一种特殊的 Map 实现，它根据键的自然顺序或构造时提供的 Comparator 对条目进行排序。之前我们研究过 HashMap 和 LinkedHashMap 的实现，会发现这些类的工作原理有很多相似之处。
建议在阅读本文前先了解上述两篇文章，这样能更好地理解 TreeMap 的特性。
2. TreeMap 的默认排序
默认情况下，TreeMap 会按照键的自然顺序对所有条目进行排序。对于整数来说就是升序，对于字符串则是字母顺序。
下面通过测试验证自然排序：
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}
注意我们以无序方式插入整数键，但检索键集时，它们确实按升序排列。这就是整数的自然顺序。
同样地，使用字符串时也会按自然顺序（字母顺序）排序：
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
TreeMap<String, String> map = new TreeMap<>();
map.put("c", "val");
map.put("b", "val");
map.put("a", "val");
map.put("e", "val");
map.put("d", "val");
assertEquals("[a, b, c, d, e]", map.keySet().toString());
}
与 HashMap 和 LinkedHashMap 不同，TreeMap 完全不使用哈希原理，因为它不依赖数组来存储条目。
3. TreeMap 的自定义排序
如果对 TreeMap 的自然排序不满意，我们可以在构造时通过 Comparator 定义自己的排序规则。
下面的示例中，我们希望整数键按降序排列：
@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
TreeMap<Integer, String> map =
new TreeMap<>(Comparator.reverseOrder());
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString());
}
HashMap 不保证键的存储顺序，且不保证该顺序随时间保持不变，但 TreeMap 保证键始终按指定顺序排序。
4. TreeMap 排序的重要性
既然 TreeMap 以有序方式存储所有条目，我们就可以执行一些特殊查询：
- 查找"最大"键
- 查找"最小"键
- 查找小于/大于某个值的所有键
以下代码展示了部分查询场景：
@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
Integer highestKey = map.lastKey();
Integer lowestKey = map.firstKey();
Set<Integer> keysLessThan3 = map.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet();
assertEquals(new Integer(5), highestKey);
assertEquals(new Integer(1), lowestKey);
assertEquals("[1, 2]", keysLessThan3.toString());
assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}
5. TreeMap 的内部实现
TreeMap 实现了 NavigableMap 接口，其内部工作原理基于红黑树：
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
红黑树的原理超出了本文范围，但需要记住几个关键点：
首先，红黑树是由节点组成的数据结构。可以想象一棵倒置的芒果树，根在天空，树枝向下生长。根节点包含添加到树的第一个元素。
规则是从根节点开始，任何节点的左分支元素都小于该节点本身，右分支元素则大于。大小比较由元素的自然顺序或构造时定义的 Comparator 决定。
这个规则保证了 TreeMap 的条目始终处于有序且可预测的状态。
其次，红黑树是自平衡二叉搜索树。这个特性加上上述规则，确保了基本操作（搜索、获取、插入、删除）的时间复杂度为对数级 *O(log n)*。
自平衡是关键。随着条目的不断插入和删除，树可能会在某一边变长，另一边变短。这意味着在较短的分支上操作更快，而在离根最远的分支上操作更慢——这是我们不愿看到的。
红黑树的设计解决了这个问题。每次插入和删除后，树的最大高度都维持在 *O(log n)*，即树会持续自我平衡。
与 HashMap 和 LinkedHashMap 一样，TreeMap 也是非线程安全的。在多线程环境中的使用规则与前两者相同。
6. 如何选择合适的 Map 实现
研究过 HashMap、LinkedHashMap 和现在的 TreeMap 后，有必要简要比较三者，帮助我们在不同场景下做出选择。
HashMap：
✅ 通用型 Map 实现，提供快速的存储和检索操作
❌ 条目排列混乱无序
⚠️ 大量迭代场景性能较差（遍历受底层数组容量影响）
LinkedHashMap：
✅ 继承 HashMap 的优点，同时保持条目插入顺序
✅ 迭代性能优异（只与条目数有关，与容量无关）
❌ 排序能力有限
TreeMap：
✅ 提供完全可控的键排序
✅ 支持范围查询等高级操作
❌ 通用性能不如前两者
⚠️ 自定义排序需实现 Comparator，可能踩坑
简单粗暴地说：**LinkedHashMap 在不牺牲 HashMap 性能的前提下解决了其无序问题，又避免了 TreeMap 的性能开销**。
7. 总结
本文深入探讨了 Java TreeMap 类及其内部实现。作为常见 Map 接口实现的压轴之作，我们还简要讨论了它与其他两种实现的适用场景对比。
本文所有示例的完整源代码可在 GitHub 项目 中找到。