brief introduction

HashMap uses a key/value storage structure, where each key corresponds to a unique value, and queries and modifications are fast enough to achieve the average time complexity of O(1).It is non-thread safe and does not guarantee the order in which elements are stored;

Inheritance System

HashMap implements Cloneable and can be cloned.

HashMap implements Serializable and can be serialized.

HashMap inherits from AbstractMap, implements the Map interface, and has all the capabilities of Map.

storage structure

In Java, HashMap's implementation uses a complex structure (array + list + red-black tree). An element of the array is also called a bucket.

When an element is added, the position of the element in the array is calculated based on the hash value. If there is no element in the position, the element is placed here directly. If there is an element in the position, the element is placed at the end of the list as a list of chains.

When the number of elements in a chain table reaches a certain number (and the length of the array reaches a certain length), the chain table is converted to a red-black tree to improve efficiency.

Array query efficiency is O(1), chain table query efficiency is O(k), red-black tree query efficiency is O(log k), K is the number of elements in the bucket, so when the number of elements is very large, converting to red-black tree can greatly improve efficiency.

Source Parsing

attribute

/**
 * The default initial capacity is 16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * Maximum capacity is 30th power of 2
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * Default Load Factor
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * Tree when the number of elements in a bucket is greater than or equal to 8
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * Convert a tree into a chain table when the number of elements in a bucket is less than or equal to 6
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * Treing occurs when the number of barrels reaches 64
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * Arrays, also known as bucket s
 */
transient Node<K,V>[] table;

/**
 * Cache as entrySet()
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * Number of elements
 */
transient int size;

/**
 * Number of modifications to execute a fast failure strategy during iteration
 */
transient int modCount;

/**
 * Expansion when the number of buckets in use reaches threshold = capacity * loadFactor
 */
int threshold;

/**
 * Loading factor
 */
final float loadFactor;

1. capacity
   Capacity is the length of the array, that is, the number of buckets, which defaults to 16 and has a maximum of 30 power of 2. It can be dendrized when capacity reaches 64.
2. Loading factor
   Loading factor is used to calculate the capacity to expand when the capacity is reached. The default loading factor is 0.75.
3. Tree
   Treing is done when the capacity reaches 64 and the length of the chain table reaches 8, and when the length of the chain table is less than 6.

Node Internal Class

Node is a typical single-chain list node where hash stores hash values calculated by the key.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

TreeNode Internal Class

It inherits from the Entry class in LinkedHashMap, which we will talk about later.

TreeNode is a typical tree node, where prev is a node in the chain table and is used to quickly find its preceding node when deleting an element.

// In HashMap
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

// Typical two-way linked list node in LinkedHashMap
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

HashMap() construction method

Empty parameter construction methods, all using default values.

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap(int initialCapacity) construction method

Call the HashMap(int initialCapacity, float loadFactor) construction method and pass in the default load factor.

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity) construction method

The validity of the incoming initial capacity and load factor is determined, and the expansion threshold is calculated to be the nearest n-th power of the incoming initial capacity.

public HashMap(int initialCapacity, float loadFactor) {
    // Check that the incoming initial capacity is legal
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // Check if the loading factor is legal
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // Calculate expansion threshold
    this.threshold = tableSizeFor(initialCapacity);
}

