preface

December 02, 2020.It was another uneventful Saturday of working overtime. Having just updated an article about the underlying source code of ArrayList, I decided to strike while the iron is hot, and a former colleague of mine told me some of the underlying understanding of hashMap. Now it is inevitable that the writing style is immature and rough, and the notes are also expressed in the language that they can understand for their own summary and combing. If I am lucky enough to be seen by the big guy, I really hope that you can point out my shortcomings and shortcomings, and guide me in what direction I should study and think more deeply. Nuggets — a community that helps developers grow and wants to grow from small fry to small fry.

Hereby note: because this is the second version of the revised version, I wrote the original source code analysis part has been deleted. Happened to see a big guy wrote very good, replaced with his detailed explanation, but also for my future study review.

Big guy blog name: programmer Jiong Hui

Original link:Blog.csdn.net/v123411739/…

HashMap data structure

If the list length is greater than 8, the list will be converted to a red black tree. The time complexity of linked lists is O(n), while the time complexity of red-black trees is O(logn). Although red black tree is a binary search tree in essence, it adds coloring and correlation properties on the basis of the binary search tree to make the red black tree relatively balanced, so as to ensure that the search, insert, delete time complexity of red black tree is O(log n) at worst. Speed up retrieval.

Attribute definitions

Initial capacity: 16

Maximum capacity: 1073741824

Load factor: 0.75

Bucket tree threshold: 8 Indicates the threshold for converting the linked list into a red-black tree. When the length of the linked list is greater than this value, the linked list is converted into a red-black tree during data storage

Bucket list restoration threshold: 6 indicates the threshold for converting a red-black tree into a linked list. When the capacity is expanded (resize ()) (in this case, the storage location of the HashMap data will be recalculated) and the storage location is recalculated, the red-black tree will be converted into a linked list when the number of the original red-black tree is less than this value

Minimum tree capacity threshold: 64 When the capacity of the hash table is greater than this value, the list is allowed to be tree-like (that is, the list is converted to a red-black tree). Otherwise, if there are too many elements in the bucket, the bucket is directly expanded rather than tree-like. To avoid the selection conflict between capacity expansion and tree-like, the value cannot be less than 4 x TREEIFY_THRESHOLD

private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final int MAXIMUM_CAPACITY = 1073741824;
    static final float DEFAULT_LOAD_FACTOR = 0.75F;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
Copy the code

The Put operation

The paper process

  1. When passed a (key, value), fetch the key and hash it to get a new hash value (overriding hashCode and equals methods).
  2. The new hash value and Length-1 obtained by bit operations and operations, that is, the addressing algorithm
  3. Check whether the slot is occupied. If no, the slot is occupied
  4. If they are occupied, check whether keys between nodes are equals and replace values
  5. If Node is treed, traverse the tree and insert key/value pairs directly
  6. If Node is linked and the linked list is traversed, the value is overwritten if the key exists

If key does not exist, it will judge whether the length of the linked list reaches 8. If so, it will tree and insert key value pair 7. Tree method, determine whether the size reaches 64, if yes, then tree, otherwise expand 8. Check whether the capacity expansion threshold is reached. If yes, expand the capacity

Source code method parsing

PutVal method

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 1. Check whether the table is empty or the length is 0. If it is initialized, call resize method if ((TAB = table) = = null | | (n = TAB. Length) = = 0) n = (TAB = the resize ()). The length; // 2. Hash the index position and assign the head node of the index position to p. If (p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); if (p = TAB [I] = (hash, key, value, null); Else {// table <K,V> e; K k; / / 3. Judge whether the key and the hash value of the p nodes with the incoming are equal, if equal, the p is to find the target node, node will be assigned to e p node if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; // 4. Check whether p is TreeNode, Else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key) value); For (int binCount = 0; for (int binCount = 0; ; ++binCount) {// 6. If the next node of p is empty, the destination node cannot be found. If ((e = p.ext) == null) {p.ext = newNode(hash, key, value, null); Check whether the number of nodes exceeds 8. If so, call the treeifyBin method to convert the linked list nodes to red-black tree nodes. If (binCount >= treeify_threshthreshold - 1) treeifyBin(TAB, hash); break; } / / 8. If e nodes exist hash value and the key values are the same as the incoming, e node is the destination node, jump out of the loop if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; }} // 9. If e is not empty, the target node exists, and oldValue if (e! = null) { V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // LinkedHashMap return oldValue; } } ++modCount; If (++size > threshold) resize(); if (++size > threshold) resize(); afterNodeInsertion(evict); // LinkedHashMap return null; }Copy the code

