Java TreeMap的内部工作原理

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

Java中TreeMap的内部工作原理

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

红黑树和TreeMap的关系

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

每个节点包含一个额外的位，表示为红色或黑色。这些颜色用于确保树保持平衡。
根节点的颜色始终为黑色。
红色节点不能有与其相邻节点相同颜色的节点。
从根节点到null的路径上，黑色节点的数量必须相同。

Java TreeMap的内部工作原理

现在，让我们看一下TreeMap的结构：

Java TreeMap的内部工作原理

如果我们向TreeMap添加一个元素，它将添加第一个条目在第一位置。从第二个元素开始，它将检查当前条目的键是大于还是小于前一个条目。具有较小值的键将添加到父条目的左边，而具有较大值的键将添加到右边。

TreeMap的构造函数

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

TreeMap(): 创建一个空的TreeMap集合。
TreeMap(Map mapInstance): 可以使用另一个地图的条目创建一个树图。
TreeMap(Comparator comparatorInstance): 允许我们创建一个使用比较器进行排序的空树图。
TreeMap(SortedMap sortedmapInstance): 我们也可以使用排序地图中的条目创建一个树图。

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

示例

在以下示例中，我们将创建一个空的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