[introduction to Java] Day30 detailed explanation of Java container class (XII) detailed explanation of treemap

Today, let's take a look at another general of the map family - treemap. Two generals of the map family have been introduced earlier, namely HashMap and LinkedHashMap. HashMap can efficiently find and store elements. LinkedHashMap can orderly traverse elements on the basis of efficient search. What are the characteristics of treemap? Don't worry, don't worry. You'll know after reading this article.

@H_ 301_ 2@

This chapter mainly introduces treemap from the following aspects:

1. Treemap features and use of chestnuts

2. Introduction to treemap inheritance structure

3. Treemap source code analysis

This article is expected to take 10 minutes. Please allocate your time reasonably.

1、 Treemap features and use of chestnuts

Yes, it's the red and black tree that makes you want to be immortal and die, but don't panic. It's the same as the red and black tree when you introduced HashMap before. Therefore, I don't intend to introduce it again in this article. If you forget the content of the red and black tree, you can move your little hand and turn it forward.

Let's take a look at the use of small chestnuts in treemap.

The output is as follows:

You can see that the default key values of the elements placed in the treemap are arranged in ascending order. The key value type here is string, and the CompareTo method of string is used for comparison and sorting. Submap returns the submap of the current map, as do headmap and tailmap,

2、 Introduction to treemap inheritance structure

Treemap inherits from abstractmap and implements the navigablemap interface. The inheritance diagram is as follows:

I believe you are no stranger to abstractmap. HashMap also inherits from abstractmap, which has some default implementations of the map interface. Here we can see two new interfaces SortedMap and navigablemap. SortedMap interface inherits from the map interface, which can be seen from the name. Compared with the map interface, SortedMap has the function of sorting, and there are not many internal methods. Just have a simple understanding

Navigablemap interface inherits from SortedMap interface and mainly provides the following navigation methods:

After saying so much, there is no nutrition. Next, let's talk about real dry goods.

3、 Treemap source code analysis

There are more than 2000 lines of treemap source code in JDK 1.8, which is still quite a lot. Therefore, this paper does not intend to analyze all the source code sentence by sentence, but selects several commonly used internal classes and methods for analysis. The functions realized by these methods are search, traversal, insertion, deletion, etc. other methods can be analyzed by the partners who are interested. The core part of treemap implementation is about the implementation of red black tree. Most of its methods are basically a package for the addition, deletion and query operations of the underlying red black tree. As mentioned earlier, as long as you understand the principle of red black tree, treemap has no secret. For the principle of red black tree, please refer to the previous article on HashMap red black tree, which will not be discussed in this article.

The main data structure of treemap is the red black tree, and the bearer of this red black tree structure is the internal class entry. Let's take a look at this entry class first:

In fact, the internal structure is also very simple, mainly including key, value and three references to the left child, the right child and the parent node respectively, as well as the color member variable used to identify the color. Let's look at several important member variables in treemap:

Comparator is used to sort the keys in the map. Root points to the root node of the red black tree. Size indicates the number of key value pairs. Modcount is believed to be familiar, indicating the number of times the internal structure has been modified. Red and black are two internal constants, namely red and black. False indicates red and true indicates black. Entryset is the set of key value pairs, navigablekeyset is the set of keys, and the last descendingmap is an inverted map of the current map.

There are many internal classes in treemap. You can see the figure first:

There are 18 internal classes, but don't panic. In fact, more than half (10) of them are related to iterators, four are related to sub maps, and the remaining four are related to internal collections. Let's take a look at the most commonly used methods:

In fact, the logic here is very similar to the insertion logic of treenode in HashMap. It is to find the location to be inserted first, and then adjust the structure. The structure adjustment here, that is, the structure adjustment of red black tree, has been described in detail in HashMap earlier. It will not be repeated here. The adjustment process is exactly the same.

Having finished inserting, let's look at the deletion operation.

Well, compared with the deletion operation of HashMap, the core steps are exactly the same, so you can eat it according to the detailed explanation of red and black trees in HashMap.

This is the end of this article=

Recently, I've had a lot of troubles and thought a lot about the development direction. I want to do a lot of things, which makes me stop. However, many things can't come in a hurry. I'd better write a blog and summarize and share more.

Opportunities are reserved for those who are prepared.