PutTreeVal method

/** * red black tree put operation, */ 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; For (TreeNode<K,V> p = root;;) { int dir, ph; K pk; If ((ph = p.hash) > h) dir = -1; if (ph = p.hash) dir = -1; if (ph = p.hash) dir = -1; If (ph < h) dir = 1; if (ph < h) dir = 1; / / 5. If incoming hash value and the key value is equal to the hash value and the key values of p node, the node p is the destination node, return p nodes else if ((pk = p.k ey) = = k | | (k! = null && k.equals(pk))) return p; / / 6. If there is no k belonging to the class to achieve Comparable interface or equal to the key k and p nodes else if (= = null && (kc, kc = comparableClassFor (k)) = = null) | | (dir = CompareComparables (kc, k, pk)) == 0) {// 6.1 Call find on the left and right nodes of p for the first time. If (! searched) { TreeNode<K,V> 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)) return q; Dir = tieBreakOrder(k, pk); dir = tieBreakOrder(k, pk); // dir<0 = k<pk; TreeNode<K,V> p; If ((p = (dir <=0)? If (p = (dir <=0)? P <K,V> XPN = xp.next; p <K,V> XPN; TreeNode<K,V> x = map.newTreeNode(h, K,V, XPN); If (dir <= 0) // If (dir <= 0), x is the left node of XP. Else // If dir> 0, xp.right = x; xp.next = x; // Set the next node of XP to x.parent = x.rev = xp; // If XPN is not empty, set the prev node of XPN to x, corresponding to the next node of x above. = null) ((TreeNode<K,V>)xpn).prev = x; // 12. Insertion insertion (TAB, balanceInsertion(root, x)); return null; }}Copy the code

tieBreakOrder

// The method used to compare when not comparable or hashCode is identical is just a consistent insert rule to maintain relocation equivalence. 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

treeifyBin

/ / Final void treeifyBin(Node<K,V>[] TAB, int hash) {int n, index; Node<K,V> e; / / 1. If the table is empty or the length of the table is less than 64, call resize method for expansion if (TAB = = null | | (n = TAB. Length) < MIN_TREEIFY_CAPACITY) the resize (); Elseif ((e = TAB [index = (n-1) &hash])! = null) { TreeNode<K,V> hd = null, tl = null; TreeNode<K,V> p = replacementTreeNode(e, null); If (tl == null) // if tl is null, hd = p is the first loop; Else {// 5. If it is not the first time through, process the prev attribute of the current node and the next attribute of the previous node p.rev = tl; // Set the prev attribute of the current node to the previous node tl.next = p; // The next property of the previous node is set to the current node} // 6. Assign the p node to tl to perform some linked list association operations as the previous node in the next loop (p.rev = tl and tl.next = p) tl = p; } while ((e = e.next) ! = null); If ((TAB [index] = hd)! If (TAB [index] = hd)! = null) hd.treeify(tab); }Copy the code

treeify

/ final void treeify(Node<K,V>[] TAB) {TreeNode<K,V> root = null; / final void treeify(Node<K,V>[] TAB) {TreeNode<K,V> root = null; For (TreeNode<K,V> x = this, next; TreeNode<K,V> x = this, next; x ! = null; x = next) { next = (TreeNode<K,V>)x.next; // next the next node assigned to x x.left = x.right = null; If (root == null) {x.parent = null; if (root == null) {x.parent = null; // The root node has no parent x.reed = false; // Root node must be black root = x; } else {K K = x.key; Int h = x.hash; // assign h to the hash value of x Class<? > kc = null; TreeNode<K,V> p = root; TreeNode<K,V> p = root; { int dir, ph; K pk = p.key; If ((ph = p.hash) > h) dir = -1; if (ph = p.hash) dir = -1; if (ph = p.hash) dir = -1; Else if (ph < h) dir = 1; if (ph < h) dir = 1; // 6. The hash value of x equals the hash value of p, Are the key value else if (= = null && (kc / / 6.1 if k does not implement Comparable interface or equal to the key key and p x node (kc = comparableClassFor (k)) = = null) | | (dir = compareComparables(kc, k, pk)) == 0) // 6.2 Use a set of defined rules to compare the size of x and p nodes to determine whether to look left or right dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; // 7. Dir <=0 looks to the left of p, otherwise looks to the right of P. If ((p = (dir <=0)? P value: p value) == null) {// 8. If (dir <= 0) // If (dir <= 0), xp.left = x; Else // If dir > 0, xp.right = x; // 8. Insertion insertion (root = balanceInsertion(root, x)); break; }}}} // 10. If the root node is not the head node of the table index, change it to the head node moveRootToFront(TAB, root); }Copy the code

moveRootToFront

/** * place root on the head node * If the head node of the current index is not root, then associate the previous node of root with the next node, * place root on the head node, Static <K,V> void moveRootToFront(Node<K,V>[] TAB, TreeNode<K,V> root) {int n; static <K,V> void moveRootToFront(Node<K,V>[] TAB, TreeNode<K,V> root) {int n; Check whether root is empty, table is empty, and table length is greater than 0. If (root! = null && tab ! = null && (n = tab.length) > 0) { // 2. Int index = (n-1) &root.hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 3. If the head of the index is not root, replace the head of the index with root if (root! = first) { Node<K,V> rn; TAB [index] = root; TreeNode<K,V> rp = root.prev; If the next node of the root node is not empty, the next node of the root node is not empty. If ((rn = root.next)! If (rn = root.next)! = null) ((TreeNode<K,V>)rn).prev = rp; // 3.3 If the prev of the root node is not empty, set the next attribute of the prev of the root node to the next attribute of the root node. = null) rp.next = rn; 3.4 If the original head node is not empty, set the prev attribute of the original head node to root if (first! = null) first.prev = root; // 3.5 Set the next attribute of the root node to root.next = first; // 3.6 Root has already been placed at the head node of that location, so set the prev property to null root.prev = null; } // 4. check the tree to see if it is normal to assert checkInvariants(root); }Copy the code

checkInvariants

/** * Recursive check */ static <K,V> Boolean checkInvariants(TreeNode<K,V> t) {// Some basic check TreeNode<K,V> tp =  t.parent, tl = t.left, tr = t.right, tb = t.prev, tn = (TreeNode<K,V>)t.next; if (tb ! = null && tb.next ! = t) return false; if (tn ! = null && tn.prev ! = t) return false; if (tp ! = null && t ! = tp.left && t ! = tp.right) return false; if (tl ! = null && (tl.parent ! = t || tl.hash > t.hash)) return false; if (tr ! = null && (tr.parent ! = t || tr.hash < t.hash)) return false; if (t.red && tl ! = null && tl.red && tr ! = null && tr.red) // If the current node is red, the left and right nodes of the node cannot be red at the same time. Return false; if (tl ! = null && ! checkInvariants(tl)) return false; if (tr ! = null && ! checkInvariants(tr)) return false; return true;Copy the code

resize

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; If (oldCap > 0) {// 1.1 Check whether the capacity of the old table exceeds the maximum capacity: // oldCap * 2 is larger than integer.max_value and therefore cannot be redistributed. If (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; return oldTab; } // 1.2 Set newCap to 2 times oldCap, If newCap< maximum capacity and oldCap>=16, Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr < < 1; If (oldThr > 0) newCap = oldThr; if (oldThr > 0) newCap = oldThr; // double threshold} // 2. NewCap = DEFAULT_INITIAL_CAPACITY; newCap = DEFAULT_INITIAL_CAPACITY; newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 4. If (newThr == 0) {float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 5. Set the current threshold to the newly calculated threshold, define a new table with the newly calculated capacity, and set table to the newly defined table. threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 6. If the old table is not empty, then all nodes are traversed and assigned to the new table if (oldTab! = null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) ! [j] = null) {// assign e oldTab[j] = null; // Set the node of the old table to empty so that garbage collector can reclaim space // 7. If (e.next == null) newTab[e.hash & (newcap-1)] = e; if (e.next == null) newTab[e.hash & (newcap-1)] = e; if (e.next == null) newTab[e.hash & (newcap-1)] = e; // 8. If the node is a red-black tree, Else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); if (TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order // 9. Node<K,V> loHead = NULL, loTail = null; // Store the Node whose index position is: Node<K,V> hiHead = null, hiTail = null; // Store the Node whose index position is oldCap. Node<K,V> next; do { next = e.next; If (e.hash & oldCap) == 0) {if (loTail == null) // If loTail is null, LoHead = e; loHead = e; Next = e; // Set loHead to the first node else loTail. // Otherwise add the node after loTail loTail = e; // 9.2 If the hash value of e and the capacity of the old table is not 0, the index position after expansion is: index position of the old table +oldCap else {if (hiTail == null) // If hiTail is null, HiHead = e; // Set hiHead to the first node else hitail. next = e; // Otherwise add the node after hiTail. // Assign hiTail to the new node}} while ((e = next)! = null); // 10. If loTail is not empty (indicating that data from the old table is distributed to nodes at the "old index position" on the new table), set next of the last node // to null, and set the node at the "old index position" on the new table to the corresponding head node if (loTail! = null) { loTail.next = null; newTab[j] = loHead; } // 11. If hiTail is not empty (indicating that the old table has nodes in the old index +oldCap position on the new table), then set next of the last // node to empty. And set the node whose index position on the new table is "old index +oldCap" to the corresponding head node if (hiTail! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }}}}} // 12. Return newTab; }Copy the code

spilt

/** * After the expansion, the hash distribution of red-black tree can only exist in two positions: OldCap */ final void split(HashMap<K,V> map, Node<K,V>[] TAB, int index, int bit) {TreeNode<K,V> b = this; TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; TreeNode<K,V> hiHead = null; Int lc = 0, hc = 0; For (TreeNode<K,V> e = b, next; TreeNode<K,V> e = b, next; e ! = null; E = next) {// Next = (TreeNode<K,V>)e.next; // next next node assigned to e e.next = null; // Set the node of the old table to empty for garbage collector to collect // 2. If e hash and the capacity of the old table is 0, the expanded index position is the same as that of the old table. If ((e.hash & bit) == 0) {if ((e.rev = loTail) == null) // If loTail is null, LoHead = e; loHead = e; Next = e; // Set loHead to the first node else loTail. // Otherwise add the node after loTail loTail = e; // Assign loTail to the new node ++lc; If the hash value of e and the capacity of the old table are not 0, the index position after the expansion is: Index position of the old table +oldCap else {if ((e.rev = hiTail) == null) // If hiHead is empty, the node is the first node hiHead = e. // Set hiHead to the first node else hitail. next = e; // Otherwise add the node after hiTail. // Assign hiTail to the new node ++hc; // Index position is old index +oldCap number of nodes}} // 4. If (loHead! If (lc <= UNTREEIFY_THRESHOLD) TAB [index] = lohead.untreeify (map); if (lc <= UNTREEIFY_THRESHOLD) TAB [index] = loHead.  Else {// 4.2 set TAB [index] = loHead; // If hiHead is not empty, it means that the original red black tree has been changed and a new red black tree needs to be rebuilt. // Create a new red-black tree lohead.treeify (TAB) with loHead as root; }} // 5. If (hiHead! If (hc <= UNTREEIFY_THRESHOLD) TAB [index + bit] = if (hc <= UNTREEIFY_THRESHOLD) TAB [index + bit] = hiHead.untreeify(map); Else {// 5.2 Set TAB [index + bit] = hiHead; // If loHead is not empty, the original red black tree has been changed, and a new red black tree needs to be rebuilt. = null) // 5.4 Build a new red-black tree hihead.treeify (TAB) with hiHead as the root; }}}Copy the code

untreeify

*/ Final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null; For (Node<K,V> q = this; for (Node<K,V> q = this; q ! = null; ReplacementNode <K,V> p = map.replacementNode(q, null); If (tl == null) hd = p; if (tl == null) hd = p; Next = p else tl.next = p; tl = p; // 5. Each time the tl node points to the current node, i.e., the tail node} // 6. Return hd;Copy the code