Java中TreeMap的特点

如果您正在阅读本文，您很可能熟悉地图界面及其用途。如果没有，那么就到这里。今天我们来谈谈TreeMap的实现特点，更具体地说，它与HashMap有何不同以及如何正确使用它。

TreeMap、HashMap 和 LinkedHashMap 的比较

Map接口最常用的实现是HashMap。它易于使用并保证快速访问数据，使其成为大多数任务的最佳选择。大多数，但不是全部。有时需要以结构化形式存储数据并能够浏览数据。在这种情况下，Map接口的另一个实现可以解决这个问题- TreeMap。 TreeMap实现NavigableMap接口，该接口继承自SortedMap，而 SortedMap 又继承自Map接口。 通过实现NavigableMap和SortedMap接口，TreeMap获得了HashMap没有的附加功能，但这是以性能为代价的。还有一个LinkedHashMap类，它还允许您按特定顺序存储数据 - 按照它们添加的顺序。为了帮助您了解这三个类之间的差异，请查看此表： 正如您所看到的，这些类有很多共同点，但也有一些差异。尽管类的TreeMap功能最多，但它不能总是null作为键存储。另外，对TreeMap元素的访问时间将是最长的。因此，如果不需要以排序形式存储数据，最好使用HashMapor LinkedHashMap。

红檀树

您可能已经注意到，它在底层TreeMap使用了一种称为红黑树的数据结构。正是这种结构中数据的存储保证了数据存储的顺序。这棵树是什么？让我们来弄清楚吧！想象一下您需要存储数字-字符串对。数字 16、20、52、55、61、65、71、76、81、85、90、93、101 将是按键。如果您将数据存储在传统列表中并且需要查找键为 101 的元素，则需要迭代所有 13 个元素才能找到它。对于 13 个元素来说，这并不重要；当处理 100 万个元素时，我们就会遇到大麻烦。为了解决此类问题，程序员使用稍微复杂的数据结构。因此，来认识一下红黑树吧！

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

所需元素的搜索从树的根开始，在我们的示例中为 61。接下来，与所需值进行比较。如果我们的值较小，我们就向左走，如果值较大，我们就向右走。这种情况会发生，直到我们找到所需的值或命中具有值的元素null（树的叶子）。红色和黑色用于使树更容易导航和平衡。构建红黑树时必须始终遵循以下规则：

• 根部应该是黑色的。
• 树的叶子应该是黑色的。
• 红色节点必须有两个黑色子节点。
• 黑色节点可以有任何子节点。
• 从节点到其叶子的路径必须包含相同数量的黑色节点。
• 添加新节点来代替叶子。

如果您一起查看规则 3、4 和 5，您可以理解着色节点如何加速树中的导航：通过黑色节点的路径总是比通过红色节点的路径短。因此，树的总大小由黑色节点的数量决定，这个大小称为“黑色高度”。红黑树是用不同的编程语言实现的。互联网上有很多 Java 的实现，因此我们不会详细讨论它，但会继续熟悉其功能TreeMap。

从 SortedMap 和 NavigableMap 接口派生的方法

就像HashMap，TreeMap它实现了接口Map，这意味着它TreeMap具有该接口的所有方法HashMap。但除此之外，TreeMap它还实现了接口SortedMap和NavigableMap，并从中获取了附加功能。 — 扩展并添加与排序数据集相关的方法的 SortedMap接口：Map

• firstKey()：返回map第一个元素的key；
• lastKey()：返回最后一个元素的键；
• headMap(K end)：返回一个包含当前元素的所有元素的映射，从开头到带有键 的元素end；
• tailMap(K start)：返回一个map，包含当前的所有元素，从该元素开始start，到end结束；
• subMap(K start, K end)：返回一个包含当前元素的所有元素的映射，从该元素开始start并以带有键 的元素结束end。

NavigableMapSortedMap— 扩展并添加在地图元素之间导航的方法的 接口：

• firstEntry()：返回第一个键值对；
• lastEntry()：返回最后一个键值对；
• pollFirstEntry()：返回并删除第一对；
• pollLastEntry()：返回并删除最后一对；
• ceilingKey(K obj)：返回大于或等于key obj的最小key k。如果不存在该键，则返回null；
• floorKey(K obj)：返回小于或等于key obj的最大key k。如果不存在该键，则返回null；
• lowerKey(K obj)：返回小于键 obj 的最大键 k。如果不存在该键，则返回null；
• higherKey(K obj)：返回大于键 obj 的最小键 k。如果不存在该键，则返回null；
• ceilingEntry(K obj)：与ceilingKey(K obj)方法类似，但返回一个键值对（或null）；
• floorEntry(K obj)：与floorKey(K obj)方法类似，但返回一个键值对（或null）；
• lowerEntry(K obj)：与lowerKey(K obj)方法类似，但返回一个键值对（或null）；
• higherEntry(K obj)：与higherKey(K obj)方法类似，但返回一个键值对（或null）；
• descendingKeySet()：返回一个 NavigableSet，其中包含所有按相反顺序排序的键；
• descendingMap()：返回一个 NavigableMap，其中包含所有按相反顺序排序的对；
• navigableKeySet()：返回一个 NavigableSet 对象，其中包含按存储顺序排列的所有键；
• headMap(K upperBound, boolean incl)：返回一个包含从开头到 upperBound 元素的对的映射。incl 参数指定 upperBound 元素是否应包含在返回的映射中；
• tailMap(K lowerBound, boolean incl)：功能与上一个方法类似，仅返回从 lowerBound 到末尾的对；
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl)：与前面的方法一样，返回从 lowerBound 到 upperBound 的对，参数 lowIncl 和 highIncl 指定是否在新映射中包含边界元素。

在实现本身中TreeMap，除了我们熟悉的构造函数之外，还添加了一个，它接受比较器的实例。该比较器将负责元素的存储顺序。

使用 TreeMap 的示例

如此丰富的附加方法似乎没有必要，但事实证明它们往往比最初看起来更有用。让我们和你一起看一下这个例子。想象一下，我们在一家大公司的营销部门工作，我们有一个我们想要向其展示广告的人员的数据库。这有两个细微差别：

• 我们需要跟踪每个人的印象数；
• 向未成年人展示广告的算法是不同的。

让我们创建一个类Person来存储我们可以获得的有关一个人的所有信息：

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

我们在类中实现逻辑Main：

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

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Main在我们创建的 类中TreeMap，其中key是特定人员，value是本月的广告展示次数。在构造函数中，我们传递一个比较器，它将按年龄对人们进行排序。map用随机值填充。现在我们需要在我们的迷你数据存储中获取第一个成人的引用。我们使用 Stream API 来完成此操作。之后，我们得到两个独立的地图，我们将其传递给显示广告的方法。有很多很多方法可以解决这个问题。该课程的方法库TreeMap允许您发明适合各种口味的解决方案。没有必要全部记住它们，因为您始终可以使用开发环境中的文档或提示。就这样！我希望你现在已经清楚了这门课TreeMap，并能在解决实际问题中找到准确的应用。