omg

The short term of the school has just ended, and there are still many days left before the school begins. It is a waste of time to stay in the dormitory and play games, so I wanted to see the source code of HashMap. Although I’ve never been in an interview, Java programmers know that HashMap is a must-ask for an interviewer, and since I’ve only been using HashMap at a basic level, I felt it was important to take a closer look at the underlying principles of HashMap. In HashMap, I think the most difficult should be red-black tree, I combined the code and drawing software research for two days, finally summed up the law, now share with you

First, the characteristics of red-black trees

So here are the five properties of red-black trees, just to give you an idea of what these properties are, and I’ll mention them a couple of times in graphic form to help you remember them

  • Each node is either red or black
  • The root node must be black
  • The leaf node must be black (the leaf node is usually not drawn, on the end node, there is no content)
  • The two children below the red node must be black
  • There are equal numbers of black nodes in any path from root to leaf

After the node is inserted into the red-black tree, if the red-black tree is unbalanced (the whole tree does not meet any of the five properties above), the operation of discoloration and rotation will be carried out until the red-black tree is balanced, and the difficulty of learning the red-black tree is the rules of discoloration and rotation

Second, the advantages of red-black trees

When it comes to the advantages of red-black trees, we have to take out AVL trees for comparison.

AVL tree is a completely balanced tree, the difference between the maximum root depth and the minimum root depth is no more than 1, and the search efficiency is relatively high, while red black tree is not completely balanced tree, the search efficiency is slightly lower than AVL tree

The insertion and deletion operation of red-black tree is much faster than that of AVL tree, because red-black tree guarantees that the insertion and deletion need at most three rotations to reach the balance, while AVL tree will carry out a large amount of balance calculation every insertion and deletion, which is very expensive

Therefore, red-black trees sacrifice a little bit of search efficiency for faster insert and delete operations, and overall, red-black trees perform better than AVL trees

How to balance red-black tree insertion

3.1 Basic rules for Red-black Tree Insertion

  1. The newly inserted node is red
  2. If the parent node is black, or the parent node is the root node, insert it directly
  3. The parent node is red and needs to change color and rotate (i.e., two connected red nodes are out of balance)
  4. If the grandparent appears after a balance and the grandparent’s father is red, then treat the grandparent as a new node and continue to change color and flip, knowing global equilibrium (recursive thinking)

3.2 Color-changing rules of red-black trees

In the basic rule, it is mentioned that two consecutive red nodes need to change color and rotate, so let’s ignore the rotation for the moment, let’s look at the color change rules of red-black trees

3.2.1 The new node does not have an uncle node, or the uncle node is black

In this case, we just need to make the parent node black and the grandfather node red

In this case, not only the parent node becomes black, the grandfather node becomes red, but also whether the grandfather node is the root nodeBasic rules for red-black tree insertionNumber two says,The root node must be black, so if the grandfather node is the root node, you need to change color again to make the root node black

3.2.2 The uncle node of the new node is red

In this case, the color of the uncle node and the parent node turns black, and the grandfather node turns red. After the change, it is necessary to consider whether the grandfather node is the root node, and then change color again depending on the situation

3.2.3 summary

  1. Because the new node is red, when the parent node is red, there are successive red nodes, resulting in imbalance and color change

  2. In the case of discoloration, the uncle node and the parent node must turn black, the uncle node does not consider it, and the grandfather node must turn red

  3. After the grandparent node turns red, you need to consider whether it is the root node, and if it is the root node, the root node turns black

3.3 Red-black tree rotation rules

In the last video, we figured out how a red black tree changes color, but now let’s look at the rotation rules for a red black tree, and I’m not going to describe how it changes color, I’m just going to describe how a red black tree rotates, okay

There are four cases of red-black tree rotation:

  1. left-handed
  2. Right hand
  3. First left, then right
  4. First turn right, then turn left

Left-handedness and right-handedness are pretty much the same thing, but the direction is changed, and if you look at left-handedness and you can see how right-handedness works, then it’s pretty straightforward, right

3.3.1 left-handed

