Java 中 TreeMap 的内部工作原理

javaobject oriented programmingprogramming更新于 2024/9/30 11:24:17

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

Java 中 TreeMap 的内部工作原理

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

红黑树与TreeMap的关系

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

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

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

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

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

现在,让我们看看 TreeMap 的结构:

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

TreeMap 的构造函数

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

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

  • TreeMap(Map mapInstance):我们可以使用来自另一个映射的条目创建一个树形映射。

  • TreeMap(Comparator comparatorInstance):它允许我们创建一个将使用 Comparator 进行排序的空树形映射。

  • TreeMap(SortedMap sortedmapInstance):我们还可以使用来自排序映射的条目创建一个树形映射。

让我们讨论几个例子,以便更好地理解上面讨论的要点。

示例

在下面的例子中,我们将创建一个空的 TreeMap,然后使用'put()' 方法。我们将使用 for-each 循环打印其详细信息。结果将按排序顺序排列。

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
        // 创建 TreeMap
        TreeMap<String, Integer> TrMap = new TreeMap<>();
        // 在映射中添加元素
        TrMap.put("Kurti", 4000);
        TrMap.put("Shirt", 3000);
        TrMap.put("TShirt", 1500);
        TrMap.put("Watch", 2000);
        TrMap.put("Perfume", 2500);
        // 打印映射的详细信息
        System.out.println("映射的元素:");
        // 遍历映射
        for (String unKey : TrMap.keySet()) {
        // 打印每个节点的详细信息
        System.out.println("Item: " + unKey + ", Price: " + TrMap.get(unKey));
        }
        String frstKey = TrMap.firstKey(); // 访问第一个键
        String lstKey = TrMap.lastKey(); // 访问最后一个键
        System.out.println("访问 Map 中第一个键的名称:" + frstKey);
        System.out.println("访问 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 的工作原理。


相关文章


有用资源