preface

“Like” is a habit.

Click like collection, brilliant life.

Click on [wechat search public number: Programming back pot man] to prevent getting lost.

HashMap series of articles

Did you not understand the member variables in the first HashMap source? Come on!! Collated member variable source code parsing

# # # # # # # # # # # # # # # # # # # # # # # # Every time I get something

Chapter 3 MoxiMoxi!! Have you seen the source code for the PUT method in HashMap?

Do you really know that the resize method in the fourth HashMap source code has another purpose besides expansion?

Leave half sober, leave half drunk!! HashMap treeifyBin, Treeify source parsing

final void treeifyBin(HashMap.Node<K,V>[] tab, int hash)Convert the Node type in the linked list under the current bucket to the TreeNode Node type and to the red-black tree

After the nodes are added, determine whether the number of nodes is greater than TREEIFY_THRESHOLD critical value 8. If so, convert the linked list to red-black tree, and the method of converting red-black tree is treeifyBin. The overall code is as follows:

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
  // Convert to a red-black tree TAB represents the array name hash represents the hash value
  treeifyBin(tab, hash);
Copy the code

Is it true that the TREEIFY_THRESHOLD is converted to a red-black tree as long as the threshold is greater than the threshold 8?

(n = tab.length) < MIN_TREEIFY_CAPACITY The value of MIN_TREEIFY_CAPACITY is 64. There are actually two conditions for switching to red and black. One condition is greater than the threshold of 8, and the other condition is greater than or equal to 64 capacity.

Why does the capacity need to be greater than 64 to allow treification?

If the array is small, convert to a red-black tree, and the traversal is much less efficient. If you have that condition, you’re going to expand it, you’re going to recalculate the hash, you’re going to shorten the list, you’re going to put the data in an array, which is relatively efficient.

The source code to read

