Recommend a goo bubble institute of video resources: link: pan.baidu.com/s/1SmSzrmfg… Password: e54x
In JDK8, HashMap can be used to solve the problem of infinite loops.
The linked list part corresponds to the code of transfer above:
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
Copy the codeSince expansion is performed twice, that is, N expands to N + N, there will be a low part 0 – (n-1) and a high part N- (2n-1), so there are loHead (low Head) and hiHead (high Head) here.
Through the above analysis, it is not difficult to find that the cycle is generated because the order of the new linked list is completely opposite to the order of the old linked list, so as long as the new chain is established in accordance with the original order, there will be no cycle.
JDK8 uses head and tail to keep the list in the same order as before, so there are no circular references.
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.
New data structure – red black tree
In JDK 1.8, there are only linked list nodes in HashMap:
static class Node implements Map.Entry {
// The hash value is the position
final int hash;
/ / key
final K key;
/ / value
V value;
// A pointer to the next point
Node next;
/ /...
}
Copy the codeThere is another type of node: TreeNode, which was added in 1.8 and belongs to a red-black tree in the data structure.
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 codeYou can see that it’s a red-black tree node with the parent, the left and right children, the node of the previous element, and a color value.
In addition, since it inherits from LinkedhashMap. Entry, and linkedhashmap. Entry inherits from HashMap.Node, there are six additional attributes:
// Inherits linkedhashmap.entry
Entry before, after;
/ / a HashMap. Node
final int hash;
final K key;
V value;
Node next;
Copy the codeThree key parameters of a red-black tree
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:
// The tree threshold of a bucket
// When the number of elements in the bucket exceeds this value, the list node needs to be replaced with a red-black tree node
// This value must be 8, otherwise frequent conversion is not efficient
static final int TREEIFY_THRESHOLD = 8;
// A tree list restore threshold
// When the number of elements in the bucket is less than this value, the tree bucket elements will be restored to the linked list structure
// This value should be smaller than the one above, at least 6, to avoid frequent conversion
static final int UNTREEIFY_THRESHOLD = 6;
// The minimum tree capacity of the hash table
// The bucket in the hash table can only be trefied if the capacity in the hash table is greater than this value
// If there are too many elements in the bucket, it will expand instead of tree
// To avoid conflicts between capacity expansion and tree selection, the value cannot be less than 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
Copy the codeNew action: treeifyBin()
In Java 8, if the number of elements in a bucket exceeds TREEIFY_THRESHOLD(the default is 8), red-black trees are used instead of linked lists to speed things up.
This replacement method is called treeifyBin(), or treification.
// Replace all list nodes in the bucket with red-black tree nodes
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
// If the current hash table is empty, or the number of elements in the hash table is less than the threshold for tree (64 by default), create/expand the hash table
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
// If the number of elements in the hash table exceeds the tree threshold, tree
// e is the list node in the bucket at the specified position in the hash table, starting from the first one
TreeNode hd = null, tl = null; // The first and last nodes of a red-black tree
do {
// Create a new tree node with the same contents as the current list node e
TreeNode p = replacementTreeNode(e, null);
if (tl == null) // Determine the tree head node
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while((e = e.next) ! =null);
// Make the first element of the bucket point to the head of the new red-black tree
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 codeThe above operations do these things:
- Determine whether to expand or tree based on the number of elements in the hash table
- If you tree it
- Iterate over the elements in the bucket, create the same number of tree nodes, copy the contents, and make connections
- The first element of the bucket points to the new tree header, replacing the bucket’s list contents with the tree contents
However, we found that the previous operation did not set the color value of the red-black tree, and now the result is a binary tree. At the end, call the tree node hd.treeify(TAB) method to shape the red-black tree. Look at 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) { // head back into the loop, make sure the head is black
x.parent = null;
x.red = false;
root = x;
}
else { // Go through the loop, x points to a node in the tree
K k = x.key;
int h = x.hash;
Class kc = null;
// Another loop, starting from the root node, traverses all nodes and compares them to the current node x, sort of like bubble sort
for (TreeNode p = root;;) {
int dir, ph; / / the dir
K pk = p.key;
if ((ph = p.hash) > h) // Dir is -1 when the hash value of the comparison node is greater than x
dir = -1;
else if (ph < h) // hash ratio x hour dir is 1
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// If you compare the hash value of the node, x
dir = tieBreakOrder(k, pk);
// Change the current node to the parent of x
If the hash value of the current comparison node is greater than x, x is the left child, otherwise x is the right child
TreeNode xp = 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 codeAs you can see, when you turn a binary tree into a red-black tree, you need order. Here is a double loop, comparing the hash values of all nodes in the tree with the current node (if the hash values are equal, compare the keys, not completely ordered here), and then determine the position in the tree based on the comparison results.
New operation: Added element putTreeVal() to 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, comparing the hashes
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.equals(pk)))
// If the current node has the same hash value, key value, and the value to be added, the current node is returned.
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
// If the hash value of the current node is equal to that of the node to be added, but the keys of the two nodes are 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 can be found in the subtree of ch, return it directly
return q;
}
// Hash values are equal, but keys cannot be compared, so a special method is used to give the result
dir = tieBreakOrder(k, pk);
}
// We get a size relation between the current node and the node to be inserted
// If the node to be inserted is smaller than the current node, it is inserted into the left subtree; if the node to be inserted is larger, it is inserted into the right subtree
TreeNode xp = p;
// If the current node has no left or right child, it can be inserted, otherwise it goes to the next cycle
if ((p = (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;
// In a red-black tree, necessary balancing operations after inserting elements
moveRootToFront(tab, balanceInsertion(root, x));
return null; }}}// This method is used when the hash values of a and B are the same but cannot be compared
// There is no need for complete order in the tree, as long as the insertion is balanced using the same rules
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 codeAs 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.
New action: Find element getTreeNode() in red-black tree
Find a HashMap by getting ():
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the codeIt calls the internal method getNode() after calculating the hash value of the specified key;
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 codeThe getNode() method evaluates the number of hash elements and the hash value (using the formula (n-1) &hash) to get the head node of the bucket where the key is located. If the head node happens to be a red-black tree node, the getTreeNode() method is called. Otherwise, the list nodes are iterated.
final TreeNode getTreeNode(int h, Object k) {
return((parent ! =null)? root() :this).find(h, k, null);
}
Copy the codeThe getTreeNode method makes the lookup happen by calling the find() method on the tree node:
// Search by hash and key from the root node
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 codeSince the previous addition has guaranteed that the tree is in order, so the search is basically a half-fold search, very efficient.
If the hash value of the node is equal to the value of the hash, the key is equal. If they’re not equal, they recurse from the subtree.
New action: 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:
// Parameter description
// TAB represents the hash table that holds the bucket header
//index indicates where to start trimming
//bit The number of bits to trim (hash)
final void split(HashMap map, 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 the last bit of the current node's hash value is equal to the bit value to trim
if ((e.hash & bit) == 0) {
// Put the current node in the lXXX tree
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
// Then loTail records e
loTail = e;
// Record the number of nodes in the lXXX tree
++lc;
}
else { // If the last bit of the current node hash is not to be trimmed
// Put the current node into the hXXX tree
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
// Record the number of nodes in the hXXX tree++hc; }}if(loHead ! =null) {
// If the number of lXXX trees is less than 6, empty the branches and leaves of the lXXX tree to make a single node
// Then make all nodes in the bucket become lXXX nodes restored to the linked list
// This is a list structure
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
// Otherwise make the node of the index point to the lXXX tree, which has been pruned and has fewer elements
tab[index] = loHead;
if(hiHead ! =null) // (else is already treeified)loHead.treeify(tab); }}if(hiHead ! =null) {
// Similarly, let the element after index + bit be specified
// Point to hXXX restore to linked list or pruned tree
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if(loHead ! =null) hiHead.treeify(tab); }}}Copy the codeIt 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
After JDK 1.8, add, delete, find, and expand hash tables to add TreeNode:
- When the bucket is added, the bucket will be converted to a red-black tree when the number of linked lists exceeds 8.
- When deleting or expanding the bucket, if the bucket structure is red-black tree and the number of elements in the tree is too small, it will be pruned or directly restored to the linked list structure.
- Even if the hash function is not good and a large number of elements are concentrated in a bucket, the performance will not be poor due to the red-black tree structure.
(Photo: tech.meituan.com/java-hashma…)
The TreeNode in JDK 1.8 is a HashMap that combines the advantages of a hash table and a red-black tree. It is not only fast, but also can guarantee performance in extreme cases. Write here can not help but look up to heaven long sigh: when I can write so NB code!!
Refer to the address
- Cloud.tencent.com/developer/a…
- Juejin. Cn/post / 684490…
If you like my article, you can follow the individual subscription number. Welcome to leave messages and communicate at any time.
