Interview old Enemy HashMap: How does it improve performance after JDK 1.8

In this article, we will introduce HashMap in JDK1.8.

After reading this article, you will know:

Disadvantages of traditional HashMaps

Before JDK 1.8, the implementation of HashMap was array + linked list, even if the hash function is good, it is difficult to achieve 100 percent uniform distribution of elements.

When a large number of elements in a HashMap are stored in the same bucket and there is a long linked list under the bucket, the HashMap is equivalent to a single linked list. If the single linked list has N elements, the traversal time complexity is O(n), completely losing its advantage.

In response, JDK 1.8 introduced red-black trees (search time complexity O(logn)) to optimize this problem.

HashMap is a red-black tree data structure added in JDK 1.8

Static class Node implements map. Entry {// final int hash; static class Node implements map. Entry {// Final int hash; // key final K key; / / value V value; // A pointer to the next point Node next; / /... }Copy the code

static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
}
Copy the code

// Linkedhashmap. Entry Entry before, after; // hashmap. Node final int hash; final K key; V value; Node next;Copy the code

Three key parameters for red-black trees in the HashMap

There are three key parameters for red-black trees in the HashMap:

• TREEIFY_THRESHOLD
• UNTREEIFY_THRESHOLD
• MIN_TREEIFY_CAPACITY

Values and functions are as follows:

Static final int TREEIFY_THRESHOLD = 8; // If the number of elements in the bucket exceeds this value, use red-black tree nodes to replace the linked list nodes. // A list restore threshold for a tree // When the number of elements in the bucket is less than this value, the tree will be restored to the list structure // This value should be smaller than the above value, at least 6, Static final int UNTREEIFY_THRESHOLD = 6; // If the size of the hash table is greater than this value, the bucket in the table can be trefied. // Otherwise, the bucket will be expanded when there are too many elements in the table. The value cannot be less than 4 * TREEIFY_THRESHOLD static final int MIN_TREEIFY_CAPACITY = 64;Copy the code

HashMap new operation in JDK 1.8: treeifyBin() for buckets

Final void treeifyBin(Node[] TAB, int hash) {int n, index; Node e; / / if the hash table is empty, or the number of element in the hash table is less than the threshold of the tree (the default is 64), will go to the newly built/expansion if (TAB = = null | | (n = TAB. Length) < MIN_TREEIFY_CAPACITY) the resize ();  else if ((e = tab[index = (n - 1) & hash]) ! TreeNode hd = null, tl = null; TreeNode hd = null, tl = null; TreeNode hd = null; TreeNode p = replacementTreeNode(e, null); replacementTreeNode(e, null); If (tl == null) // determine tree head node hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) ! = null); If ((TAB [index] = hd)! // if (TAB [index] = hd)! = null) hd.treeify(tab); } } TreeNode replacementTreeNode(Node p, Node next) { return new TreeNode<>(p.hash, p.key, p.value, next); }Copy the code

final void treeify(Node[] tab) { TreeNode root = null; for (TreeNode x = this, next; x ! = null; x = next) { next = (TreeNode)x.next; x.left = x.right = null; If (root == null) {// enter the loop to determine the header, the black x.parent = null; x.red = false; root = x; } else {// if x points to a node in the tree, K = x.key; int h = x.hash; Class kc = null; For (TreeNode p = root;;) { int dir, ph; // dir K pk = p.key; If ((ph = p.hash) > h) // If (ph = p.hash) > h) // If (ph = p.hash) > h) // If (ph = p.hash) > h) Else if (ph < h) // hash = 1 dir = 1 dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, X dir = tieBreakOrder(k, pk); TreeNode xp = p; TreeNode = p; TreeNode = p; TreeNode = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }Copy the code

PutTreeVal () added to a red-black tree

This is how to turn a bucket’s linked list into a red-black tree.

When adding, if a bucket already has a red-black tree structure, the red-black tree appelement method putTreeVal() is called.

final TreeNode putTreeVal(HashMap map, Node[] tab, int h, K k, V v) { Class kc = null; boolean searched = false; TreeNode root = (parent ! = null) ? root() : this; // Each time an element is added, traverse from the root node and compare the hash for (TreeNode p = root;;) { int dir, ph; K pk; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (k ! = null &&k. quals(pk))) // Return the current node if the current node's hash value, key, and to be added are the same. return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, Pk)) == 0) {// If the hash value of the current node and the node to be added is equal, but the key of the two nodes is not the same class, we have to compare the left and right children one by one if (! searched) { TreeNode q, ch; searched = true; if (((ch = p.left) ! = null && (q = ch.find(h, k, kc)) ! = null) || ((ch = p.right) ! = null && (q = ch.find(h, k, kc)) ! = null)) // If the node to be added is found in the subtree of ch, return q; } dir = tieBreakOrder(k, pk); dir = tieBreakOrder(k, pk); TreeNode xp = p; TreeNode xp = p; TreeNode xp = p; TreeNode xp = p If ((p = (dir <= 0)? If (dir <= 0)? p.left : p.right) == null) { Node xpn = xp.next; TreeNode x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn ! = null) ((TreeNode)xpn).prev = x; // Insertion of elements into a red-black tree after necessary balance operations moveRootToFront(TAB, balanceInsertion(root, x)); return null; }} // This method is used when a and B have the same hash value but cannot be compared. Static int tieBreakOrder(Object a, Object b) {int d; 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 code

As you can see from the above code, adding a new node n to the red-black tree in HashMap does the following:

• The element P in the current red-black tree is traversed from the root node to compare the hash values of n and P.
• If the hashes are equal and the keys are equal, the element already exists (it’s not clear why the ratio is wrong);
• If the hash value is used to give a rough idea of what the comparison is going to be based on other information, such as the reference address, you can see that the comparison of the red-black tree is not very accurate, as the comment says, just to ensure a relative balance;
• Finally, after the hash comparison result is obtained, the current node P can be inserted only when there is no left or right child, otherwise, the next cycle is entered;
• After inserting elements, you also need to perform the usual red-black tree balancing and ensure that the root node takes the lead.

Find getTreeNode() in a red-black tree

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code

final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key ! = null && key.equals(k)))) return first; if ((e = first.next) ! = null) { if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }Copy the code

final TreeNode getTreeNode(int h, Object k) { return ((parent ! = null) ? root() : this).find(h, k, null); }Copy the code

Final TreeNode find(int h, Object k, Class kc) {TreeNode p = this; do { int ph, dir; K pk; TreeNode pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k ! = null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc ! = null || (kc = comparableClassFor(k)) ! = null) && (dir = compareComparables(kc, k, pk)) ! = 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) ! = null) return q; else p = pl; } while (p ! = null); return null; }Copy the code