// TAB: all nodes in the set. The first Node in the red-black tree is a Node Node
final void treeify(Node<K,V>[] tab) {
 // Define a root node
 TreeNode<K,V> root = null;
 X points to the current node and next points to the next node, which is the root node when first traversed
 for (TreeNode<K,V> x = this, next; x ! =null; x = next) {  // Cast the next node of this node to a tree node  next = (TreeNode<K,V>)x.next;  // Initialize the left and right subtrees of this node to null  x.left = x.right = null;  // Check whether the root node is null, and set the current node to the root node, that is, no root node  // The first pass will enter the judgment and find the root node  if (root == null) {  // The parent of the root node is set to NULL  x.parent = null;  // Set the color of the node to black  x.red = false;  // Assign the current node to the root node. Only one node is successfully assigned, that is, the root node points to the current node  root = x;  }  else {// At this point, the root node already exists  // Get the current node's key and assign it to k  K k = x.key;  // Get the current node hash value assigned to h  int h = x.hash;  // Define the Class to which key belongs Class<? > kc =null;  // Build a real red-black tree  for (TreeNode<K,V> p = root;;) {  // dir indicates the direction, whether to the left or right of the root node  // ph indicates the hash value of the current tree node  int dir, ph;  // Assign the key of the current root node to pk  K pk = p.key;  // Assign the hash value of the root node to ph, if the current root node hash value is greater than the current list node hash value  if ((ph = p.hash) > h)  // Indicates that the current list node will be placed to the left of the current root node  dir = -1;  // Assign the hash value of the root node to ph if the hash value of the current root node is smaller than the hash value of the current list node  else if (ph < h)  // Indicates that the current list node will be placed to the right of the current root node  dir = 1;  // Assign the hash value of the root node to ph if the current root node hash value is equal to the current list node hash value  If the key of the current list node implements the COMPARABLE interface and the current tree node and list node are instances of the same Class  // Then compare the two using comparable.  // If it is still equal, make a final comparison with tieBreakOrder  // dir = compareComparables(kc, k, pk)) == 0  else if ((kc == null && (kc = comparableClassFor(k)) == null) | | (dir = compareComparables(kc, k, pk)) == 0)  // Break the balance  dir = tieBreakOrder(k, pk);   // The current node  TreeNode<K,V> xp = p;  // dir <= 0: The current list node is placed to the left of the current tree node, but not necessarily the left subtree of the tree node, but also the right subtree of the left subtree or a deeper node.  // dir > 0: The current list node is placed to the right of the current tree node, but not necessarily the right subtree of the tree node, but also the left subtree of the right subtree or a deeper node.  // If the current tree node is not a leaf node, it will eventually start with the left or right subtree of the current tree node and then find its position (the current list node)  // If the current tree node is a leaf node, then the current list node can be mounted to the left or right of the current tree node depending on the value of dir.  // Once mounted, the tree needs to be rebalanced. Once balanced, you can move on to the next list node.  if ((p = (dir <= 0)? p.left : p.right) ==null) {  // The current list node is the child of the current tree node  x.parent = xp;  if (dir <= 0)  / / the left subtree  xp.left = x;  else  / / right subtree  xp.right = x;  // After inserting a node, adjust the red-black tree  root = balanceInsertion(root, x);  break;  }  }  }  }  // After the list nodes have been traversed, the resulting tree may undergo multiple balancing operations, and it is uncertain which node in the list is the root node.  // Move the root node of the red-black tree to the first position of the linked list node (table[I]).  moveRootToFront(tab, root); } Copy the code

Source summary

  • 1. Determine whether to expand or tree based on the number of elements in the hash table. The following two conditions must be met
  • 2. If the bucket is tree-traversed, create the same number of tree nodes and copy the contents to establish connections.
  • 3. Then make the first element in the bucket point to the newly created root node and replace the bucket’s list contents with the tree-like contents.

Conversion to red black tree source code analysis

Source code analysis

// TAB: all nodes in the set. The first Node in the red-black tree is a Node Node
final void treeify(Node<K,V>[] tab) {
  // Define a root node
 TreeNode<K,V> root = null;
  X points to the current node and next points to the next node, which is the root node when first traversed
 for (TreeNode<K,V> x = this, next; x ! =null; x = next) {  // Cast the next node of this node to a tree node  next = (TreeNode<K,V>)x.next;  // Initialize the left and right subtrees of this node to null  x.left = x.right = null;  // Check whether the root node is null, and set the current node to the root node, that is, no root node  // The first pass will enter the judgment and find the root node  if (root == null) {  // The parent of the root node is set to NULL  x.parent = null;  // Set the color of the node to black  x.red = false;  // Assign the current node to the root node. Only one node is successfully assigned, that is, the root node points to the current node  root = x;  }  else {// At this point, the root node already exists  // Get the current node's key and assign it to k  K k = x.key;  // Get the current node hash value assigned to h  int h = x.hash;  // Define the Class to which key belongs Class<? > kc =null;  // Build a real red-black tree  for (TreeNode<K,V> p = root;;) {  // dir indicates the direction, whether to the left or right of the root node  // ph indicates the hash value of the current tree node  int dir, ph;  // Assign the key of the current root node to pk  K pk = p.key;  // Assign the hash value of the root node to ph, if the current root node hash value is greater than the current list node hash value  if ((ph = p.hash) > h)  // Indicates that the current list node will be placed to the left of the current root node  dir = -1;  // Assign the hash value of the root node to ph if the hash value of the current root node is smaller than the hash value of the current list node  else if (ph < h)  // Indicates that the current list node will be placed to the right of the current root node  dir = 1;  // Assign the hash value of the root node to ph if the current root node hash value is equal to the current list node hash value  If the key of the current list node implements the COMPARABLE interface and the current tree node and list node are instances of the same Class  // Then compare the two using comparable.  // If it is still equal, make a final comparison with tieBreakOrder  // dir = compareComparables(kc, k, pk)) == 0  else if ((kc == null && (kc = comparableClassFor(k)) == null) | | (dir = compareComparables(kc, k, pk)) == 0)  // Break the balance  dir = tieBreakOrder(k, pk);   // The current node  TreeNode<K,V> xp = p;  // dir <= 0: The current list node is placed to the left of the current tree node, but not necessarily the left subtree of the tree node, but also the right subtree of the left subtree or a deeper node.  // dir > 0: The current list node is placed to the right of the current tree node, but not necessarily the right subtree of the tree node, but also the left subtree of the right subtree or a deeper node.  // If the current tree node is not a leaf node, it will eventually start with the left or right subtree of the current tree node and then find its position (the current list node)  // If the current tree node is a leaf node, then the current list node can be mounted to the left or right of the current tree node depending on the value of dir.  // Once mounted, the tree needs to be rebalanced. Once balanced, you can move on to the next list node.  if ((p = (dir <= 0)? p.left : p.right) ==null) {  // The current list node is the child of the current tree node  x.parent = xp;  if (dir <= 0)  / / the left subtree  xp.left = x;  else  / / right subtree  xp.right = x;  // After inserting a node, adjust the red-black tree  root = balanceInsertion(root, x);  break;  }  }  }  }  // After the list nodes have been traversed, the resulting tree may undergo multiple balancing operations, and it is uncertain which node in the list is the root node.  // Move the root node of the red-black tree to the first position of the linked list node (table[I]).  moveRootToFront(tab, root); } Copy the code

Log nine strings with the same hashCode

Case presentation

@Test
public void test_hash_map_hash(a) {
 ArrayList<String> list = new ArrayList<>();
 list.add("3Qj");
 list.add("2pj");
 list.add("2qK");  list.add("2r,");  list.add("3RK");  list.add("3S,");  list.add("42j");  list.add("43K");  list.add("44,");  list.forEach(s -> System.out.println(s + "= = = =" + s.hashCode())); } Copy the code

Print the result

3Qj  ====  51628
2pj  ====  51628
2qK  ====  51628
2r,  ====  51628
3RK  ====  51628
3S, ==== 51628 42j ==== 51628 43K ==== 51628 44. = = = =51628 Copy the code

Thank you for your thumb up

  • It is not easy to create, and we welcome your likes, comments and concerns
  • Your likes, comments and followers are the biggest support and encouragement for me, and your support and encouragement
  • My motivation to continue to create high quality blogs!!