Set @hashMap (version 1.8)

1. HashMap1.7 insufficiency

1.7 With the structure of array + linked list, it is difficult to achieve 100% uniform distribution of elements even if the hash function is achieved well

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 isO(n)And completely lost its advantage

2. HashMap1.8 optimization

HashMap1.8Version based onCollection @hashMap (version 1.7)Optimize. We’re only talking about improvements here
The biggest difference is that 1.7 uses array + linked list structure for improving performance, while 1.8 uses more efficient array + linked list + red-black tree (search time complexity isO(logn)The structure of the)
In my opinion, due to changes in the underlying data structure, in factHashMap1.8It’s almost overwritten, so you can think of it as a new class
Version 1.8 of the red-black tree implementation withTreeMapBasically the same (same situation, just a few code differences)TreeMap (version 1.7)

3. Data structure of HashMap

Important new variable

    
     / * *
       * The bin count threshold for using a tree rather than list for a bin. 
       * Bins are converted to trees when adding an element to a bin with at least this many nodes.
       * The value must be greater than 2 and should be at least 8 to mesh with assumptions in tree 
       * removal about conversion back to plain bins upon shrinkage.
     * Tree threshold for a bucket:
     * 1. When the number of elements in the bucket exceeds this value, the linked list is converted to a red-black tree
     * 2. The value must be greater than 2 and at least 8 to avoid inefficient conversion
     * 3. The default value is 8, that is, when the new element causes the list length to be 8, it is automatically converted to a red-black tree
     * /
     static final int TREEIFY_THRESHOLD = 8;
     / * *
       * The bin count threshold for untreeifying a (split) bin during a
       * resize operation. Should be less than TREEIFY_THRESHOLD, and at
       * most 6 to mesh with shrinkage detection under removal.
     * A tree linked list restore threshold:
     * 1. If the number of elements in the bucket is less than this value, the bucket elements in the tree will be reduced to a linked list
     * 2. The value should be smaller than TREEIFY_THRESHOLD and at least 6 to avoid inefficient conversion
     * /
     static final int UNTREEIFY_THRESHOLD = 6;
     / * *
       * The smallest table capacity for which bins may be treeified.
       * (Otherwise the table is resized if too many nodes in a bin.)
       * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
       * between resizing and treeification thresholds.
     * The minimum tree capacity of the hash table:
     * 1. Only when the capacity of the hash table is larger than this value, the bucket in the table can be trefied. Otherwise, the bucket will be expanded when there are too many elements
     * 2. 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;

The constructor

    
     / * *
     * version 1.7
     * /
     public HashMap(int initialCapacity, float loadFactor) {
         if (initialCapacity < 0)
             throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
         if (loadFactor <= 0 || Float.isNaN(loadFactor))
             throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
         this.loadFactor = loadFactor;
     // Here are the differences with 1.8
     // Find a power of 2 >= initialCapacity tableSizeFor()
         int capacity = 1;
         while (capacity < initialCapacity)
             capacity <<= 1;
         threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
         table = new Entry[capacity];
         useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
         init();
     }
     / * *
     * Version 1.8 differs from 1.7
     * 1. The constructor stage does not initialize the array (instead resize the array on the first PUT)
     * 2. Initial capacity was placed in threshold
     * /
     public HashMap(int initialCapacity, float loadFactor) {
         if (initialCapacity < 0)
             throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
         if (loadFactor <= 0 || Float.isNaN(loadFactor))
             throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
             this.loadFactor = loadFactor;
     // The constructor stage threshold is equal to the capacity, guaranteed to be power 2 (resize)
             this.threshold = tableSizeFor(initialCapacity);
     }

Node

    
     / * *
       * Basic hash bin node, used for most entries.  (See below for
       * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     * 1.8 Change Entry to Node (internal structure unchanged)
     * Even though it's just a name change, the name change reflects the importance HashMap attaches to the concept of 'nodes'
     * /
     static class Node<K,V> implements Map.Entry<K,V> {
     final int hash; // Add the final property to indicate that the hash value is immutable
             final K key;
             V value;
     Node<K,V> next; // one-way linked list
     
             Node(int hash, K key, V value, Node<K,V> next) {
                 this.hash = hash;
                 this.key = key;
                 this.value = value;
                 this.next = next;
             }
     .
     }

TreeNode

    
     / * *
       * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn extends Node) 
       * so can be used as extension of either regular or linked node.
     * Compared with TreeMap,
     * 1. Add pre to record the previous node
     * 2. Inherit from linkedhashmap. Entry<K,V>, which in turn inherit from Hashmap. Node:
     * 1. Has all the functionality of Node and linked List Node
     * 2. Entry<K,V> before, after; final int hash; final K key; V value; Node<K,V> next;
     * /
     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
     TreeNode<K,V> parent; / / the parent node
     TreeNode<K,V> left; // Left child node
     TreeNode<K,V> right; // Right child node
     TreeNode<K,V> prev; // The node of the previous element
     boolean red; // Is a red node
         TreeNode(int hash, K key, V val, Node<K,V> next) {
             super(hash, key, val, next);
         }
     .
     }
     / * *
     * Implementation of LinkedhashMap.Entry
       * HashMap.Node subclass for normal LinkedHashMap entries.
     * As you can see, TreeNode still inherits all the functionality of HashMap.Node, and the underlying implementation is Node
     * /
     static class Entry<K,V> extends HashMap.Node<K,V> {
         Entry<K,V> before, after;
         Entry(int hash, K key, V value, Node<K,V> next) {
             super(hash, key, value, next);
         }
     }

3. New method analysis of HashMap1.8

3.1 tableSizeFor Method Parsing

    
     / * *
       * Returns a power of two size for the given target capacity.
     * The capacity method is found to be greater than or equal to the 2nd power of the specified capacity parameter
     * /
     static final int tableSizeFor(int cap) {
     int n = cap - 1; // Cap -1 is the same as cap-1.
     // When a number is between two neighboring powers of 2, the place where the first 1 appears from the highest number is the same as the place where the nearest power of 2 is less than the highest 1
     //[example 1]
     // >>> indicates an unsigned move of N bits to the right; | representation and operation: with any number from 1 for operation, the result is 1
     [example] : This algorithm is most important to find the nearest n and greater than the second power of n -1 value (binary is 1 value)
         n |= n >>> 1;
         n |= n >>> 2;
         n |= n >>> 4;
         n |= n >>> 8;
         n |= n >>> 16;
     // N +1 must be cap to the 2nd power
     // If you move 32 bits to the right of the first 1, you have already exceeded the maximum value of int
     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // A second power, but at least 1
     }

Case Study 1

Argument: When a number is between two neighboring powers of 2, the position from which the first 1 of the number appears is the same as that of the nearest power of 2, which is less than 1

Assuming that the number we are looking for is nearest 9 and greater than the second power, we know that the value should be 2^4=16

And if we find the nearest power that’s less than the second power, we know that this value is 2^3=8

Base 2 of 8:0000 1000

Base 2 of 9:0000 1001

16 hexadecimal 2:0001 0000 readers whether according to these findings, 9 appear for the first time since high position 1 and 8 is consistent, so can get the conclusion: a number between adjacent two 2 times the power, the number from high in the position of the first 1 and the nearest and twice less than its power high. 1 position is consistent

Case Study 2

Argument: Find the nearest value to n greater than the second power of n -1

Suppose we want to find the nearest power of 17 to the second power greater than 17, which should be 2^6=32, and the algorithm follows

【Notice the padding of 1】

32 = 2^6 = 0010 0000 = 0001 1111 + 0000 0001 = 31 + 1

As can be seen from the figure and the formula above, this algorithm can effectively find the value of the nearest and greater than the second power of n -1 (that is, binary values are all 1 values), or the value of n starts from the highest digit and is followed by all 1 values, after which +1 can get the nearest and greater than the second power of n

Because the first move to the right is 1 and the two highest positions after the operation are 1, so the operation is 2 to the right, the next time is the four highest positions are 1.That is, the change in x is based on the number of 1s in the higher x after the bit operationAnd ultimately, useAnd any number that operates with 1, you get 1The property of theta changes everything to 1

Case Study 3

Argument: Cap-1 is going to be in the case of all 1s, so it’s not going to double

2^0=1=0000 0001, and the value of 1, 2, 4, 8, 16 bits to the right with itself, still 1, no effect

If a number is exactly a power of 2, if it is directly moved to the right without subtracting 1, the value obtained in the end will be doubled. For example, 4 (0100) will be directly taken, and the following bits will be filled with 1 to get 7 (0111). 7+1=8, that is, it will be doubled, which obviously does not meet our expected requirements

3.2 putVal method parsing

    
     public V put(K key, V value) {
         return putVal(hash(key), key, value, false, true);
     }
     / * *
       * Implements Map.put and related methods
     * New key-value pairs
       * @param hash hash for key
       * @param key the key
       * @param value the value to put
       * @param onlyIfAbsent if true, don't change existing value 
       * @param evict if false, the table is in creation mode.
       * @return previous value, or null if none
     * /
     // Note that overloading cannot be inherited if using 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;
     // When the array is empty
         if ((tab = table) == null || (n = tab.length) == 0) {
     n = (tab = resize()).length; // When initializing or the current array length is 0, resize and return the new length
         }
     // Calculate the subscript and get the element by h & (length-1)
         if ((p = tab[i = (n - 1) & hash]) == null){
     // If the current subscript position is empty (that is, the key does not exist), create a non-tree node
             tab[i] = newNode(hash, key, value, null);
         }else {
     // When the key exists or a hash conflict occurs
             Node<K,V> e; K k;
     // If the value can be found directly in the array by comparing hash and equals, the old value is overwritten
     // the bucket is neither a linked list nor a red-black tree
     if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))){
     e = p; / / cover
             }
     // Otherwise, check whether the node is a red-black tree node
     Else if (p instanceof TreeNode){// If the tree type is red-black, execute putTreeVal
                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
             }
             else {
     // There is a conflict
                 for (int binCount = 0; ; ++binCount) {
     // If the bucket is not already in the list and needs to be converted to the list, or if it is not already in the list, add a new node
                     if ((e = p.next) == null) {
     // Note that 1.7 is different from 1.8 when the list is inserted
     //1.7: it is head insertion, the last one stays on the array, the first one stays on the last (traversal is first in last out)
     //1.8: is the tail insertion method, the first to stay on the array, the last chain on the tail (traversal is first in, first out)
                         p.next = newNode(hash, key, value, null); 
     // If the bucket's list length >= the bucket's tree threshold, the list needs to be converted to a red-black tree
     // Add elements first and then judge the tree condition, not first and then add elements
                         if (binCount >= TREEIFY_THRESHOLD - 1)
     treeifyBin(tab, hash); // The current bucket tree
                         break;
                     }
     // If the value already exists in the list, the old value is overwritten
     if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k))))
                         break;
                     p = e;
                 }
             }
     // Rule: overwrite old values with new values
     if (e ! = null) { // existing mapping for key
                 V oldValue = e.value;
     //onlyIfAbsent Cannot be overwritten if it is true
     if (! onlyIfAbsent || oldValue == null)
                     e.value = value;
     afterNodeAccess(e); // Equivalent to 1.7 afterNodeAccess, dedicated to LinkedHashMap for ordered control
                 return oldValue;
             }
         }
         ++modCount;
     If (++size > threshold)// If the threshold is exceeded, expand the capacity
                 resize();
     afterNodeInsertion(evict); // remove the oldest element;
         return null;
     }
     // Create a regular (non-tree) node Creates a regular non-tree node
     Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
         return new Node<>(hash, key, value, next);
     }

3.3 Resize method analysis

    
     / * *
       * Initializes or doubles table size.  If null, allocates in accord with initial capacity
       * target held in field threshold. Otherwise, because we are using power-of-two expansion,
       * the elements from each bin must either stay at same index, or move with a power of two
       * offset in the new table.
     * Initialize the Map or double capacity expansion, and evenly distribute the previously conflicting nodes into the new bucket
     * When Map is empty, the same amount of capacity as the threshold is allocated
     * When the Map is not empty, there are two cases of element positions due to a 2-power expansion
     * 1. Either the element is in the same position
     * 2. Either the element's position changes: it moves to the right by a power of 2
     * Note: Since capacity in 1.8 is based on threshold values, it is important to be aware that readers will see a lot of threshold judgments and processing in 1.8
       * @return the table
     * /
     final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table; // Since the new array overwrites the old one, a temporary backup is needed to reassign to the new array
         int oldCap = (oldTab == null) ? 0 : oldTab.length;
         int oldThr = threshold;
         int newCap, newThr = 0;
     If (oldCap > 0) {// If Map is not empty
     // Critical processing: maximum
             if (oldCap >= MAXIMUM_CAPACITY) {
     threshold = Integer.MAX_VALUE; // The maximum value is actually the maximum value of Integer
                 return oldTab;
             }
     // If the original capacity is less than MAXIMUM_CAPACITY and the default capacity is 16, double the capacity
             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
     newThr = oldThr << 1; // Double threshold = double threshold
     } else if (oldThr >0){// If Map is empty, check whether the threshold is >0
     newCap = oldThr; // The threshold is the new capacity.
     // Initial capacity was placed in threshold
         } else {
     // When Map is empty and the threshold is not greater than 0 (i.e., invalid threshold), the default value is used
             // zero initial threshold signifies using defaults
     newCap = DEFAULT_INITIAL_CAPACITY; //1 << 4 = 16
     newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //0.75 * 16 = 12
         }
     // If the new threshold is not reset, you need to recalculate the new threshold based on the new capacity and load factor
     // Note: the threshold will be reset during initialization. = capacity, which was reset when (oldThr > 0)
         if (newThr == 0) {
     // Equivalent to version 1.7: threshold = (int) math. min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
             float ft = (float)newCap * loadFactor;
             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                           (int)ft : Integer.MAX_VALUE);
         }
     threshold = newThr; // Reset to the real threshold
         @SuppressWarnings({"rawtypes","unchecked"})
     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // Create a Node array with a new capacity
     table = newTab; // Overwrite the array (the first line is already backed up)
     // If the original array is not empty, the new array needs to be repopulated
     if (oldTab ! = null) {
     / / traverse
             for (int j = 0; j < oldCap; ++j) {
     Node<K,V> e; // To back up the current node
     // If the array subscript position is not empty
     if ((e = oldTab[j]) ! = null) {
     oldTab[j] = null; // Clear the current location of the original array, since the Help GC has been backed up
     If (e.ext == null)// The bucket is neither a linked list nor a red-black tree
     newTab[e.hash & (newCap - 1)] = e; // The position may remain the same or move 2 powers, relative to newcap-1
     Else if (e instanceof TreeNode)// if the bucket is a TreeNode, you need to split the tree
                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
     Else {// Preserve order is a linked list, the order 1.7 will be inverted
     // The order of the list in the new array is the same as the order of the list in the old array!!
     Node<K,V> loHead = null, loTail = null; //lo=low, which means low (the first part of the list)
     Node<K,V> hiHead = null, hiTail = null; //hi=high, indicating high (the list at the bottom of the array)
                         Node<K,V> next;
     // Iterate over the current bucket list
     //1.8: is the tail insertion method, the first to stay on the array, the last chain on the tail (traversal is first in, first out)
                         do {
                             next = e.next;
     // Split the original list into 2 linked lists according to whether e.hash & oldCap is zero
     // Check whether the current position has changed
                             if ((e.hash & oldCap) == 0) {
     // The original index is processed in the first half of the array
     // If the end of the queue is empty, the current element is the first element of the queue (i.e. the first element inserted)
                                 if (loTail == null) 
                                     loHead = e;
                                 else
     // If the end of the queue is not empty, the current element is linked to the end of the original queue, ensuring first-in, first-out
                                     loTail.next = e;
     loTail = e; // To ensure the same insertion order, the current element must be set to the end of the queue
                             }
     // Old index +oldCap otherwise move to new linked list with "old index +oldCap"
                             else {
     // Process in the bottom half of the array
                                 if (hiTail == null)
                                     hiHead = e;
                                 else
                                     hiTail.next = e;
     hiTail = e; // To ensure the same insertion order, the current element must be set to the end of the queue
                             }
     } while ((e = next) ! = null);
     // Put the index in the bucket
     if (loTail ! = null) {// If the last element of the queue is not empty
     loTail.next = null; //loTail is the last element of the queue
     newTab[j] = loHead; // The header of the queue is placed in the array
                         }
     // Add old index +oldCap to new bucket
     if (hiTail ! = null) {// If the last element of the queue is not empty
     hiTail.next = null; //hiTail is the last element of the queue
     newTab[j + oldCap] = hiHead; // The header of the queue is placed in the array
                         }
                     }
                 }
             }
         }
         return newTab;
     }

Why does 1.8 not need to recalculate index subscripts during resize?

Note: there is no need to calculate the index subscript, the Hash value of the node does not change!!

Definition of ampersand: the result is “1” only if both digits are “1”, otherwise it is 0

First, we get the index changes before and after expansion according to the subscript calculation formula

According to the figure, the index subscript of 21 after expansion is one more than that before expansion, and the 1 is in the highest bit of the mask of NewCap-1

Conclusion: After the element is recalculated, because n is doubled, the mask range of N-1 is 1bit more at the high level, that is, the distance of the original capacity is increased

Optimization: No need to recalculate Hash, saving time. New index = original index + original capacity

So the question is,e.hash & oldCapWhere does it come from??

Function: Check whether the hash(key) bit corresponding to the highest bit of newCap-1 is 0 or 1

Before and after expansionHash unchangedBy theCapacity to the second powerandindex=(n-1)&hashUnknown:

The determinant of the new index is whether the hash bit corresponding to the highest binary bit (newcap-1) is 0 or 1;

So the source code authors cleverly pull relationships to“OldCap is equivalent to newTab’s highest bit of (n-1).”Thus it is concluded thate.hash & oldCap!

Optimization: Since the calculated hash(key) bit is 1 or 0, it can be considered as random, so a long conflicting list is “evenly divided” into two lists to reduce collisions

3.4 Parsing the treeifyBin method

    
     / * *
       * Replaces all linked nodes in bin at index for given hash unless
       * table is too small, in which case resizes instead.
     * In-bucket tree: Replace all list nodes in the bucket with red-black tree nodes, and resize when there are not enough elements to tree
     * Note: Not the whole Map transformation, just the current bucket!
     * /
     final void treeifyBin(Node<K,V>[] tab, int hash) {
         int n, index; Node<K,V> e;
     // When the array is empty or the length of the array is less than the tree threshold (64), the resize method is used to determine the internal data structure type
         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
             resize();
     // Otherwise, you need to tree
     else if ((e = tab[index = (n - 1) & hash]) ! = null) {
     TreeNode<K,V> hd = null, tl = null; //hd refers to head and tl refers to tail
     // Walk through the list from the head node, which is stored in the array
             do {
     // Create a new tree node with the same contents as the current list node e
     // Next defaults to null, and next is reassigned sequentially
                 TreeNode<K,V> p = replacementTreeNode(e, null);
     If (tl == null)// If (tl == null)// If (tl == null)
                     hd = p;
                 else {
     p.prev = tl; // Prev is assigned to the last node of the current node
     tl.next = p; //p points to next at the end of the previous node, preserving the insertion order
                 }
     tl = p; // The current node is set to the last node, keeping the insertion sequence
     } while ((e = e.next) ! = null);
     // The first element in the bucket is the list head node and is placed in the array
     if ((tab[index] = hd) ! = null)
     hd.treeify(tab); // Start traversing from the beginning node to tree the entire bucket
     // Note that the head node is not necessarily the root node of the tree: the trefied root node is reset to the head node, i.e. TAB [index]=root
     // See moveRootToFront() for details
         }
     }
     // For treeifyBin Creates a new tree node
     TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
         return new TreeNode<>(p.hash, p.key, p.value, next);
     }
     / * *
       * Forms tree of the nodes linked from this node. 
     * Shape red black tree
     * @return root of tree * @return root of tree
     * /
     final void treeify(Node<K,V>[] tab) {
     TreeNode<K,V> root = null; // The root node needs to be reset after sorting (the head node of the previous list is not necessarily the root node of the tree)
     // This refers to the head node of the current binary tree, traversed from the beginning node
     for (TreeNode<K,V> x = this, next; x ! = null; x = next) {
             next = (TreeNode<K,V>)x.next;
             x.left = x.right = null;
     // When the root node is empty, set the root node to black first and the current node to be the root node first.
             if (root == null) {
                 x.parent = null;
     x.red = false; // The root node of a red-black tree is black
                 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;
     // Re-loop, starting from the root node, through all nodes compared to the current node X, re-adjust the position, similar to bubble sort
                 for (TreeNode<K,V> p = root;;) {
                     int dir, ph;
                     K pk = p.key;
     If ((ph = p.hash) > h)// If the hash of the comparison node is larger than that of the current node, look up the left subtree
                         dir = -1;
                     else if (ph < h)
     dir = 1; // If the hash of the comparison node is smaller than that of the current node, look up the right subtree
                     else if ((kc == null && (kc = comparableClassFor(k)) == null) || 
                                     (dir = compareComparables(kc, k, pk)) == 0 )
     //tieBreakOrder is used to compare by reference when hashes are the same and keys cannot be compared
     If the hash value of the current comparison node is greater than x, return -1, otherwise return 1
                         dir = tieBreakOrder(k, pk);
     // We get a size relation between the current node and the node x to be inserted
     X is the left child if the hash value of the current comparison node is greater than x, otherwise x is the right child
                     TreeNode<K,V> xp = p;
                     if ((p = (dir <= 0) ? p.left : p.right) == null) {
     x.parent = xp; // Change the current node to the parent node of x
                         if (dir <= 0)
                             xp.left = x;
                         else
                             xp.right = x;
                         root = balanceInsertion(root, x);
                         break;
                     }
                 }
             }
         }
     moveRootToFront(tab, root); // Set the root node to the head node
     }

3.5 putTreeVal Parsing

    
     / * *
     * Tree version of putVal.
     * If the node does not exist, it is added, and null is returned
     * If the current node exists, return the current node for future value overwriting operations
     * /
       //this, tab, hash, key, newValue
     final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
     Class<? > kc = null;
         boolean searched = false;
     TreeNode<K,V> root = (parent ! = null) ? root() : this; // If the current node is not the root node, you need to trace to the root node
     // Double for loop to determine node position
     for (TreeNode<K,V> p = root;;) {// Start at the root node to determine the position of the key-value pair
             int dir, ph; K pk;
     If ((ph = p.hash) > h)// Compare the current node and compare the hash size of the node
     dir = -1; // Compare node hash > current node hash to find the left subtree
             else if (ph < h)
     dir = 1; // Compare node hash < current node hash find the right subtree
     else if ((pk = p.key) == k || (pk ! = null && k.equals(pk)))
     return p; // If the node already exists, return it directly
             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, only the left and right child nodes can be compared one by one
     if (! searched) {
                     TreeNode<K,V> q, ch;
                     searched = true;
     // Check left or right
     if (((ch = p.left) ! = null && (q = ch.find(h, k, kc)) ! = null) ||
     ((ch = p.right) ! = null && (q = ch.find(h, k, kc)) ! = null))
                         return q;
                 }
                 dir = tieBreakOrder(k, pk);
             }
     // After the previous calculation, we get a size relation between node P and node x
     X is the left child if the hash value of p is greater than x, otherwise x is the right child
             TreeNode<K,V> xp = p;
     // Insert only if the comparison node has no left or right child, otherwise the next cycle (because it is looking for a binary tree)
             if ((p = (dir <= 0) ? p.left : p.right) == null) {
     // Next of the comparison node is next of the new node, because x needs to be the child of p (the tree position needs to be adjusted).
                 Node<K,V> xpn = xp.next;
     TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // Create a tree node
                 if (dir <= 0)
     xp.left = x; // the hash of x is smaller than the comparison node, that is, it is the left child of the comparison node
                 else
     xp.right = x; // the hash of x is larger than the comparison node, that is, it is the right child of the comparison node
                 xp.next = x;
     x.parent = x.prev = xp; // The parent of x of the current node is also the previous node
     if (xpn ! = null)// When the original next node of the comparison node exists, the previous node of the comparison node needs to be reset to point to the new node
                 ((TreeNode<K,V>)xpn).prev = x;
     moveRootToFront(tab, balanceInsertion(root, x)); // Each time rebalance and determine the new root node
     return null; // New node returns NULL
             }
         }
     }
     / *
      *
      * Tie-breaking utility for ordering insertions when equal hashCodes and non-comparable.
      * We don't require a total order, just a consistent insertion rule to maintain equivalence 
      * across rebalancings. Tie-breaking further than necessary simplifies testing a bit.
     * When a and B have the same hash value but cannot be compared, the two referenced addresses are compared directly
     * Complete order is not required in the tree, just use the same rules for balance when inserting
     * /
     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;
     }

3.6 Parsing the getNode method

    
     public V get(Object key) {
     Node<K,V> e; //getEntry changed to getNode
         return (e = getNode(hash(key), key)) == null ? null : e.value;
     }
     / * *
       * Implements Map.get and related methods
     * The get method consists of several steps:
     * 1. Get the first node (that is, the element placed in the array) first -- advantage: no need to iterate first
     * 2. If the head node does not match and the head node next is not empty, then we need to traverse
     * 3. Before traversal, it is necessary to judge whether it is a tree node. If yes, it is traversal according to the red-black tree; otherwise, it is traversal according to the linked list
     * 4. If the node corresponding to the key does not exist, null is returned by default
       * @param hash hash for key
       * @param key the key
       * @return the node, or null if none
     * /
     final Node<K,V> getNode(int hash, Object key) {
         Node<K,V>[] tab; Node<K,V> 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 always matches the head node first
     ((k = first.key) == key || (key ! = null && key.equals(k))))
                 return first;
     // If the head node does not match and the head node next is not empty, then we need to traverse
     if ((e = first.next) ! = null) {
     If the bucket is treed, all nodes in the bucket are TreeNode types
                 if (first instanceof TreeNode)
                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
     // First in first out (FIFO first in first out)
                 do {
     if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k))))
                         return e;
     } while ((e = e.next) ! = null);
             }
         }
     return null; // If the node does not exist, null is returned
     }

3.7 Parsing the getTreeNode method

    
     / * *
       * Calls find for root node.
     * Red-black trees always look up from the root node
     * /
     final TreeNode<K,V> getTreeNode(int h, Object k) {
     return ((parent ! = null) ? root() : this).find(h, k, null);
     }
     / * *
       * Finds the node starting at root p with the given hash and key.
       * The kc argument caches comparableClassFor(key) upon first use comparing keys.
     * Finds the specified key and recurses from the root node
     * /
     final TreeNode<K,V> find(int h, Object k, Class<? > kc) {
     TreeNode<K,V> p = this; // Where this refers to root, see getTreeNode
         do {
             int ph, dir; K pk;
             TreeNode<K,V> pl = p.left, pr = p.right, q;
     // Search principle: the left subtree is smaller than itself, the right subtree is larger than itself, binary search can be
     // Compare hash, the current node hash is small, continue to search the left subtree, otherwise search the right subtree
             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; // If found, return directly
     // If the subtree is empty, check the other subtree
             else if (pl == null)
                 p = pr;
             else if (pr == null)
                 p = pl;
     // The key implements Compareble as well as hash.
     else if ((kc ! = null || (kc = comparableClassFor(k)) ! = null) &&
     (dir = compareComparables(kc, k, pk)) ! = 0)
                 p = (dir < 0) ? pl : pr;
     // The left subtree is not empty.
     else if ((q = pr.find(h, k, kc)) ! = null)
                 return q;
             else
                 p = pl;
     } while (p ! = null);
     return null; // Return null if not found
     }

3.8 Split method

    
     / * *
       * Splits nodes in a tree bin into lower and upper tree bins,or untreeifies if now too small. 
     * Called only from resize; see above discussion about split bits and indices.
     * This method has two main functions:
     * 1. Divide the elements in the bucket into low-order list and high-order list
     * 2. When the number of elements in the bucket is too low, the anti-tree operation (i.e. chain operation) is performed.
     * This method can only be used by the resize method
     * @param map the map Current map
     * @param TAB the table for recording bin heads
     * @param index The index of the table being split current array subscript
     * @param bit the bit of hash to split on
     * /
     final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
     TreeNode<K,V> b = this; / / the current node
         // Relink into lo and hi lists, preserving order
     TreeNode<K,V> loHead = null, loTail = null; //lo=low
     TreeNode<K,V> hiHead = null, hiTail = null; //hi=high
     int lc = 0, hc = 0; //lc=lowCount indicates the number of low elements in the bucket. Hc =highCount indicates the number of high elements in the bucket
     for (TreeNode<K,V> e = b, next; e ! = null; e = next) {
             next = (TreeNode<K,V>)e.next;
             e.next = null;
     //(e.hash & bit) == 0 is equivalent to (e.hash & oldCap) == 0 in resize
     // The elements in the bucket are divided into two parts, i.e. the red-black tree is split into two linked lists
             if ((e.hash & bit) == 0) {
                 if ((e.prev = loTail) == null)
                     loHead = e;
                 else
                     loTail.next = e;
                 loTail = e;
                 ++lc;
             }
             else {
                 if ((e.prev = hiTail) == null)
                     hiHead = e;
                 else
                     hiTail.next = e;
                 hiTail = e;
                 ++hc;
             }
         }
     // Note that the two links are not placed in the corresponding slot in the form of a linked list, but are also judged by the length of the chain
     // The lower list is still in the same bucket
     if (loHead ! = null) {
     // If the number of low level elements is <= the list reduction threshold, then the tree needs to be de-treed, turning the tree back into a list structure
             if (lc <= UNTREEIFY_THRESHOLD)
                 tab[index] = loHead.untreeify(map);
             else {
     tab[index] = loHead; // Reset the original bucket head node
     // If the new bucket head node is not empty, the old bucket needs to be re-treed (because of the re-partition).
     if (hiHead ! = null) // (else is already treeified)
                     loHead.treeify(tab);
             }
         }
     // Index +oldCap = [index+oldCap
     if (hiHead ! = null) {
     // If the number of high-level elements is <= the list reduction threshold, it is necessary to de-tree the tree back to the list structure
             if (hc <= UNTREEIFY_THRESHOLD)
                 tab[index + bit] = hiHead.untreeify(map);
             else {
     tab[index + bit] = hiHead; // Reset the new bucket head node
     // If the old bucket head node is not empty, the new bucket needs to be re-treed (because of the re-partition).
     if (loHead ! = null)
                     hiHead.treeify(tab);
             }
         }
     }

1. HashMap1.7 insufficiency

2. HashMap1.8 optimization

3. Data structure of HashMap

3. New method analysis of HashMap1.8

3.1 tableSizeFor Method Parsing

3.2 putVal method parsing

3.3 Resize method analysis

3.4 Parsing the treeifyBin method

3.5 putTreeVal Parsing

3.6 Parsing the getNode method

3.7 Parsing the getTreeNode method

3.8 Split method

Related Posts

How is Seesion used on the C++ server?

C: Pointers

Design Patterns – A learning journey of chain of Responsibility patterns