Early in the morning to see a good article, from the source code very detailed explanation of the red black tree tree process, especially to do an article of the porter, share to dig friends, the end of the text with the original address!
The interview with force
Self improvement
An overview of the
HashMap is the most frequently used data type for mapping (key-value pair) processing by Java programmers. With the Java Developmet Kit (JDK) update, JDK1.8 has made improvements to the underlying implementation of HashMap, such as introducing red-black tree data structures and scaling optimizations. This article mainly analyzes the process of treifying red-black trees in HashMap.
Red Black Tree
A node is marked red or black. The roots are black. If a node is red, then its children must be black (that’s why it’s called a red-black tree). Every path from a node to a null reference must contain the same number of black nodes (so red nodes don’t matter). The RB Tree has a lot in common with the famous AVL Tree, but the hard part is inserting a new item into the Tree. Those of you who know AVL Tree know that in order to maintain the height of the Tree you have to change the structure of the Tree after you insert a new item, and this is mainly by rotation, as it is in RB Tree.
Two rotations and a typical transformation
Direction of rotation:
Transformation process:
Interrelated:
Unidirectional association:
Red nodes:
Black nodes:
It’s a part of the red-black tree, maybe a node, maybe a subtree, that doesn’t break the structure of the current tree. This part will be rotated to the back of the other nodes, and we can think of it as falling on the following node due to gravity:
- One rotation transformation.
- Double spin conversion, ie requires two single rotations in the opposite direction
- Perform a color change when both subpoints are red, because if the insert is red it will cause a conflict. If the children on both sides of the root node are red, the two leaves become black, the root node becomes red, and then the root node becomes black.
The three typical transformations in a red-black Tree are described in the figure above, and the first two transformations are actually the two typical transformations in an AVL Tree.
A few questions
Why do we rotate?
Since both P and X nodes are red, this breaks the rule that everything below the red node must be black.
New nodes are always red. Why is that?
Since the tree structure before insertion is already constructed, once we add black nodes, no matter where we add them, the number of black nodes on the original path will be destroyed, so inserting red nodes is the right choice.
Why do I change colors?
Rotation as the first one new node X destroyed the red-black tree structure have to rotate, the back is rotated, the result of the new structure is formed after rotation, we found two child nodes are red so to perform the third transformation characteristics of color transformation, because if the child node is red so we only can add black when add node, However, adding any black leaf nodes breaks the fourth property of the tree, so transform it. The leaves are red when you transform them and the default leaves that we’re adding are red, so adding a black node doesn’t break the fourth structure of the tree, so this transformation is useful.
In the second kind of double transformation, how does the red node appear inside the tree? It is because of the color change above that the new color changed node conflicts with its parent node.
Compared to AVL trees? The advantage over AVL trees is that you do not have to store a node height variable in the node class, saving memory.
And red-black trees are generally implemented not recursively but in a loop.
Normal operations take order logN time in the worst case.
With these basic concepts in mind, let’s take a look at the implementation of the code in HashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
{
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else
{
Node<K, V> e;
K k;
if (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p;else if(p instanceof TreeNode) e = ((TreeNode<K, V>) p).putTreeval (this, TAB,hash, key, value);
else
{
for (int binCount = 0;; ++binCount)
{
if ((e = p.next) == null)
{
p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD = 8, determine if the current bucket location list is longer than 8 and change the list to a red-black tree.if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))break; p = e; }}if(e ! = null) { // existing mappingfor key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e);return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeThe above methods by hash calculation inserted into the slot of the item, if you have the same key, according to the set parameters are executed, if the corresponding slot empty directly inserted, if one is corresponding to the slot of judgment is red and black tree or list structure slot structure, list it down the list to find if found the same key, according to the parameter selection, If the list is not found, the link is at the end of the list. If the number of items in the list is greater than 8, the list is treed. If the list is a red-black tree, the items are added in the way of adding the tree.
Let’s take a look at the treeifyBin method.
final void treeifyBin(Node<K, V>[] tab, int hash)
{
int n, index;
Node<K, V> e;
if(TAB = = null | | (n = TAB. Length) < MIN_TREEIFY_CAPACITY) / / resize () method but more about here, can go to look at the links of interest. resize(); / / byhashFind the position of the bucket.else if ((e = tab[index = (n - 1) & hash]) != null)
{
TreeNode<K, V> hd = null, tl = null;
do{// Wrap each node as a TreeNode. TreeNode<K, V> p = replacementTreeNode(e, null);if (tl == null)
hd = p;
else{// Link all treenodes together. p.prev = tl; tl.next = p; } tl = p; }while((e = e.next) ! = null);if((tab[index] = hd) ! = null) // Treenodes the list. hd.treeify(tab); }}Copy the codeAnd what you do in finding a way is you join the last nine items together in a linked list, and you build a red-black tree from that.
Before looking at the code, let’s take a look at TreeNode
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V>
{
TreeNode<K, V> parent; // red-black tree links
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K, V> next)
{
super(hash, key, val, next); } final void treeify(Node<K,V>[] tab) { // ...... } static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { // ...... } static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { // ...... } static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { // ...... } / /... Omit other methods}Copy the codeAs you can see, the real way to maintain the red-black tree structure is not in the HashMap, but in the TreeNode class.
Let’s look at the Treeify code
final void treeify(Node<K, V>[] tab) { TreeNode<K, V> root = null; / / toforLoop through the list we just created.for(TreeNode<K, V> x = this, next; x ! = null; X = next) {// next push forward. next = (TreeNode<K, V>) x.next; x.left = x.right = null; // Assign a value to the root node.if (root == null)
{
x.parent = null;
x.red = false;
root = x;
} else{// x is an entry in the current access list. K k = x.key; int h = x.hash; Class<? > kc = null; // At this point, the red-black tree already has a root node, which obtains the key sum of the items currently added to the red-black treehashValue goes into the core loop. // We start at root and iterate through the additions in a top-down manner. //forLoop has no control condition by code insidebreakBreak out of the loop.for(TreeNode<K, V> p = root;;) {// dir: directory, compare the added item with the access node in the current treehashValue to determine the path of the added item. -1 is the left subtree and +1 is the right subtree. / / ph: the parenthash. int dir, ph; K pk = p.key;if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); // xp: x parent. TreeNode<K, V> xp = p; // Find a node that matches the x addition criteria.if((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; // If xphashValues greater than xhashValue, adding x to the left of XP.if(dir <= 0) xp.left = x; // Add the opposite to the right of XP.elsexp.right = x; // Maintain the red-black structure of the added red-black tree. root = balanceInsertion(root, x); The current list item was successfully added to the red-black tree.break; }}}} // Ensures that the given root is the first node of its bin. moveRootToFront(tab, root); }Copy the codeThe first loop will take the first node of the list as the root of the red-black tree, and the next loop will compare hash values and connect items to the left or right side of the tree. Insertion may break the tree structure, so then balanceInsertion will be done.
We see balanceInsertion
Static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) { Does not destroy the structure of the tree. x.red =true; // These variable names are not defined by the author. // xp: x parent; // XPPL: x parent parent left; // XPPL: x parent parent left; // XPPR: x parent parent right;for(TreeNode<K, V> xp, xpp, xppl, xppr;;) {// If the parent node of x is null, there is only one node. The root node is black, red =false.if ((xp = x.parent) == null)
{
x.red = false;
returnx; } / / to enterelseNote It is not the root node. // If the parent node is black, the red x node can be added directly after the black node, returning the root without any additional operations. // If the parent node is red but the grandparent node is empty, you can return the root directly. In this case, the parent node is the root node, because the root must be black.else if(! xp.red || (xpp = xp.parent) == null)returnroot; 1. X's parent node xp is red, so we have two red nodes connected, so we have to go through the rotation transformation. // 2. X's grandparent XPP is not empty. // Determine if the parent node is the left of the grandparent nodeif(xp = = (XPPL = XPP. Left)) {/ / parent node xp is judging XPPR / / grandfather grandfather left node of the node is not null and is a red right / / at this time of XPP node is red, so directly to the third transformation mentioned above, the two child nodes into a black, Turn XPP red and add red node X to the end of XP. // Why x = XPP? // This is because changing XPP to red may cause two red nodes to collide with the parent node of XPP. This forms the second rotation transformation, so the transformation must be done from the bottom up to the root. // So let x = XPP, and then go through the next layer, and then go up.if((xppr = xpp.right) ! = null && xppr.red) { xppr.red =false;
xp.red = false;
xpp.red = true; x = xpp; } // Enter thiselseIt says. // The parent node xp is the grandparent left node XPPR. // The right node of the grandparent XPP is either black or empty. By default, empty nodes are also black. X is the left or right node of XP.else{// XPP left -> XPP right ->x. This is obviously the second transformation that requires two rotations, so I'm going to do one first. // Here is the first rotation.if(x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } // Perform a rotation on a structure that is itself XPP left ->xp left ->x or is caused by the rotation above.if(xp ! = null) { xp.red =false;
if(xpp ! = null) { xpp.red =true; root = rotateRight(root, xpp); }}}} // the analysis method here and the previous relative name but all in the right test no longer repeat analysis.else
{
if(xppl ! = null && xppl.red) { xppl.red =false;
xp.red = false;
xpp.red = true;
x = xpp;
} else
{
if (x == xp.left)
{
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if(xp ! = null) { xp.red =false;
if(xpp ! = null) { xpp.red =true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
Copy the codeBy this point, if you have strong associative skills, you should have understood the main relationship of the transformations in this set.
Here is a brief description of the first two lucky situations
X itself is the root node returns x. The parent of x is black or the parent of x is the root. If the above two conditions are not met, it is time to transform, allow me to post a little more code…… It’s hard to analyze without code.
Color change
if (xp == (xppl = xpp.left))
{
if((xppr = xpp.right) ! = null && xppr.red) { xppr.red =false;
xp.red = false;
xpp.red = true; x = xpp; }}Copy the codeHere is a typical a black node of the two children are so red color transform, because insert node is red, when they tested the grandfather of the nodes around child nodes are red the conflicts with the two red, so first will be the color transform node, node to grandfather to red, then grandfather two child nodes into a black, So the red nodes that we insert don’t violate the rules of a red-black tree.
Anyone here will be a question that if my grandfather node is the root node, then grandfather node becomes black, because every time the operation of the cycle are inserted into the balance when the color transform will be inserted into the nodes of the reference is to grandfather node, when the next round of circulation will be preferred to detect whether the current node is the root node, If it is the root node then change the color to black, as shown below:
*** When pointing a node to the grandparent for the next loop:
Two core rotations (left and right)
1. X's parent node xp is red, so we have two red nodes connected, so we have to go through the rotation transformation. // 2. X's grandparent XPP is not empty. // Determine if the parent node is the left of the grandparent nodeif (xp == (xppl = xpp.left))
{
if((xppr = xpp.right) ! = null && xppr.red) {// ...... } // Enter thiselseIt says. // The parent node xp is the grandparent left node XPPR. // The right node of the grandparent XPP is either black or empty. By default, empty nodes are also black. X is the left or right node of XP.else{// XPP left -> XPP right ->x. This is obviously the second transformation that requires two rotations, so I'm going to do one first. // Here is the first rotation.if(x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } // Perform a rotation on a structure that is itself XPP left ->xp left ->x or is caused by the rotation above.if(xp ! = null) { xp.red =false;
if(xpp ! = null) { xpp.red =true; root = rotateRight(root, xpp); }}}}Copy the codeSo when you’re done with the color change you go to the else block below
Given that XP is the left node of XPP, we first determine whether X is the left node or the right node of XP. If x is the right node, it forms the following structure.
This structure requires a double rotation, first a left rotation.
Left rotation
1 static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p) 2 {3; 4 // pp: parent parent, parent of the parent node. 5 // rl: right left of the right node. 6 TreeNode<K, V> r, pp, rl; 7if(p ! = null && (r = p.right) ! = null) 8 { 9if((rl = p.right = r.left) ! = null) 10 rl.parent = p; 11if ((pp = r.parent = p.parent) == null)
12 (root = r).red = false;
13 else if (pp.left == p)
14 pp.left = r;
15 else16 pp.right = r; 17 r.left = p; 18 p.parent = r; 19} 20returnroot; 21}Copy the code1. When you first enter the method, the status is as shown in the figure below. (RL may be empty)
2. After entering the if block, execute after line 10.
9 if((rl = p.right = r.left) ! = null) 10 rl.parent = p;Copy the code
If RL is null, the right node of P is null. If RL is null, the right node of P is null.
3. Move on to lines 11 and 12.
11 if ((pp = r.parent = p.parent) == null)
12 (root = r).red = false;
Copy the codeFirst let’s look at the effect of the assignment statement in line 11, if.
Expressions inside if are executed regardless of the contents of the condition ().
If the conditions are met, 12 lines of code will be executed, resulting in the following result.
Because PP is empty, that’s all we have left.
4. If the condition in line 11 is false, execute line 13 after the expression in line 11 ()
13 else if (pp.left == p)
14 pp.left = r;
Copy the code
R and PP are related to each other.
5. Do not enter the else statement on lines 15 and 16 because lines 13 and 14 are entered.
15 else
16 pp.right = r;
Copy the code6. Look at lines 17 and 18.
17 r.left = p;
18 p.parent = r;
Copy the code
if (x == xp.right)
{
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
xpp = (xp = x.parent) == null ? null : xp.parent;
Copy the codeAfter executing the above code, rotate and adjust the relationship between X, XP, and XPP to get the following figure.
Right rotation
if(xp ! = null) { xp.red =false;
if(xpp ! = null) { xpp.red =true; root = rotateLeft(root, xpp); }}Copy the code1. First make XP black.
2. Red if XPP is not empty.
Since we passed XXP in rotateLeft(root, XPP), the following rotation is actually the same rotation for XP and XXP in the opposite direction.
Then we look at the code that rotates to the right
Static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p) {// l: left, left. // pp: parent parent, parent of parent node. // lr: left right, the right of the left node. TreeNode<K, V> l, pp, lr;if(p ! = null && (l = p.left) ! = null) {if((lr = p.left = l.right) ! = null) lr.parent = p;if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
Copy the code3. The structure is like this when you come in.
This P right here is the XPP that was passed in.
4. Here we think that LR exists, but it does not affect the main rotation. If it is null, it means null.
9 if((lr = p.left = l.right) ! = null) 10 lr.parent = p;Copy the code
5. In this case, if PP exists, the expression that has executed 11 will not execute line 12. (No more analyzing nonexistent situations).
11 if ((pp = l.parent = p.parent) == null)
12 (root = l).red = false;
Copy the code
15 else
16 pp.left = l;
Copy the code
17 l.right = p;
18 p.parent = l;
Copy the code
Is it?
You might think it’s not going to work but it looks like this, it looks like this before the right rotation.
Because we’re passing in XPP, so combined with the last rotation to the left we’re going to see the whole picture look like this when we rotated to the right. (Note: XPPP can be either the left or right parent of XPP. It doesn’t matter here, and it can be any color)
Now you can see why XPPP can be any color, because X is black after the rotation even if XPPP is red, and now we can transform the two red children, and then X and XPPP have a color conflict, and then we can rotate it all the way to the root.
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)
{
x.red = true;
for (TreeNode<K, V> xp, xpp, xppl, xppr;;)
{
if ((xp = x.parent) == null)
{
x.red = false;
return x;
}
else if(! xp.red || (xpp = xp.parent) == null)return root;
if(xp == (XPPL = xpp.left)) {// Insert position the parent is to the left of the grandparent. }else{// Insert position The parent is to the right of the grandparent. }}}Copy the codeWe’re looking at the insertion position where the parent is to the left of the grandparent, and we’re not looking at the symmetry on the other side, which is the same thing because we’re calling the same method.
The above is the newly introduced red-black tree treification process of HashMap in 1.8. Compared with the original linked list, when many entries are stored on the same bucket, the tree lookup structure is obviously more efficient than the linear linked list.
The original address: www.cnblogs.com/finite/p/82…
Sorry I lied to you, it can’t be finished in three minutes, hahahahahaha!