static final int tableSizeFor(int cap) {
    // The expansion threshold is the nearest 2 n-th power up to the initial incoming capacity
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

put(K key, V value) method

Entry to add elements.

public V put(K key, V value) {
    // Call hash(key) to calculate hash value of key
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    // If the key is null, the hash value is 0, otherwise the hashCode() method of the key is called
    // And make the 16-bit high exclusive to the entire hash, in order to make the calculated hash more dispersed
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, i;
    // Initialize if the number of buckets is 0
    if ((tab = table) == null || (n = tab.length) == 0)
        // Call resize() initialization
        n = (tab = resize()).length;
    // (n - 1) & In which bucket is the hash element calculated
    // If there is no element in the bucket, place the element in the first place in the bucket
    if ((p = tab[i = (n - 1) & hash]) == null)
        // Create a new node in the bucket
        tab[i] = newNode(hash, key, value, null);
    else {
        // If an element already exists in the bucket
        Node<K, V> e;
        K k;
        // If the key of the first element in the bucket is the same as the key of the element to be inserted, save in e for subsequent modification of the value value
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // If the first element is a tree node, call the tree node's putTreeVal to insert the element
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        else {
            // Traversing through the chain table corresponding to this bucket, binCount stores the number of elements in the chain table
            for (int binCount = 0; ; ++binCount) {
                // If no element of the same key is found after the chain table has been traversed, indicating that the corresponding element of the key does not exist, a new node is inserted at the end of the chain table
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // If the length of the chain list is greater than 8 after inserting a new node, determine if it needs to be tree, because the first element is not added to the binCount, so here-1
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Exit the loop if the key to be inserted is found in the list of chains
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // If an element of the corresponding key is found
        if (e != null) { // existing mapping for key
            // Record old values
            V oldValue = e.value;
            // Determine if old values need to be replaced
            if (!onlyIfAbsent || oldValue == null)
                // Replace old value with new value
                e.value = value;
            // What to do after the node is accessed, used in LinkedHashMap
            afterNodeAccess(e);
            // Return Old Value
            return oldValue;
        }
    }
    // Note here that no elements were found
    // Modifications plus 1
    ++modCount;
    // Number of elements plus 1 to determine if expansion is required
    if (++size > threshold)
        // Expansion
        resize();
    // What to do after a node is inserted, used in LinkedHashMap
    afterNodeInsertion(evict);
    // Element not found returns null
    return null;
}

1. Calculates the hash value of the key;
2. Initialize the bucket if the number of buckets (array) is 0;
3. If the key is in a bucket with no elements, insert it directly;
4. If the key of the first element in the bucket in which the key is located is the same as the key to be inserted, the element is found and processed in a subsequent process (9);
5. If the first element is a tree node, call putTreeVal() of the tree node to find the element or insert the tree node;
6. If not, traverse the chain table corresponding to the bucket to find out if the key exists in the chain table.
7. If an element of the corresponding key is found, it is processed in a subsequent process (9);
8. If no key element is found, a new node is inserted at the end of the chain table and a tree is determined.
9. If an element of the corresponding key is found, it determines whether the old value needs to be replaced and returns the old value directly.
10. If an element is inserted, add 1 to the number and determine if expansion is required;

resize() method

Expansion method.

final Node<K, V>[] resize() {
    // Old Array
    Node<K, V>[] oldTab = table;
    // Old capacity
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // Old expansion threshold
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // If the old capacity reaches the maximum capacity, no expansion is carried out
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            // If the old capacity is less than twice the maximum capacity and the old capacity is greater than the default initial capacity (16), the capacity is expanded to two and the expansion threshold is doubled.
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        // map created with a non-default constructor where the first element insertion will go
        // If the old capacity is 0 and the old expansion threshold is greater than 0, assign the new capacity to the old threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // Call the map created by the default constructor and the first insertion of an element will come here
        // If the old capacity expansion threshold is 0, indicating that it has not been initialized, the initialization capacity is the default capacity, and the expansion threshold is the default capacity*the default load factor
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // If the new expansion threshold is 0, it is calculated as the capacity*loading factor, but cannot exceed the maximum capacity
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                (int) ft : Integer.MAX_VALUE);
    }
    // Assignment Expansion Threshold is New Threshold
    threshold = newThr;
    // Create a new capacity array
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    // Assign bucket to new array
    table = newTab;
    // Move elements if the old array is not empty
    if (oldTab != null) {
        // Traversing through old arrays
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            // Assign to e if the first element in the bucket is not empty
            if ((e = oldTab[j]) != null) {
                // Empty old drums for GC recycling  
                oldTab[j] = null;
                // If there is only one element in this bucket, calculate its position in the new bucket and move it to the new bucket
                // Since the capacity is doubled each time, the first element here must have no elements when the new bucket is moved to it
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // If the first element is a tree node, break up the tree into two trees and insert it into a new bucket
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // If this list has more than one element and is not a tree
                    // Then split into two chains and insert them into a new bucket
                    // For example, if the original capacity was 4, 3, 7, 11, 15 these four elements are all in barrel 3
                    // Now expanding to 8, 3 and 11 will still be in barrel 3, 7 and 15 will be moved to barrel 7
                    // That is, it divides into two chains
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        // (e.hash & oldCap) == 0 elements in low-order list
                        // For example, 3 & 4 == 0
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            // (e.hash & oldCap)!= 0 element in high-order list
                            // For example, 7 & 4!= 0
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // Traversal is complete and divides into two chains
                    // The list of low chains is in the same position in the new bucket as in the old one (that is, 3 and 11 are still in bucket 3).
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // The position of the high list in the new bucket is exactly where it was before plus the old capacity (that is, 7 and 15 moved to bucket 7).
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1. If the default construction method is used, the element is initially inserted with a default value of 16 and a threshold of 12 for expansion.
2. If a non-default construction method is used, the initial capacity at the first insertion of an element is equal to the expansion threshold, which in the construction method is equal to the n-th power of the nearest two incoming capacities up;
3. If the old capacity is greater than 0, the new capacity is equal to twice the old capacity, but not more than the 30th power of the maximum capacity 2, and the new expansion threshold is twice the old expansion threshold.
4. Create a new capacity bucket;
5. Move elements, the original chain table is divided into two chains, the low chain table is stored in the location of the original bucket, the high chain table is moved to the location of the original bucket and the old capacity is added.

TreeNode.putTreeVal(...) Method

Method of inserting elements into a red-black tree.

final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab,
                                int h, K k, V v) {
    Class<?> kc = null;
    // Mark whether the node for this key is found
    boolean searched = false;
    // Find the root node of the tree
    TreeNode<K, V> root = (parent != null) ? root() : this;
    // Traverse from the root node of the tree
    for (TreeNode<K, V> p = root; ; ) {
        // dir=direction, mark left or right
        // ph=p.hash, hash value of current node
        int dir, ph;
        // pk=p.key, the key value of the current node
        K pk;
        if ((ph = p.hash) > h) {
            // The current hash is larger than the target hash, indicating on the left
            dir = -1;
        }
        else if (ph < h)
            // The current hash is smaller than the target hash, indicating on the right
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // Both have the same hash and the same key, indicating that the node was found and returned directly to it
            // Go back to putVal() to determine if you need to modify its value
            return p;
        else if ((kc == null &&
                // Returns the true class if k is a subclass of Comparable, otherwise returns null
                (kc = comparableClassFor(k)) == null) ||
                // Returns 0 if k and pk are not of the same type, otherwise returns the result of comparison
                (dir = compareComparables(kc, k, pk)) == 0) {
            // This condition means that they have the same hash but one of them is not a Comparable type or the other is different
            // For example, if key is of type Object, you can pass either String or Integer, which may have the same hash value
            // Storing elements with the same hash value in a red-black tree in the same subtree is equivalent to finding the vertex of the subtree
            // Traverse the left and right subtrees from this vertex to find out if there are any elements that are the same as the key to be inserted
            if (!searched) {
                TreeNode<K, V> q, ch;
                searched = true;
                // Traversing the left and right subtrees found a direct return
                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;
            }
            // If they are of the same type, then hash values are calculated based on their memory addresses and compared
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K, V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // If you do not find an element for the key at the end, create a new node
            Node<K, V> xpn = xp.next;
            TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K, V>) xpn).prev = x;
            // Balance after inserting a tree node
            // Move the root node to the first node in the chain table
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

1. Find the root node;
2. Look from the root node;
3. Comparing hash and key values, if they are the same, returns directly, and decides whether to replace the value in the putVal() method.
4. Based on the hash value and key value, it determines whether to search in the left or right subtree of the tree and finds a direct return.
5. If you don't find one at the end, insert the element in the tree and balance it.

treeifyBin() method

If the length of the list of chains after inserting an element is greater than or equal to 8, determine whether the tree is needed.

final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // If the number of barrels is less than 64, expand without tree
        // Because after expansion, the chain list will be divided into two chains to reduce the number of elements
        // Of course, it's not necessarily. For example, if the capacity is 4, it contains all the elements whose remainder is equal to 3 divided by 4.
        // This will not reduce the length of the chain table even if the capacity is expanded
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K, V> hd = null, tl = null;
        // Replace all nodes with tree nodes
        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 you go into the loop above, start treeing from the beginning node
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

TreeNode.treeify() method

A true tree approach.

final void treeify(Node<K, V>[] tab) {
    TreeNode<K, V> root = null;
    for (TreeNode<K, V> x = this, next; x != null; x = next) {
        next = (TreeNode<K, V>) x.next;
        x.left = x.right = null;
        // The first element acts as the root node and is a black node. The other elements are inserted into the tree in turn and then balanced.
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        } else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // Find the location where the element is inserted from the root node
            for (TreeNode<K, V> p = root; ; ) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                        (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                // If no element is found at last, insert
                TreeNode<K, V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // Balance after insertion, which inserts a red node by default, in the balanceInsertion() method
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // Move the root node to the head node of the list, because the first element after balance is not necessarily the root node
    moveRootToFront(tab, root);
}

1. Traverse starts from the first element of the list of chains;
2. Use the first element as the root node;
3. The other elements are inserted into the red and black trees in turn and then balanced.
4. Move the root node to the position of the first element in the list (because the root node changes when balancing);

get(Object key) method

public V get(Object key) {
    Node<K, V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K, V> getNode(int hash, Object key) {
    Node<K, V>[] tab;
    Node<K, V> first, e;
    int n;
    K k;
    // If the number of buckets is greater than 0 and the key to be found is in a bucket where the first element of the bucket is not empty
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        // Check if the first element is the one to look for and if it is returned directly
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // If the first element is a tree node, look it up as a tree
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);

            // Otherwise, traverse the entire list to find the element
            do {
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

1. Calculates the hash value of the key;
2. Find the bucket where the key is located and its first element;
3. If the key of the first element is equal to the key to be found, it is returned directly.
4. If the first element is a tree node, look it as a tree, otherwise look it as a chain table.

TreeNode.getTreeNode(int h, Object k) method

final TreeNode<K, V> getTreeNode(int h, Object k) {
    // Find from the root node of the tree
    return ((parent != null) ? root() : this).find(h, k, null);
}

final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
    TreeNode<K, V> p = this;
    do {
        int ph, dir;
        K pk;
        TreeNode<K, V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            // Left Subtree
            p = pl;
        else if (ph < h)
            // Right Subtree
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // Direct return found
            return p;
        else if (pl == null)
            // hash is the same but key is different, left subtree is empty right subtree
            p = pr;
        else if (pr == null)
            // Right subtree is empty left subtree
            p = pl;
        else if ((kc != null ||
                (kc = comparableClassFor(k)) != null) &&
                (dir = compareComparables(kc, k, pk)) != 0)
            // Comparing the size of key values by compare method determines whether to use left or right subtrees
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            // If none of the above fails, try looking in the right subtree
            return q;
        else
            // Find it in the left subtree
            p = pl;
    } while (p != null);
    return null;
}

The classical binary search tree searching process first compares according to hash value, then decides whether to search left or right subtree according to key value comparison.

remove(Object key) method

public V remove(Object key) {
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
}

final Node<K, V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, index;
    // The first element of the bucket in which the number of buckets is greater than 0 and the element to be deleted is not empty
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
        Node<K, V> node = null, e;
        K k;
        V v;
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            // If the first element happens to be the one you are looking for, assign it to the node variable and delete it later
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                // If the first element is a tree node, find the node as a tree
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
            else {
                // Otherwise, traverse the entire list to find elements
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key ||
                                    (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // If an element is found, see if the parameter needs to match the value, delete directly if no match is needed, and see if the value is equal to the value passed in
        if (node != null && (!matchValue || (v = node.value) == value ||
                (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                // If it is a tree node, call the deletion method of the tree (called with node, delete yourself)
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // If the element to be deleted is the first element, move the second element to the first position
                tab[index] = node.next;
            else
                // Otherwise delete node
                p.next = node.next;
            ++modCount;
            --size;
            // Delete node postprocessing
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

1. Find the node where the element is located first;
2. If the node found is a tree node, the removal node is processed by the tree.
3. If the node found is the first node in the bucket, move the second node to the first position;
4. Otherwise, delete nodes according to the list of chains;
5. Modify size, call post-processing after removing nodes, etc.

TreeNode.removeTreeNode(...) Method

final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,
                          boolean movable) {
    int n;
    // Return directly if the number of buckets is 0
    if (tab == null || (n = tab.length) == 0)
        return;
    // Index of Node in Bucket
    int index = (n - 1) & hash;
    // First node, root node, root left child node
    TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
    // Succeeding node, preceding node
    TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;

    if (pred == null)
        // If the leading node is empty, indicating that the current node is the root node, assigning the successor node to the position of the first node is equivalent to deleting the current node
        tab[index] = first = succ;
    else
        // Otherwise, setting the next node of the preceding node as the successor node of the current node is equivalent to deleting the current node
        pred.next = succ;

    // If the succeeding node is not empty, having the preceding node of the succeeding node point to the preceding node of the current node is equivalent to deleting the current node
    if (succ != null)
        succ.prev = pred;

    // If the first node is empty, there are no successor nodes, go back directly
    if (first == null)
        return;

    // If the parent node of the root node is not empty, look up the parent node again
    if (root.parent != null)
        root = root.root();

    // If the root node is empty, it needs to be de-tree (converting the tree to a chain table)
    // If you need to move the node and the tree height is small, you need to de-tree it
    if (root == null
            || (movable
            && (root.right == null
            || (rl = root.left) == null
            || rl.left == null))) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }

    // These are all nodes in the deletion list, but the next is the node directly deleting the red-black tree (because TreeNode itself is both a list node and a tree node)

    // The code below relates to red and black trees, but there are no more comments here.The general process of deleting a red-black tree node is to find the smallest node in the right subtree where it will be deleted and balance it

1. TreeNode itself is both a chain table node and a red-black tree node.
2. Delete the list node first;
3. Remove the red-black tree nodes and balance them;

summary

1. HashMap is a Hash list with a storage structure (array + Chain Table + red-black tree);
2. HashMap has a default initial capacity of 16 (1 < 4), a default load factor of 0.75f, and a capacity of always 2 to the n-th power;
3. HashMap doubles its capacity each time it expands;
4. When the number of barrels is less than 64, it will not be dendrified, but will only expand capacity.
5. Tree when the number of barrels is greater than 64 and the number of elements in a single barrel is greater than 8.
6. When the number of elements in a single bucket is less than 6, it is dendrified.
7. HashMap is a non-thread-safe container;
8. HashMap finds added elements with O(1) time complexity;

Red and Black Tree Nodule

The red-black tree has the following five properties:

(1) Nodes are red or black.

(2) The root node is black.

(3) Each leaf node (NIL node, empty node) is black.

(4) The two children of each red node are black.(You cannot have two consecutive red nodes on all paths from each leaf to the root)

(5) All paths from any node to each leaf contain the same number of black nodes.

The time complexity of a red-black tree is O(log n), which is proportional to the height of the tree.

Every insertion and deletion of red and black trees needs to be balanced, which may change the position of the root node, color conversion, left-hand, right-hand, and so on.