First of all, there are two cases where left-handed rotation occurs

  • Both the new node and the parent node are to the right
  • The parent node is on the left and the new node is on the right

The second one is a little bit more complicated, and I’ll think about that after I write left and right, because it involves both left and right

So let’s first look at how left-handed it is when the new node and the parent are both right

Diagram 1

In this case, left-handed nodes are grandparent nodes, and grandparent nodes turn left to become the parent left child.

Diagram 2

This is a slightly more complicated case, where the grandfather rotates to the left and becomes the left child of the parent

But if the parent has a left child (that is, a sibling), that sibling becomes the right child of the grandfather.

If the left child of the ancestor node is the grandfather node, then the left child of the ancestor node becomes the parent node. If the right child of the ancestor node is the grandfather node, then the right child of the ancestor node becomes the parent node after rotation.

3.3.2 rainfall distribution on 10-12 right-handed

There are also two cases where dextral rotation occurs

  • Both the new node and the parent node are to the left
  • The parent node is on the right and the new node is on the left

The operation of right-handed rotation is very similar to that of left-handed rotation, but the direction has been changed. I will not explain it in detail here. You can understand it by yourself by looking at the picture

Diagram 1

Diagram 2

3.3.3 First left rotation, then right rotation

This is a complicated situation, so I don’t have to do this How to understand?

As you can see, the new node, the parent node, and the grandfather node are not on the same line. As you can see from the figure, the idea is to rotate the three nodes to a straight line, and then apply the left and right rotation we talked about above to achieve balance, so there are two steps of rotation

Step 1 Rotate

The rotated node in the first step is different from the node in the previous section. In the previous section, the rotated node was the grandfather node. In this section, the rotated node is the parent node (the parent node is rotated left down and the child node is rotated left up).

Step 2 Spin

The second step is the right rotation mentioned above, slowly experience yourself

How do you remember?

So what we’re looking at here is we’re looking at left-handed or right-handed, and we’re going to show you a way to figure out which side the parent is on, the parent is on the left, the parent is left-handed, the parent is on the right, the parent is right-handed, isn’t that easy

Color changing process

We used to do color change in the first step, but in this case we did it in the second step, so when we look at this picture, we have to think of it like this, left rotation + color change + right rotation, and then it’s easy to remember

First right rotation, then left rotation

This is also the caseFirst left, then rightAlmost the same, but the direction changed, but here more verbose, we see the picture slowly experience

3.3.5 section

  1. When the grandfather node, the parent node and the new node are in a straight line, left-rotation and right-rotation occur, and the parent node and the child node are left and right-rotation. Parent and child nodes are rotated to the right and left

  2. When the grandfather node, the parent node, and the new node are not in a straight line, rotate the parent node so that it and its child nodes are on the left or right, and then change color, and then rotate. Parent on the left, left-handed + discoloration + dextral, parent on the right, dextral + discoloration + left-handed

Four red black tree left – rotation rules are summarized in detail

Five red black tree insertion rules are summarized in detail

Six, experience

The source code for HashMap has changed a lot between the 1.7 and 1.8 versions. It is recommended that you look at the 1.7 source code first and then the 1.8 source code. To tell the truth, I just started 1.7 source don’t understand, later found a talk JDK1.7 in the HashMap source video, speak very good, after watching the video, and then look at their own source, it is very feeling. After looking at 1.8 source code I have not seen the video, they can understand

So to be honest, I don’t have a reference for the balance of the red-black tree rule anyone else to write articles, I also try to see other people write articles about the red-black tree, but I still think the node color spinning process is too complicated, understand and remember to pass the article is very difficult, so I chose to see the source code yourself summary regularly

Later, I understood all these processes and wrote them down. I wrote them down through the combination of understanding and skills, which I will also mention in this article, not by rote memorization

Finally, be sure to record what you have learned like I have, so that you can see it for yourself and share it with those who need it. This is a two-stone thing.

Vii. Words to readers

Next, I will summarize the balancing rules for removing HashMap red black trees, and I will share them with you at that time

How to article where there are mistakes, or questions, you must write down in the comment area, I will timely reply to you and modify the error, thank you