Java 中的树图

如果您正在阅读本文，您很可能熟悉 Map 接口以及可以适当应用的位置。如果没有，那就来这里。今天我们将讨论 Java TreeMap 实现的特点，更具体地说，它与 HashMap 有何不同以及如何正确使用它。

比较 TreeMap、HashMap 和 LinkedHashMap

Map 接口最常用的实现是 HashMap。它易于使用并保证快速访问数据，因此它是解决大多数问题的最佳选择。大多数，但不是全部。有时您需要以结构化方式存储数据并能够在其中导航。在这种情况下，Map 接口的另一个实现 (TreeMap) 可以派上用场。TreeMap 实现了NavigableMap接口，它继承了SortedMap，而 SortedMap 又继承了 Map 接口。 通过实现NavigableMap和SortedMap接口，TreeMap 获得了 HashMap 所没有的额外功能，但它在性能方面付出了代价。还有LinkedHashMapclass ，它还允许您以特定顺序存储数据（将数据添加到地图的顺序）。要了解这三个类之间的差异，请查看此表： 如您所见，这些类有很多共同点，但也有一些不同之处。虽然 TreeMap 类是最通用的，但它不能总是将null存储为键。此外，访问 TreeMap 的元素花费的时间最长。因此，如果您不需要按某种排序顺序存储数据，最好使用HashMap或LinkedHashMap。

红黑树

您可能注意到，在幕后，TreeMap 使用一种称为红黑树的数据结构。以这种结构存储数据正是提供数据排序的原因。那么这是什么树呢？让我们弄清楚！想象一下，您需要存储数字-字符串对。数字 16、20、52、55、61、65、71、76、81、85、90、93 和 101 将成为密钥。如果将数据存储在传统列表中，并且需要查找键为 101 的元素，则需要逐步遍历所有 13 个元素才能找到它。对于 13 个元素，这没什么大不了的，但是当处理一百万个元素时，我们就会遇到大问题。为了解决这些问题，程序员使用稍微复杂一点的数据结构。这就是红黑树出场的地方！搜索元素从树的根开始，在我们的例子中是 61。然后我们将节点值与我们要查找的值进行比较。如果我们的价值较小，那么我们就往左走；如果它更大，那么我们就往右走。重复此过程，直到我们找到所需的值或遇到值为null的元素（树的叶子）。红色和黑色用于简化树的导航和平衡。构建红黑树时必须始终遵守以下规则：

• 根必须是黑色的。
• 树的叶子必须是黑色的。
• 一个红色节点必须有两个黑色子节点。
• 黑色节点可以有任何颜色的子节点。
• 从节点到其叶子的路径必须包含相同数量的黑色节点。
• 新节点被添加到叶子中。

如果将规则 3、4 和 5 一起考虑，您就会理解节点颜色如何让我们更快地导航树：通过黑色节点的路径总是比通过红色节点的路径短。因此，树的总大小由黑色节点的数量决定，称为“黑色高度”。红黑树数据结构在各种编程语言中都有实现。Java的实现网上有很多，这里就不多说了。相反，让我们继续了解 TreeMap 的功能。

来自 SortedMap 和 NavigableMap 接口的方法

和HashMap一样，TreeMap实现了Map接口，也就是说TreeMap拥有HashMap存在的所有方法。但是 TreeMap 还实现了SortedMap和NavigableMap接口，因此从中获得了额外的功能。SortedMap是一个扩展Map并添加与排序数据集相关的方法的接口：

• firstKey()：返回地图中第一个元素的键
• lastKey()：返回最后一个元素的键
• headMap(K end) : 返回一个包含当前地图所有元素的地图，从开始到键为end的元素
• tailMap(K start)：返回一个包含当前地图所有元素的地图，从开始元素到结束
• subMap(K start, K end)：返回一个包含当前地图所有元素的地图，从开始元素到以end为键的元素。

NavigableMap是一个扩展 SortedMap 的接口，并添加了在地图元素之间导航的方法：

• firstEntry()：返回第一个键值对
• lastEntry()：返回最后一个键值对
• pollFirstEntry()：返回并删除第一对
• pollLastEntry()：返回并删除最后一对
• ceilingKey(K obj)：返回大于或等于键obj的最小键k。如果没有这样的键，则返回 null
• floorKey(K obj)：返回小于或等于键obj的最大键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参数表示返回的map中是否包含upperBound元素
• tailMap(K lowerBound, boolean incl) : 功能类似于之前的方法，只返回从 lowerBound 到末尾的对
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl)：与前面的方法一样，返回从 lowerBound 到 upperBound 的对；参数 lowIncl 和 highIncl 指示是否在新地图中包含边界元素。

除了通常的构造函数之外，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;
   }
}

我们在主类 中实现逻辑：

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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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是这个月的广告展示次数。我们向构造函数传递一个按年龄对人进行排序的比较器。我们用任意值填充地图。现在我们想在我们的小数据存储库中获取对第一个成年人的引用。我们使用 Stream API 来做到这一点。然后我们得到两个单独的地图，我们将其传递给显示广告的方法。我们可以通过多种方式完成这项任务。TreeMap 类的方法库使我们能够为各种需要创建自定义解决方案。您不需要全部记住它们，因为您始终可以使用 IDE 中的文档或提示。 为了巩固您所学的知识，我们建议您观看我们的 Java 课程中的视频课程 目前为止就这样了！我希望您现在已经清楚 TreeMap 类，并希望您在解决实际编码任务时正确应用它。