Photo by hippopx.com

We know that the bottom layer of HashMap is composed of arrays, linked lists and red-black trees. When expanding HashMap, not only the array capacity is doubled, but also the hash value of all elements will be recalculated, because the hash value will also change after the length is expanded.

If it is a simple Node object, you just need to recalculate the subscript. If it is a linked list and a red-black tree, the operation will be more complicated.

What do we do with linked lists when we rehash?

Suppose a HashMap originally had a bucket size of 16. 19, 3, 35 at subscript 3 form a linked list due to index conflicts.


When the HashMap is expanded from 16 to 32, 19, 3, and 35 are rehashed into two linked lists.


Check the JDK1.8 HashMap source code, we can see the list optimization operations as follows:

// Split the list into two lists
// list 1 is stored in a low place.
Node<K,V> loHead = null, loTail = null;
// List 2 is stored high (old index + old array length)
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next; do {  next = e.next;  / / chain table 1  if ((e.hash & oldCap) == 0) {  if (loTail == null)  loHead = e;  else  loTail.next = e;  loTail = e;  }  / / chain table 2  else {  if (hiTail == null)  hiHead = e;  else  hiTail.next = e;  hiTail = e;  } } while((e = next) ! =null); // List 1 is stored in the original index location if(loTail ! =null) {  loTail.next = null;  newTab[j] = loHead; } // List 2 contains the offset of the old index plus the length of the old array if(hiTail ! =null) {  hiTail.next = null;  newTab[j + oldCap] = hiHead; } Copy the code

In JDK1.8, we can split the list into two parts: high and low, and place the list at the original index or at the offset of the original index plus the original array length. So let’s do it in bits.

Let’s review the remainder of the original hash:


Take a look at the bit operations done to judge a rehash, i.e. E.hash & oldCap:


Let’s look at the actual redundancy process after capacity expansion:


Is this wave operation very 666? Why the integer power -1 of 2 can be ampersand and can replace the remainder calculation? Because the binary power -1 of 2 is special, that is, a string of 11111 is ampersand with this string of numbers 1. To achieve the effect of redundant. The binary power of 2 is also special, with a 1 followed by a string of zeros.

For example, if 16 -> 32 = 10000 -> 100000, then its n-1 is 15 -> 32 = 1111 -> 11111. That’s one more index, so the index after the expansion can be calculated from the original index. The difference is that in the figure above, where I marked it in red, if I marked it in red 0, then I would have the same result, if I marked it in red 1, then I would have the same index + offset. How to determine whether 0 or 1 is marked red is to put E. hash & oldCap.

What happens to red-black trees when I rehash them?

// Red black tree list threshold
static final int UNTREEIFY_THRESHOLD = 6;

// Perform capacity expansion
final Node<K,V>[] resize() {
 / /...  else if (e instanceof TreeNode)  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  // ... }  final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {  TreeNode<K,V> b = this;  // Relink into lo and hi lists, preserving order  // Same as linked lists, high and low  TreeNode<K,V> loHead = null, loTail = null;  TreeNode<K,V> hiHead = null, hiTail = null;  int lc = 0, hc = 0;  / * ** TreeNode inherits Node indirectly, keeping Next and traversing it like a linked list* The operations here are the same as in a linked list* /  for(TreeNode<K,V> e = b, next; e ! =null; e = next) {  next = (TreeNode<K,V>)e.next;  e.next = null;  // bit 就是 oldCap  if ((e.hash & bit) == 0) {  if ((e.prev = loTail) == null)  loHead = e;  else  / / end plug  loTail.next = e;  loTail = e;  ++lc;  }  else {  if ((e.prev = hiTail) == null)  hiHead = e;  else  hiTail.next = e;  hiTail = e;  ++hc;  }  }   // Tree the low level list  if(loHead ! =null) {  // If the loHead is not empty and the list length is less than or equal to 6, then the red-black tree is turned into a list  if (lc <= UNTREEIFY_THRESHOLD)  tab[index] = loHead.untreeify(map);  else {  / * ** hiHead == null* All nodes are still in the original position, the tree structure remains unchanged, no need to re-tree* /  tab[index] = loHead;  if(hiHead ! =null) // (else is already treeified)  loHead.treeify(tab);  }  }  // Tree the high order list, logic is the same as above  if(hiHead ! =null) {  if (hc <= UNTREEIFY_THRESHOLD)  tab[index + bit] = hiHead.untreeify(map);  else {  tab[index + bit] = hiHead;  if(loHead ! =null)  hiHead.treeify(tab);  }  } } Copy the code

It can be seen from the source code, the split of red-black tree and linked list logic is basically the same, the difference is that after remapping, the red-black tree will be split into two linked lists, according to the length of the list, determine whether the list needs to be re-treed.

Source code series

Java source code Series 1 – ArrayList

Java source code Series 2 – HashMap

Java source code series 3 – LinkedHashMap

reference

HashMap (JDK1.8)

This post was originally posted on my personal blog http://chaohang.top

The author is Zhang Xiaochao

Please indicate the source of reprint

Please follow my wechat official account [Chaochao Won’t fly] to get the latest updates.


This article is formatted using MDNICE