Shulou(Shulou.com)06/01 Report--

This article is to share with you about how to analyze the TreeMap source code, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Today we are going to learn a new set called TreeMap. The bottom layer of TreeMap is not realized by hash table, but is stored by a new data structure, red-black tree structure. Now let's briefly introduce the relevant knowledge of the red-black tree.

The basic concept of red-black tree

Red-black tree is also called red-black binary tree, so it is also a kind of binary tree, which not only has the basic characteristics of binary tree, but also has its own unique characteristics. A binary tree is a tree structure with at most two child nodes in each tree node. And the child nodes of the binary tree are divided into left and right, and the value of the left node is smaller than that of the right node. As a result, data stored through the binary tree structure is fast to retrieve elements, because when retrieved from the root node, nearly half of the data is filtered (ideally). And the red-black tree is a balanced binary tree, which is also a characteristic of the red-black tree. Let's take a look at what a balanced binary tree is.

Red and black tree characteristics

The balanced binary tree mainly has the following characteristics: it is an empty tree or the absolute value of the height difference between its left and right subtrees is not more than 1, and the left and right subtrees are also a balanced binary tree. To put it bluntly, red-black tree is an implementation algorithm of balanced binary tree. In addition, there are AVL, Treap, stretching tree, SBT and other algorithms. (the main source is Baidu encyclopedia)

Let's go on to introduce other features of the red-black tree, which, as its name implies, ensures the balance of the tree by setting states such as red or black. So the main characteristics of the red-black tree are as follows:

Each node can only be red or black

The root node must be black

Each leaf node (NIL or NULL) is black

If a node is red, its child nodes must be black (all nodes)

All paths from a node to the descendants of that node contain the same number of black nodes

The rotation of the red-black tree

Above are the relevant characteristics of the red-black tree, that is to say, the red-black tree must have all the above characteristics at all times. But in our daily development, we often need to add or remove elements to the collection, so when performing the above operations, it will inevitably destroy the relevant characteristics of the red-black tree, so what should we do at this time? In fact, whenever we perform add or delete operations, if the characteristics of the red-black tree are destroyed, then the tree will be rotated to ensure the relevant characteristics of the red-black tree. The rotation of the red-black tree is mainly divided into left-handed and right-handed. Let's take a look at the specific implementation.

Left-handed

The left-handed logic of the red-black tree is to set the parent node of the left-handed node to its own left node, and then set the original left node to the right node of the new left node.

Dextral rotation

The right-handed logic of the red-black tree is to set the parent node of the right-handed node to its own right node, and then set the original right node to the left node of the new right node.

Now that we know all about the red-black tree, let's analyze the underlying source code of TreeMap to see how the bottom layer of TreeMap implements the logic of the red-black tree. Like other collections, let's first look at the initialization of TreeMap.

The above is the no-parameter constructor for TreeMap, and we found that when we create the TreeMap object through the parameter constructor, we do not initialize the underlying tree structure, but just set the comparator to null. So according to the rules we summed up when we analyzed other collections in the past, the initialization of TreeMap must be performed when the put method is called for the first time. Let's focus on the put method in TreeMap.

Let's take a look at the specific logic of the fixAfterInsertion method mentioned above, that is, the specific implementation of left-handed and right-handed methods.

The specific logic of left-handed and right-handed is not analyzed in detail here, the main implementation logic is what is mentioned above, left-handed means that the parent node of the node to be left-handed is set to its own left node, and then the original left node is set as the right node of the new left node. Right-hand rotation means that the right-handed parent node is set to its own right node, and then the original right node is set to the left node of the new right node.

Summary

Saving to TreeMap collections using null as key is not allowed in TreeMap

When we analyze the source code, we don't find the synchronization keyword synchronized, which means that TreeMap is not a thread-safe collection class either.

When we analyze the source code, we know that TreeMap will compare key every time we add elements, so when we use the TreeMap collection, we must make sure that the elements stored in TreeMap are comparable, otherwise the virtual machine will throw a field directly. For example

The above is how to parse the TreeMap source code, and the editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.