Java中TreeMap的内部工作原理

WBOY

发布时间：2023-08-26 11:41:16

849人浏览过

来源于tutorialspoint

转载

TreeMap is a class of Java Collection Framework that implements NavigableMap Interface. It stores the elements of the map in a tree structure and provides an efficient alternative to store the key-value pairs in sorted order. Internally, TreeMap uses a red-black tree, which is a self-balancing binary search tree. A TreeMap must implement the Comparable Interface or a custom Comparator so that it can maintain the sorting order of its elements otherwise, we will encounter a java.lang.ClassCastException. This article aims to explain how TreeMap works internally in Java.

Java中TreeMap的内部工作原理

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

Relation of Red Black Tree and TreeMap

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

每个节点都包含一个额外的位，由红色或黑色表示。这些颜色用于确保树保持平衡。
The color of root node is always black.
一个红色节点不能有与其邻居相同颜色的另一个节点
从根节点到空节点，所有路径上的黑色节点数量必须相同

Java中TreeMap的内部工作原理

Now, let's see the structure of TreeMap:

Java中TreeMap的内部工作原理

立即学习“Java免费学习笔记（深入）”；

杰易OA办公自动化系统6.0

基于Intranet/Internet 的Web下的办公自动化系统，采用了当今最先进的PHP技术，是综合大量用户的需求,经过充分的用户论证的基础上开发出来的，独特的即时信息、短信、电子邮件系统、完善的工作流、数据库安全备份等功能使得信息在企业内部传递效率极大提高，信息传递过程中耗费降到最低。办公人员得以从繁杂的日常办公事务处理中解放出来，参与更多的富于思考性和创造性的工作。系统力求突出体系结构简明

下载

If we add an element to the TreeMap, it will add the first entry in the first place. From the second element, it will check whether the key of current entry is greater or smaller than the previous entry. The keys with lower value will be added to the left and the ones with greater value will be added to the right of Parent entry.

TreeMap的构造函数

To use the TreeMap collection in our program, we first need to create an instance of the TreeMap class. For that Java provides the following constructors:

TreeMap(）：它将创建一个空的TreeMap集合
TreeMap(Map mapInstance): 我们可以使用另一个映射中的条目创建一个树映射
TreeMap(Comparator comparatorInstance)：它允许我们创建一个空的树映射，通过使用比较器进行排序。
TreeMap(SortedMap sortedmapInstance): We can also create a tree map with the entries from a sorted map.

Let's discuss a few examples to have a better understanding of the above discussed points.

Example

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

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
      // creating a TreeMap
      TreeMap 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);
   }
}

Output

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