ConcurrentHashMap implementation process, it is mentioned that during the PUT operation, if the elements in the linked list structure exceed the TREEIFY_THRESHOLD (default is 8), the linked list will be converted to a red-black tree, which is easy to improve the query efficiency. The code is as follows:
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
Copy the codeRed and black tree
First, the basic concept of red-black tree: red-black tree is a special balanced binary tree, mainly used to store ordered data, provide efficient data retrieval, time complexity O(LGN). Red-black trees each node has an identifying bit for color, red or black, with five characteristics:
1. Each node is either red or black 2. The root node is black 3. Leaf nodes are NIL nodes, i.e. empty nodes 4. If a node is red, then its children must be black 5. All paths from a node to its descendants contain the same number of black nodesCopy the codeThese five features are particularly important when maintaining red-black trees
The structure diagram of red-black tree is as follows:
For red-black trees, there are three main steps: left rotation, right rotation and coloring. All “red black trees” that do not meet the above five characteristics can be adjusted to be regular red black trees through these three steps.
rotating
Red-black tree features may be broken when inserted or deleted. In order to maintain the properties of the red-black tree, it is necessary to rotate and recolor the red-black tree, where rotation includes left rotation and right rotation.
left-handed
The schematic diagram of left rotation is as follows:
The process of left-handed rotation is relatively simple. The right child S of E is adjusted as the parent node of E, and the left child of S node as the right child of E node after adjustment.
Right hand
Red-black tree inserts nodes
Since there is only an add operation to convert a linked list into a red-black tree, and space is limited, so here we only introduce the insert operation of red-black tree. For details of red-black tree, please Google.
In the analysis process, we take the following simple tree as an example. The root node G has two child nodes P and U, and the newly added node is N
Red-black trees insert red nodes by default, because black always breaks rule 5 of red-black trees (all paths from a node to its descendants contain the same number of black nodes).
Although the default node is red, insertion will cause the red-black tree to be out of balance. The imbalance caused by red-black tree insertion is mainly caused by the color conflict between the current node inserted and its parent node (red-red, contrary to rule 4: if a node is red, its children must be black).
This conflict is resolved by the above three operations: left rotation, right rotation, and recolor. Due to the red-red conflict, the grandfather node must exist and be black, but the color of the uncle node U is uncertain. It can be adjusted accordingly according to the color of the uncle node.
- Uncle U is red
If the uncle node is red, then the process becomes relatively simple: change the color of G, P and U nodes, as shown in figure 1 below.
Of course, such discoloration may lead to another problem, that is, the color conflict between parent node G and parent node GG (figure 2), so the G node needs to be treated as a new node for recursive processing.
- Uncle U node is black uncle
If the uncle node U of the current node is black, it needs to be determined according to the position of the current node N and its parent node P, which can be divided into four cases:
N is the right child of P, P is the right child of G, N is the left child of P, P is the right child of G, P is the left child of GCopy the codeCases 1 and 2 are called lateral insertions, and cases 3 and 4 are medial insertions. The distinction is made because they are handled in relative terms.
The lateral insertion
For example, N is the right child node of P and P is the right child node of G. In this case, left-rotation is performed with P as the fulcrum, and then the colors of P and G are switched (P is set to black and G to red), as follows:
The left-outside case (N is the left child of P and P is the left child of G) is treated in the same way as above, first right-handed and then recolor.
The inside of the insert
Take the case where N is the left child of P and P is the right child of G. The inner insertion situation is slightly more complicated, after a rotation, coloring is unable to adjust to the red and black tree, the processing method is as follows: first a right rotation, then a left rotation, and then recolor, you can complete the adjustment. Notice that in both cases, the new node N is the fulcrum, not P. Here the two NIL nodes of N node are named X and L. As follows:
For the inside left, the logic is as follows: first turn right, then left, and then color.
ConcurrentHashMap treeifyBin procedure
The conversion of ConcurrentHashMap’s linked list to a red-black tree is a red-black tree adding nodes. During the PUT process, if the list structure is found to have more elements than the TREEIFY_THRESHOLD (default: 8), the list is converted to a red-black tree:
if(binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); The main function of treeifyBin is to convert all nodes of the linked list into TreeNode nodes as follows:private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if(tab ! =null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if((b = tabAt(tab, index)) ! =null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for(Node<K,V> e = b; e ! =null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null.null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
Copy the codeCheck whether the array length of the current Node is smaller than MIN_TREEIFY_CAPACITY (64). If it is smaller than MIN_TREEIFY_CAPACITY (64), call tryPresize to expand the capacity to alleviate the performance problem caused by large single list elements. Otherwise, the Node list is converted to the TreeNode Node list, and then setTabAt() is called to build the red-black tree. TreeNode inherits Node as follows:
static final class TreeNode<K.V> extends Node<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,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent; }... }Copy the codeConcurrentHashMap creates a red-black tree using ConcurrentHashMap.
put 12
12 as the root node, directly to red programming black can be, corresponding source code:
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (r == null) {
x.parent = null;
x.red = false;
r = x;
}
Copy the code
(Note: For convenience, NIL nodes are omitted here, as well as later)
put 1
At this point, root node is not empty, so you need to find the appropriate insertion position when inserting the node, the source code is as follows:
K k = x.key;
inth = x.hash; Class<? > kc =null;
for (TreeNode<K,V> p = r;;) {
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);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
r = balanceInsertion(r, x);
break; }}Copy the codeAs can be seen from the above, the processing logic is as follows:
-
Compute the hash value p of the node. Dir means to move to the left or to the right. X represents the node to be inserted and P represents the node with the comparison.
-
Starting from the root node, calculate the hash value ph of the comparison node P. If ph > h, dir = -1, indicating the left shift, p = P. left. If p == null, insert, if p! If = null, the tree continues to be compared until it reaches an appropriate location. Finally, balanceInsertion() method is called to adjust the red-black tree structure. Ph < h, shift to the right.
-
If ph = h, then nodes are “in conflict” (same as HashMap). The comparableClassFor() method is first called to determine if the node’s key implements the Comparable interface, if KC! If dir == 0, tieBreakOrder() is called. If dir == 0, tieBreakOrder() is called. TieBreakOrder is as follows:
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
Copy the codeThe tieBreakOrder() method is ultimately compared by calling the System.identityHashCode() method.
At the insertion position, the nodes may break the red-black tree structure, so I call the balanceInsertion() method to adjust the red-black tree structure.
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode
root, TreeNode
x)
,v>
,v> {
x.red = true; // All nodes are inserted red by default
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// x.parent == null
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// the parent node of x is black, or the grandfather node of x is empty
else if(! xp.red || (xpp = xp.parent) ==null)
return root;
/ * * x's parent red * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * x's parent for his grandfather left child node * / node
if (xp == (xppl = xpp.left)) {
/* * The uncle node of x exists and is red. The parent node and uncle node of x become black and the grandfather node become red */
if((xppr = xpp.right) ! =null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
/* * x is the right child of its parent node, so when * is inserted inside, it is left rotated first and then right rotated */
if (x == xp.right) {
/ / left
root = rotateLeft(root, x = xp);
// After left rotation x becomes the parent of XP
xpp = (xp = x.parent) == null ? null : xp.parent;
}
/** * there are two parts here. * First part: x is originally the left child of its parent node, so it is inserted outside, and then it is rotated right */
if(xp ! =null) {
xp.red = false;
if(xpp ! =null) {
xpp.red = true; root = rotateRight(root, xpp); }}}}/** ** corresponds to */
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 codeReturn to node 1, its parent is black, that is:
else if(! xp.red || (xpp = xp.parent) ==null)
return root;
Copy the codeDirect insertion:
put 9
9 is inserted as the right child node of 1, but there is a red-red conflict. At this time, 9 has no uncle node. The parent node 1 of 9 is the left child node of 12, and 9 is the right child node of its parent node 1, so the processing logic is first left and then right, and the corresponding code is as follows:
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if(xp ! =null) {
xp.red = false;
if(xpp ! =null) {
xpp.red = true; root = rotateRight(root, xpp); }}Copy the codeThe legend changes as follows:
put 2
Node 2 is inserted as the right child node of 1, red and red conflict, cut its uncle node to be red, and change color directly:
if((xppr = xpp.right) ! =null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
Copy the codeThe corresponding legend is:
put 0
Node 0 is inserted as the left child node of 1. Since its parent node is black, the red-black tree structure will not be broken after insertion, so it can be directly inserted:
put 11
Node 11 is the left child node of 12, and its parent node 12 is black, just like 0. Insert it directly:
put 7
Node 7 is inserted as the right child node of 2, red and red conflict, and its uncle node 0 is red and can be changed:
put 19
As the right child of node 12, node 19 is directly inserted:
At this point, the process is complete, and the final result is as follows:
