This is the 14th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The principle of HashMap is that key-value pairs with the same bucket subscript are stored in a linked list. As the list gets longer, finding and adding (the need to determine whether the key already exists) requires traversing the list, which becomes slower. A mechanism to convert a linked list to a red-black tree was added in JDK 1.8, but converting a red-black tree is not a cheap operation, and treeify only occurs when the list length is greater than or equal to TREEIFY_THRESHOLD.

    /**
     * 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.
     */
    static final int TREEIFY_THRESHOLD = 8;
Copy the code

The default value for TREEIFY_THRESHOLD is 8, and putVal() has the following source code:

    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
Copy the code

In fact, it does not treeify any list longer than 8. When table. Length (the number of buckets) is less than MIN_TREEIFY_CAPACITY, the table is expanded rather than converted to a red-black tree.

Use jdk1.8 as an example to open the source section of HashMap and analyze the attributes of the TreeNode inside the red-black tree:

Static final class TreeNode<K,V> extends linkedhashMap. Entry<K,V> {// TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> right; TreeNode<K,V> prev; TreeNode<K,V> prev; Boolean red; . }Copy the code

The left-handed rotatory method rotateLeft is as follows:

Static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {//root: indicates the root node //p: indicates the node to be adjusted //r: indicates the right node of p //pp: indicates the parent node of p //rl: indicates the left child node of p <K,V> r, pp, rl; // if r is null, rotation is meaningless if (p! = null && (r = p.right) ! = null) {// set the parent of rl to p if ((rl = p.right = r.left)! = null) rl.parent = p; If ((pp = r.arent = p.arent) == null) (root = r).red = false; Else if (pp.left == p) pp.left = r; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; }Copy the code

Similarly, the rotateRight method is as follows:

Static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {//root: indicates the root node //p: indicates the node to be adjusted //l: indicates the left node of p //pp: indicates the parent node of p //lr: indicates the right child node of the left child of p TreeNode<K,V> l, pp, lr; If (p! = null && (l = p.left) ! = null) {// set lr parent to p if ((lr = p.lift = l.light)! = null) lr.parent = p; If ((pp = l.arent = p.arent) == null) (root = l).red = false; Else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; }Copy the code

Expansion mechanism

HashMap is implemented based on array + linked lists and red-black trees, but the length of the bucket used to hold the key value is fixed and determined by initialization.

Then, as the number of data inserts increases and the load factor increases, we need to expand to store more data. One important aspect of scaling is that the optimization in JDK1.8 eliminates the need to recalculate the hash value of each element.

Here we will focus on the expansion code (comment section);

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // Cap is short for capacity. If the capacity is not empty, it is initialized. If (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr  = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold // initial capacity was placed in The meaning of threshold in translation is as follows; // When initializing, assign the value of threshold to newCap. // HashMap uses the threshold variable to temporarily store the value of the initialCapacity parameter newCap = oldThr; The I so initial threshold 05.6 using defaults so {// The I so initial threshold 05.6 using defaults is the default so << 4; Aka 16 // Threshold; Is the product of the default capacity and the load factor, 0.75 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // if newThr == 0, use the threshold formula to calculate the capacity if (newThr == 0) {float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY (int)ft : Integer.MAX_VALUE); } threshold = newThr; @suppresswarnings ({" unchecked","unchecked"}) // Listing key Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab ! For (int j = 0; oldCap = 0; oldCap = 0; oldCap = 0; oldCap = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) ! = null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; Else if (e instanceof TreeNode) // Where split is a red black tree split operation. Operated during remapping. ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // Here is the list, if the current list is stored as a linked list, then group the list nodes in the original order {here is a special article on how to split the list without recalcalculating the hash value. } do {next = e.ext; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); // Map the list to the bucket if (loTail! = null) { loTail.next = null; newTab[j] = loHead; } if (hiTail ! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

Mainly include;

  1. When expanding, calculate the new newCap and newThr, which are abbreviations of Capacity and Threshold
  2. NewCap for innovative array bucketsnew Node[newCap];
  3. With the expansion, the elements that were previously stored as linked lists and red-black trees due to hash collisions need to be split and stored in new locations.