Java中的TreeMap 指南

1.概述

在这篇文章中，我们将探讨Java Collections Framework(JCF)中Map接口的TreeMap的实现。

TreeMap是一个map实现，它根据其键的自然排序来保持其条目的排序，如果用户在构建时提供了一个比较器，则更好了。

之前，我们介绍了 HashMap 和 LinkedHashMap 实现，我们将意识到有很多关于这些类如何工作的信息是相似的。

在进行这项工作之前，强烈建议阅读所提到的文章。

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());
}

TreeMap与散列映射和链接散列映射不同，它没有在任何地方采用散列原理，因为它没有使用数组来存储它的条目。

3.在TreeMap中自定义排序

如果我们对TreeMap的自然排序不满意，我们也可以在构建树状图的过程中通过比较器来定义我们自己的排序规则。

在下面的例子中，我们想让整数键按降序排列。

@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());
}

哈希映射不保证存储的键的顺序，特别是不保证这个顺序会随着时间的推移而保持不变，但树形图保证键总是按照指定的顺序进行排序。

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

红黑树的原理超出了本文的范围，然而，为了理解红黑树如何融入TreeMap，有一些关键的事情需要记住。

首先，红黑树是一个由节点组成的数据结构；想象一下一棵倒置的芒果树，它的根在天上，树枝向下生长。根部将包含添加到树上的第一个元素。

规则是，从根部开始，任何节点的左边分支的任何元素总是小于节点本身的元素。右边的则总是大于。什么定义大于或小于是由元素的自然排序或如我们前面看到的构造时定义的比较器决定的。

此规则保证了树状图的条目总是以分类和可预测的顺序出现。

其次，红黑树是一种自平衡二叉搜索树。此属性和上述属性保证搜索、获取、放置和删除等基本操作需要对数时间 O(log n)。

自我平衡是这里的关键。当我们不断插入和删除条目时，想象一下这棵树在一条边上变长或在另一条边上变短。

这意味着一个操作在较短的分支上需要较短的时间，而在离根部最远的分支上则需要较长的时间，这是我们不希望发生的。

因此，这在红黑树的设计中得到了照顾。对于每一次插入和删除，任何边上的树的最大高度都保持在O(log n) ，也就是说，树不断地自我平衡。

就像哈希映射和链接哈希映射一样，树状映射也是不同步的，因此在多线程环境中使用它的规则与其他两种映射的实现类似。

6.选择正确的Map

之前看了HashMap和LinkedHashMap的实现，现在又看了TreeMap，有必要对这三者做一个简单的比较，以指导我们选择适合的那一个。

HashMap作为提供快速存储和检索操作的通用映射实现是很好的。然而，由于它的条目排列混乱无序，所以它不尽如人意。

这导致它在有大量迭代的情况下表现不佳，因为底层数组的全部容量都会影响到遍历，而不仅仅是条目的数量。

LinkedHashMap拥有HashMap的良好属性，并为条目添加了顺序。在有大量迭代的情况下，它的表现更好，因为只考虑条目的数量而不考虑容量。

TreeMap通过提供对键的排序方式的完全控制，将排序提升到一个新的水平。反过来说，它的总体性能比其他两个方案更差。

我们可以说，一个LinkedHashMap减少了HashMap的混乱排序，而不会产生TreeMap的性能损失。

7.结语

在这篇文章中，我们探讨了Java TreeMap类及其内部实现。由于它是一系列常见的Map接口实现中的最后一个，我们也继续简要讨论了它与其他两个接口的最佳位置。

本文中使用的所有示例的完整源代码可以在GitHub项目中找到。