HashMap new operation in JDK 1.8: Tree structure trim split()

In a HashMap, the resize() method is used to initialize or expand the hash table. If the bucket is a red-black tree and the number of elements is less than UNTREEIFY_THRESHOLD (default: 6), split() will be called to reduce the tree structure of the bucket or directly restore (split) to the list structure:

Final void split(HashMap map, Node[] TAB, int index, final void split(HashMap, Node[] TAB, int index, int bit) { TreeNode b = this; // Relink into lo and hi lists, preserving order TreeNode loHead = null, loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode e = b, next; e ! = null; e = next) { next = (TreeNode)e.next; e.next = null; If ((e.hash & bit) == 0) {// Place the current node in the lXXX tree if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; LoTail = e; // Record the number of nodes in lXXX tree ++lc; If ((e.rev = hiTail) == null) hiHead = e; if (e.rev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; // Record the number of nodes in hXXX tree ++hc; } } if (loHead ! = null) {// If the number of lXXX trees is less than 6, empty all branches of lXXX tree to a single node. If (lc <= UNTREEIFY_THRESHOLD) TAB [index] = lohead.untreeify (map); TAB [index] = loHead; else {// add index to lXXX tree; if (hiHead ! = null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead ! = null) {// If (hc <= UNTREEIFY_THRESHOLD) TAB [index + bit] = hihead.untreeify (map); if (hc <= UNTREEIFY_THRESHOLD) TAB [index + bit] = hiHead.  else { tab[index + bit] = hiHead; if (loHead ! = null) hiHead.treeify(tab); }}}Copy the code

It can be seen from the above code that the pruning of red-black tree nodes during HashMap expansion is mainly divided into two parts: classification first, and then according to the number of elements, whether to restore to a linked list or simplify the elements and retain the red-black tree structure.

Classification of 1.

Hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash

2. Determine the processing based on the number of elements

When the number of elements is less than 6, restore the linked list. Finally, let the TAB [index] pruned in the hash table point to the lXXX tree. If the number of elements is greater than 6, it’s still a red-black tree, but it’s trimmed;

An element that does not meet the requirement (hXXX tree) does the same, except that it ends up TAB [index + bit] outside the clipping range.

conclusion

Thanks

openjdk.java.net/jeps/180