disclaimer

This article contains some of the author’s personal views, if the description is wrong, welcome to correct

preface

I wrote this article because a recent study of the hashMap source code has been combined with some blogs on the web to facilitate understanding. There are two constants defined in hashMap:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
Copy the code

When the number of linked list elements is greater than 8, it will be converted to a red-black tree; When the number of red-black tree elements is less than 6, it goes back to the list. Through careful observation, the author found that this statement is not rigorous. These two constants are defined in the hashMap, but are not simply converted by the number of elements.

Lists are converted to red-black trees

The ultimate purpose of converting a linked list into a red-black tree is to solve the problem of low read and write efficiency caused by too many elements in a map and large hash conflicts. In the putVal method of the source code, the branches of the red-black tree structure are:

                // Iterate through the list here
                for (int binCount = 0; ; ++binCount) {
                    // Iterate to the last node of the list
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // If the number of list elements is greater than or equal to TREEIFY_THRESHOLD
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // Red-black tree conversion logic
                            treeifyBin(tab, hash);
                        break;
                    }
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                        break;
                    p = e;
                }
Copy the code

TreeifyBin = treeifyBin; treeifyBin = treeifyBin; treeifyBin = treeifyBin;

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
    // Check whether the table length is smaller than MIN_TREEIFY_CAPACITY (64)
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    // If the value is smaller than 64, expand the capacity
            resize();
        else if ((e = tab[index = (n - 1) & hash]) ! =null) {
     // Otherwise, the list is converted to a red-black tree
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while((e = e.next) ! =null);
            if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code

In treeifyBin, instead of simply converting a linked list to a red-black tree, the table length is larger than 64. If the table length is smaller than 64, the table length is expanded to avoid red-black tree structuring. The reason? In my opinion, there are two cases when the linked list length is larger than 8:

  • 1. The table length is sufficient, but hash conflicts are excessive
  • 2. There is no hash conflict. However, when calculating table subscripts, the table length is too small

The second case can be avoided by expanding the capacity. After the expansion, the length of the linked list becomes shorter and the read and write efficiency naturally improves. In addition, the benefit of scaling up versus switching to a red-black tree is that the data structure is simpler. Therefore, it is not necessary to convert a list over 8 to a red-black tree, but to try to expand it first

Red-black trees are converted to linked lists

The basic idea is that when the number of elements in a red-black tree decreases to less than a certain number, it switches back to the linked list. There are two cases of element reduction:

  • 1. Call map’s remove method to remove elements

The remove method of hashMap will enter the removeNode method, find the node to be removed, determine whether the node type is treeNode, and then enter the removeTreeNode method to remove the red-black treeNode logic. The branches of the removeTreeNode method are as follows:

// Determine whether to remove the red-black tree condition
if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
Copy the code

It can be seen that the conversion does not take advantage of the online saying that when the number of nodes is less than UNTREEIFY_THRESHOLD, it is judged by whether the red and black root nodes and their children are empty. The maximum red-black tree structure satisfying this condition is as follows:The number of nodes is 10, larger than UNTREEIFY_THRESHOLD (6), but according to the logic judgment of this method, it needs to be converted into a linked list

  • 2. When resize, the red-black tree is split

If it is a linked list, split the linked list; if it is a TreeNode, perform the split method of TreeNode to split the red-black tree, and the split method converts the red-black tree into the branches of the linked list as follows:

// The logic before this is to hash each node of the red-black tree with a bit &,
// Divide the tree into two red-black trees, lc represents the number of nodes in one tree
if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if(hiHead ! =null) // (else is already treeified)
                        loHead.treeify(tab);
                }
Copy the code

Here, the judgment of UNTREEIFY_THRESHOLD is used. When the red-black tree node element is less than or equal to 6, the untreeify method is called to convert back to the linked list

conclusion

  • 1. HashMap is not necessarily converted to a red-black tree when the number of linked list elements is greater than 8
  • 2. The hashMap’s red-black tree is not necessarily converted to a linked list when it is less than 6, but is only converted to UNTREEIFY_THRESHOLD when it is resize. (why? HHH)