Java 中 TreeMap 的内部工作原理

TreeMap 是 Java 集合框架的一个类，它实现了 NavigableMap 接口。它以树状结构存储映射的元素，并提供了一种高效的替代方案，以排序顺序存储键值对。在内部，TreeMap 使用红黑树，这是一种自平衡二叉搜索树。TreeMap 必须实现 Comparable 接口或自定义 Comparator，以便它可以维护其元素的排序顺序，否则，我们将遇到 java.lang.ClassCastException。本文旨在解释 TreeMap 在 Java 中的内部工作原理。

Java 中 TreeMap 的内部工作原理

要了解 TreeMap 的内部工作原理，有必要概述红黑树算法，因为 TreeMap 使用它来存储元素。

红黑树与 TreeMap 的关系

红黑树是一种自平衡二叉搜索树，其属性如下所述

  • 每个节点包含一个额外的位，用红色或黑色表示。这些颜色用于确保树保持平衡。

  • 根节点的颜色始终为黑色。

  • 红色节点不能有另一个与它颜色相同的节点作为邻居。

  • 从根节点到空节点，所有路径上的黑色节点数必须相同。

现在，让我们看看 TreeMap 的结构

如果我们将一个元素添加到 TreeMap 中，它将首先将第一个条目添加到第一个位置。从第二个元素开始，它将检查当前条目的键是否大于或小于上一个条目。键值较小的元素将添加到父条目的左侧，键值较大的元素将添加到父条目的右侧。

TreeMap 的构造函数

要在我们的程序中使用 TreeMap 集合，我们首先需要创建 TreeMap 类的实例。为此，Java 提供了以下构造函数

  • TreeMap()：它将创建一个空的 TreeMap 集合。

  • TreeMap(Map mapInstance)：我们可以使用另一个映射中的条目创建一个 TreeMap。

  • TreeMap(Comparator comparatorInstance)：它允许我们创建一个空的 TreeMap，该 TreeMap 将使用 Comparator 进行排序。

  • TreeMap(SortedMap sortedmapInstance)：我们还可以使用排序映射中的条目创建一个 TreeMap。

让我们讨论一些示例，以便更好地理解上面讨论的要点。

示例

在下面的示例中，我们将创建一个空的 TreeMap，然后使用 'put()' 方法将一些元素存储到其中。我们将使用 for-each 循环打印其详细信息。结果将按排序顺序显示。

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
      // creating a TreeMap
      TreeMap<String, Integer> TrMap = new TreeMap<>();
      // Adding elements in the map
      TrMap.put("Kurti", 4000);
      TrMap.put("Shirt", 3000);
      TrMap.put("TShirt", 1500);
      TrMap.put("Watch", 2000);
      TrMap.put("Perfume", 2500);
      // printing the details of map 
      System.out.println("Elements of the map: ");
      // iterating through the map
      for (String unKey : TrMap.keySet()) {
         // printing details of each node
         System.out.println("Item: " + unKey + ", Price: " + 
TrMap.get(unKey));
      }
      String frstKey = TrMap.firstKey(); // accessing first key
      String lstKey = TrMap.lastKey(); // accessing last key
      System.out.println("Accessing name of first key in Map: " + 
frstKey);
      System.out.println("Accessing name of last key in Map: " + 
lstKey);
   }
}

输出

Elements of the map: 
Item: Kurti, Price: 4000
Item: Perfume, Price: 2500
Item: Shirt, Price: 3000
Item: TShirt, Price: 1500
Item: Watch, Price: 2000
Accessing name of first key in Map: Kurti
Accessing name of last key in Map: Watch

结论

我们从定义 TreeMap 开始本文，并在下一节中讨论了它的内部工作原理。TreeMap 使用红黑树来存储其元素，红黑树是一种可以自平衡的二叉搜索树。此外，我们还讨论了一个示例来说明 TreeMap 的工作原理。

更新于： 2023年7月20日

625 次查看

启动你的 职业生涯

通过完成课程获得认证

开始
广告