TreeMap source code parsing (JDK1.8)

1. An overview of the

Map interface implementation classes HashMap, LinkedHashMap, TreeMap. This article describes how TreeMap is implemented. TreeMap is not as common as HashMap, but it makes sense, and it has its own application scenarios where TreeMap can implement automatic ordering of elements. The underlying implementation of TreeMap is based on the red-black tree. By virtue of the red-black tree, the sorting function of key-value pairs is implemented to ensure that elements are traversed by key value.

Principle 2.

2.1 TreeMap Inheritance Relationship

TreeMap inherits AbstractMap class and implements class Map, SortedMap, NavigableMap, Cloneable, Serializable, and other interfaces. As follows:

As shown in the figure above, TreeMap inherits and implements Map. Therefore, TreeMap must perform put and GET operations like Map and directly obtain value through key. At the same time, SortedMap is implemented to support traversal according to the size of the element ordered traversal.

SortedMap specifies that elements can be traversed by key size, and it defines methods that return a partial map.

Public interface SortedMap<K,V> extends Map<K,V> super K> comparator(); SortedMap<K,V> subMap(K fromKey, K toKey) SortedMap<K,V> subMap(K fromKey, K toKey); SortedMap<K,V> headMap(K toKey); SortedMap<K,V> tailMap(K fromKey); // return the smallest key K firstKey(); // return the largest key K lastKey(); // Return keySet <K> keySet(); // Return value Collection<V> values(); Set< map.entry <K, V>> entrySet(); }Copy the code

NavigableMap is an enhancement of SortedMap that defines methods that return the element closest to the target key.

