Java 中 TreeMap 的内部工作原理
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 的工作原理。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