Public interface NavigableMap<K,V> extends SortedMap<K,V> {map. Entry<K,V> lowerEntry(K key); // The maximum key K lowerKey(K key) is smaller than the given key; Map.Entry<K,V> floorEntry(K key); // Maximum key K floorKey(K key) that is less than or equal to the given key; Map.Entry<K,V> ceilingEntry(K key); K ceilingKey(K key); Map.Entry<K,V> higherEntry(K key); // The smallest key greater than the given key K higherKey(K key); Map.entry <K,V> firstEntry(); Map.entry <K,V> lastEntry(); // Pop up the smallest node map.entry <K,V> pollFirstEntry(); // Popup the largest node map.entry <K,V> pollLastEntry(); NavigableMap<K,V> descendingMap(); NavigableSet<K> navigableKeySet(); NavigableSet<K> descendingKeySet(); // Return a submap from fromKey to toKey, NavigableMap<K,V> subMap(K fromKey, Boolean fromInclusive, K toKey, Boolean toInclusive); NavigableMap<K,V> headMap(K toKey, Boolean inclusive); NavigableMap<K,V> headMap(K toKey, Boolean inclusive); NavigableMap<K,V> tailMap(K fromKey, Boolean inclusive); SubMap (fromKey, true, toKey, false) SortedMap<K,V> subMap(fromKey, K toKey); // headMap(toKey, false) SortedMap<K,V> headMap(K toKey); TailMap (fromKey, true) SortedMap<K,V> tailMap(K fromKey); }Copy the code

2.2 Data structure of TreeMap

TreeMap is implemented using the data structure of red-black trees. Here we first review the characteristics and basic operations of red-black trees.

Red black tree rule features:

  1. Nodes are red or black;
  2. The root node must be black.
  3. The leaf nodes are black and null;
  4. The two children of the red node are black (no adjacent red nodes appear in red-black trees);
  5. The path from any node to each of its leaf nodes contains the same number of black nodes;
  6. New nodes added to the red-black tree are red nodes.

Red black tree self-balancing basic operations:

  1. Discoloration: Change the color of a node in a red-black tree from red to black, or from black to red, without violating the above red-black tree rules.
  2. Left-handed: Rotate two nodes counterclockwise so that one node is replaced by its right child node, which becomes the left child node of the right child node;
  3. Dextral: Move two nodes clockwise so that one node is replaced by its left child, which becomes the right child of the left child.

TreeMap is implemented using red-black tree data structure. The tree node Entry implements map. Entry as an inner class:

Static final class Entry<K,V> implements map. Entry<K,V> {// The element key K key; // value message V value; // Entry<K,V> left; // Right child Entry<K,V> right; // Parent Entry<K,V> parent; Boolean color = BLACK; // other ellipses}Copy the code

Take a look at the data members in TreeMap that support red-black trees:

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Java.io.Serializable {// Can be used to receive external comparators that compare the size of elements when inserted. super K> comparator; Private TRANSIENT Entry<K,V> root; Private TRANSIENT int size = 0; // other ellipses}Copy the code

Because red-black tree reconstruction requires comparison of the size of elements to determine whether to insert left or right, TreeMap has a comparator that can be used by default or by custom.

ConcurrentHashMap Uses the hash value of the key to compare the size.

2.3 TreeMap construction method

TreeMap provides four constructors to implement method overloading. In the no-parameter constructor, the value of the comparator is null, and the natural sorting method is adopted. If comparison is specified, it is called custom sorting.

  • Natural ordering: All keys of a TreeMap must implement the Comparable interface. All keys are objects of the same class;
  • Custom sort: Create a TreeMap and pass in a COmparable object that sorts all the keys in the TreeMap. Custom sort does not require key to implement the COmparable interface.
Public TreeMap() {comparator = null; } public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } public TreeMap(SortedMap<K,? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }Copy the code

Added: \

The default constructor creates an empty tree. 2, The default is to use the natural order of the key to build the ordered tree, the so-called natural order, meaning that the type of the key is the compareTo method to compare the size, determine the order. For example, if the key is of type String, the compareTo method of the String class is used to compare the size. If the key is of type Interger, the compareTo method of the Interer class is used to compare the size. Java’s native primitive data types and boxing types implement the compareTo method of the Compareable interface.

2.4 put method

putThe method is the core method of Map, and the process of TreeMap method is as follows:Next, analyze the source code:

public V put(K key, V value) { Entry<K,V> t = root; // If the root node is null, the red black tree has not been created yet. // We create a new Entry and assign the value to root to create the red black tree. If (t == null) {compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } // If the node is not null, define a CMP for binary lookup comparison; int cmp; Entry<K,V> parent; Split comparator and comparable paths // CPR = split comparator <? super K> cpr = comparator; if (cpr ! = null) {/** * start at root and work down through binary search * first loop: We start with the root node, where parent is the root node, and then use a custom sorting algorithm cpr.pare (key, t.key) to compare the incoming key with the root node's key value. * If the key passed in is < root.key, then continue in the left subtree of root, starting with root's left child node (root.left); * If the key passed is > root.key, continue in the root's right subtree, starting with root's right child node (root.right); Key == root. Key == root. */ do {parent = t; parent = t; parent = t; parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t ! = null); If (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Do {parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t ! = null); } /** * the node is traversed to the end, so we just need to put a new Entry under the parent. */ Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; /** * Insertion insertion (e) */ fixAfterInsertion(e); /** * insertion insertion (e); size++; modCount++; return null; }Copy the code

Self-balancing in fixAfterInsertion(e) method

Private void fixAfterInsertion(Entry<K,V> x) {// New node is RED node. // Case 1: the new node x is the root of the tree and has no parent. No operation is required // Case 2: the parent of the new node X is black and no operation is required. = null && x ! = root &&x.parent. color == RED) { If (parentOf(x) == leftOf(parentOf(x)))) {// Get the sibling of the parent node of x, Entry<K,V> y = rightOf(parentOf(parentOf(x))); If (colorOf(y) == RED) {setColor(parentOf(x), BLACK); setColor(parentOf(x), BLACK); // set y node color to BLACK setColor(y, BLACK); Parent setColor(parentOf(parentOf(x)), RED); X = parentOf(parentOf(x)); 🈶️ if (x == rightOf(parentOf(x))) {// x == parent x = parentOf(x); // x == parent x = parentOf(x); // rotateLeft(x); SetColor (parentOf(x), BLACK); parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); RotateRight (parentOf(parentOf(x))); }} else {// y is the left child Entry of the grandfather node of x <K,V> y = leftOf(parentOf(parentOf(x))); If (colorOf(y) == RED) {setColor(parentOf(x), BLACK); // The parent's sibling is set to BLACK setColor(y, BLACK); // Set the grandparent node to RED setColor(parentOf(parentOf(x)), RED); ParentOf (parentOf(x)); } else {// x is the left child of its parent if (x == leftOf(parentOf(x))) {x = parentOf(x); // rotate the parent node as the rotation point rotateRight(x); } // Set the parent to BLACK setColor(parentOf(x), BLACK); SetColor (parentOf(parentOf(x)), RED); RotateLeft (parentOf(parentOf(x))); }} // The root node is changed to the root node, and the root node is set to BLACK root. }Copy the code

In the above code, the function of each statement is marked in detail, but it is still very unclear and difficult to understand. Next, we will describe it separately:

  • Case 1: The newly inserted node is the root node of the red-black tree and has no parent node. No operation is required and the color is directly set to black.
  • Case 2: The parent of the new node is black, and the new node is red. No operation is required because the insertion of the new node does not affect the characteristics of the red-black tree.
  • Case 3: The parent (left child) of the new node is red in color, and the sibling of the parent node is also red in color. This is where the node inserted violates the red-black tree property 4, and the red-black tree needs to be adjusted. The operation is as shown in the figure below: change the parent node and the sibling node of the parent node to black, and then change the grandfather node to red. Because the color of the grandfather node is changed, color conflict may occur on the grandfather node, so change the newly inserted node to the grandfather node, and then adjust it.

  • Case 4: The parent node (left child node) is red, the sibling node is black or null, and the newly inserted node is the right child node of the parent node. As shown in the figure below: At this point, the parent node is taken as the rotation point, and the newly inserted node is left-rotated. This is going to be case 5, which is going to point to case 5.

  • Case 5: The color of the parent node (left child node) is red, the sibling node is black or null, and the newly inserted node is the left child node of the parent node. The diagram below:

  • The operation of case 6 and 7 is the same as that of case 4 and case 5, except that the parent node is the right child node, which will not be described here.

In addition, the above source code through rotateLeft for “left”, through rotateRight for “right”. They’re all very similar, so let’s just look at the code for left-handed. The “left-handed” rule is as follows: rotate the two nodes counterclockwise so that a point is replaced by its right sub node, which becomes the left child of the right sub node.

private void rotateLeft(Entry<K,V> p) { if (p ! // Disassociate the current node P from its right child and re-point the address of the right child of node P to the left child of the right child of node P <K,V> r = p.right; p.right = r.left; // make p the parent of r. = null) r.left.parent = p; // point the parent of p to the same place as the parent of r. If (p.parent == null) root = r; if (p.parent == null) root = r; R else if (p.arent.left == p) p.arent.left = r; else p.parent.right = r; R.lift = p; p.parent = r; }}Copy the code

The comments above are not very clear, just look at the picture below

2.5 the get method

Get method is through the idea of binary search, we look at the source:

public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } /** * First loop: start at the root node, where parent is the root node, then k.compareTo(p.key) compares the passed key to the root node key: * If the key passed in is < root.key, then continue in the left subtree of root, starting with root's left child node (root.left); * If the key passed is > root.key, continue in the root's right subtree, starting with root's right child node (root.right); * If key == root.key, return the value of root. */ // Final Entry<K,V> getEntry(Object key) {if (comparator! = null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p ! = null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; } /** * First loop: start at the root node, where parent is the root node, then k.compareTo(p.key) compares the passed key to the root node key: * If the key passed in is < root.key, then continue in the left subtree of root, starting with root's left child node (root.left); * If the key passed is > root.key, continue in the root's right subtree, starting with root's right child node (root.right); * If key == root.key, return the value of root. The following loop rules are the same: when the current node is the start node, Final Entry<K,V> getEntryUsingComparator(Object key) {@suppressWarnings ("unchecked") K K = (K) key; Comparator<? super K> cpr = comparator; if (cpr ! = null) { Entry<K,V> p = root; while (p ! = null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; }Copy the code

2.6 the remove method

Remove method can be divided into two steps, first to find the node, directly call the above mentioned getEntry(Object key), this step is not to say, directly to the second step, after finding the deletion operation.

Public V remove(Object key) {// Search for the node based on the key and return the node Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; // Delete node deleteEntry(p); // Return oldValue; } private void deleteEntry(Entry<K,V> p) {modCount++; Size --; // If strictly internal, To copy the element to p and then make p. // The two children of the current node are not empty if (p.left! = null && p.right ! Succeeded (p) {// Find the right child of the current node or the smallest left Entry of the right child of the node <K,V> s = succeeded (p); // replace key-value without replacing color p.key = s.key; p.value = s.value; // point to the successor p = s; } p has 2 children // Start fixup at replacement node, if it exists. If not, go back to the right child // it is impossible to have both left and right children. The search for the smallest node whose left child is null Entry<K,V> replacement = (P. leFT! = null ? p.left : p.right); if (replacement ! = null) {// Link replacement to parent; // Link replacement to parent; // if (p.parent == null) root = replacement; P.arent. left = p.left else if (p == p.arent.left) p.arent. left = replacement; else p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. // Delete the p node to the left and right branches, and the parent node reference p.left = P.right = P.parent = Null; // Fix replacement if (p.color == BLACK) // Restore color assignment fixAfterDeletion(replacement); } else if (p.parent == null) {// return if we are the only node. } else { // No children. Use self as phantom replacement and unlink. if (p.color == BLACK) fixAfterDeletion(p); if (p.parent ! = null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; }}}Copy the code

The operation of deleting a red-black tree is slightly more complicated than the operation of inserting, and consists of two steps:

  • Removes the specified node by sorting the binary tree. There are three scenarios for deleting nodes:
    • Deleted node, there is no left and right child node, can be directly deleted;
    • The deleted node has a child node, so its child node points to its parent node.
    • If the node to be deleted has two non-empty child nodes, it is necessary to find the precursor or successor node of the node, replace the element value, and then delete the precursor or successor node (the precursor or successor of any node must have one non-empty child node, which can be cleaned according to the previous two operations).
  • Carry on the color exchange and the tree rotation operation, meet the characteristics of red black tree.

Here are some possible scenarios to discuss:

  • Case 1: The node to be deleted is the root node or its color is red. Deleting the node does not affect the characteristics of the red-black tree and no operation is required.
  • Case 2: The deleted node is black and the sibling node is red, as shown below:

If the x node in the figure above is deleted, a black node will be missing, which conflicts with the nature of red-black tree. Therefore, change the color of SIB to black, set the p node to red, and perform left-rotation operation. Perform subsequent operations.

  • Case 3: The deleted node is black, and the child nodes of the sibling node of x node are black, as shown below:

The x node is black, the child nodes of the sibling node (black) are also black, and the color of the P node is not defective, which may be red or black. If it is red, directly set it to black. If it is black, locate the P node where X is located before processing.

  • Case 4: The deleted node is black, and the right child node of the sibling node of X is black, as shown below: Case 4 is adjusted to convert to case 5 for processing.

  • Case 5: The deleted node is black, and the right child node of the sibling node of X is red, as shown below:

The color of the left child node of SIB is uncertain. It may be red or black, but it does not matter because the number of black nodes in the upper branch of siB does not change before and after the transformation.

The above situation is only analyzed for the case where the deleted node is the left child. The deleted node may also be the right branch. The situation is exactly the same except that the left and right order is reversed.

The deletion operation is actually very simple, and there are few cases. Let’s take a look at the self-balancing operation method fixAfterDeletion

/** From CLR */ private void fixAfterDeletion(Entry<K,V> x) {// Not the root node, the color is black, adjust the structure while (x! = root && colorOf(x) == BLACK) {/** * The current node X is the left node or the right node, both of which are four scenarios. Here we analyze the situation where X is the left node through the code. The right node can be understood by referring to the left node. If (x == leftOf(parentOf(x))) {Entry<K,V> sib = rightOf(parentOf(x)); /** * Scenario 1: When x is the left black node, sib is the red node * the brother node turns from red to black, and the parent node turns from right to black, the structure of the tree changes according to the parent node's left-rotation * left-rotation, then sib is reassigned, */ if (colorOf(sib) == RED) {// Set sibling to BLACK setColor(sib, BLACK); // Set the parent to RED setColor(parentOf(x), RED); // rotateLeft(parentOf(x)); Sib = rightOf(parentOf(x)); } /** * Scenario 2: If node X and sib, the sibling node of X, and the left and right child nodes of SIB are all black, the siB node needs to be changed from black to * red. */ if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { SetColor (sib, RED); ParentOf (x) = parentOf(x); } else {/** * Scenario 3: Sib and the right child node of node X and its sibling node SIB and SIB are all black. When the left child node of SIB is red, * needs to set the left child node of SIB to black and the right child node of SIB to red, and press SIB to right-rotate at the same time. If (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK); // Sibling is RED setColor(sib, RED); // rotateRight(sib); Sib = rightOf(parentOf(x)); } /** * Scenario 4: Node x, x brothers sib is black, and about the sib child nodes are in red or right child node is red, *, left child node is black, now need to set the color of the sib node into the same color and x's parent p, * set x parent node to black, set the sib right child nodes to black, left-handed parent x p, SetColor (sib, colorOf(parentOf(x))); // Set the parent node to BLACK setColor(parentOf(x), BLACK); // Set the right child of the sibling node to BLACK setColor(rightOf(sib), BLACK); / / sinistral rotateLeft (parentOf (x)); // Set x to root. }} else {// Symmetric // x is the right node of the parent node. For details, see Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }Copy the code

Left nodes for the current operation node, the above describes four kinds of scenes, and scenes may turn black, such as after deleteEntry entered the scenario 1, after a series of operating scenario 1, red and black tree structure adjustment have not completed, but entered the scenario 2, after the completion of the scenario 2 points to jump out of the loop, will stay operation node set to black, complete.

Scenario 1: When X is a left black node and sib is a red node, the sibling node needs to turn from red to black, and the parent node needs to turn from black to red. The structure of the left-spin tree changes as the parent node. At this time, sib points to the sibling node of X.

But after this sequence of actions, it’s not over, it might be scenario 2, or scenario 3 and 4.

Scenario 2: If sib, the sibling node of X, and the left child node and right child node of SIB are all black, change siB from black to red, and point X to the parent node of x.

After a series of actions in Scene 2, the loop ends, we jump out of the loop, set node X to black, and complete the self-balancing adjustment.

Scenario 3: If node X, siB, and the right child of NODE X are black, and the left child of node SIB is red, set the left child of node SIB to black and the right child of node SIB to red, rotate siB to the right, and point siB to the brother node of node X

After a sequence of actions in scenario 3, which are not completed, scenario 4 is entered.

Scenario 4: Node x, x brothers sib is black, and the sib about child node is red, left or right child node to child nodes to black, the color will need to sib node set to x number of the parent node p, of the same color set x of the parent node is black color, set the sib color is black, with children right x’s father node p, Then assign x to root.

3. Summary

  • As for the node insertion operation of red-black tree, the first operation is to change the new node, the parent node, the grandfather node, and the color of the new node, which can be changed by the rotation of the node in the current branch, so as to meet the characteristics of red-black tree.
  • If the current rotation of the relevant node does not resolve the conflict in the red-black tree, it is resolved by moving the red node to the root node, and finally setting the root node to black.

Some pictures from the network, copyright to the original author, delete.Copy the code