preface

As for thread safety, the put method can expose the problem of thread safety. When two different hashcode s get the same index through hash calculation, they should form a linked list. However, if multiple threads are placed in the same index, it may be overwritten, which is when judging whether the table[index] is empty.

No more nonsense, go directly to the source code

Source code

public V put(K var1, V var2) {
        return this.putVal(hash(var1), var1, var2, false, true);
    }

hash() method

    static final int hash(Object var0) {
        int var1;
        // h = key.hashCode() calculates the hash value
        // ^(H > > > 16) the high 16 bits perform XOR calculation with itself to ensure that the calculated hash is more discrete
        return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
    }

Question: why must the length of the hash bucket group table be to the nth power of 2

For example, we set length=16; In jdk1 In 8, HashMap will calculate the key when put ting, and then it will become index, which is the location of the table array, which is the location of the K and V of this team. Then K - > index should meet three characteristics:

1. Must be int;
2. Ensure sufficient hashing;
3. The index obtained must be within the range of table array, i.e. 0-15;

This requirement corresponds to the Hash method in the source code,

• Step 1: int h = key hashCode();
• Step 2: H ^ (H > > > 16); This is called the perturbation function
• Step 3: (n-1) & H;

Disturbance function

The second step is to reduce the conflict of Hash codes, so as to ensure that both high and low bits of lenth participate in the calculation of Hash when it is relatively small. Hashcode shifts 16 bits to the right without sign, and the high Bit complements 0, and performs * bitwise XOR ^ operation * with hashcode. Why do you want to shift 16 bits to the right? Because you can see that only the last few bits are involved in the operation during the and operation, shift to the right to make the results scattered enough; Why is there an XOR operation? This is a feature of XOR operation. If a person changes and records a certain change, it is also for sufficient hashing of the result
Note: for XOR operation, if the same bit is different, it is 1, and if the same bit is the same, it is 0. 00101 ^ 11100 = 11001. The characteristic of XOR operation is that one bit changes and the result will change.

Step 3: Here we assume that h=834957084. If we want to ensure that 834957084 is between 0-15, we can use modular operation: 834957084% 16. The result must be between 0-15, but * and operation * is selected in the HashMap source code:

Binary calculation:

The binary of 16 is 00010000

16-1 = 15 binary: 0000 1111

0000 1111 any h: 0110 1110 & (and operation, if two are 1, it is 1) result: 0000 1110

The final result is that the minimum binary value must be 0000 and the maximum value must be 1111, that is, decimal system: 0-15, which ensures the range of the third step above. In fact, it is the same as modular operation; But why choose the & and operation? Because the & and operation is a bit operation, and its efficiency is much higher than that of modulus%

In the second step, through the above operation, we find that the upper 4 bits of H do not participate in the operation. If you want the upper 4 bits to participate in the operation process, you need to move to the right. Move h to the right: 0000 0110, and then conduct XOR operation to make the hash better, corresponding to the second step

putVal() method

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // tables array
    Node<K,V> p; // Node at corresponding position
    int n; // Array size
    int i; // Location of the corresponding table
    //  If the table is uninitialized or the capacity is 0, the capacity will be expanded
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // If the Node node in the corresponding location is empty, you can directly create a Node node.
    if ((p = tab[i = (n - 1) & hash] /*Get the Node at the corresponding position*/) == null)
        tab[i] = newNode(hash, key, value, null);
    // If the Node in the corresponding location is not empty, there may be a hash conflict
    else { //Hash conflict logic
        Node<K,V> e; // key is in the old node corresponding to HashMap
        K k;
        // If the found p node is the one to be found, you can use it directly
        if (p.hash == hash && // Judge whether the hash values are equal
            ((k = p.key) == key || (key != null && key.equals(k)))) // Judge whether key s are really equal
            e = p;
        // If the found p Node is a red black tree Node, it is directly added to the tree
        else if (p instanceof TreeNode)//Red black tree logic
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //  If the found p is a Node node, it indicates that it is a linked list and needs to traverse the search
        else {//Linked list logic
            // Sequential traversal of linked list
            for (int binCount = 0; ; ++binCount) {
                // `(e = p.next) `: e points to the next node, because we have determined the initial P node above.
                // If the tail of the linked list has been traversed, it indicates that the key does not exist in the HashMap and needs to be created
                if ((e = p.next) == null) {
                    // Create a new Node
                    p.next = newNode(hash, key, value, null);
                    // If the length of the linked list reaches treeify_ Treeing is performed when threshold (8).
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break; // end
                }
                // If the traversed e-node is what you want to find, you can use it directly
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // end
                // p points to the next node
                p = e;
            }
        }
        //If the corresponding node is found
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // Modify the value of the node. If it is allowed to be modified
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // Callback of the node being accessed
            afterNodeAccess(e);
            // Return old value
            return oldValue;
        }
    }
    // <4.2>
    // Increase the number of modifications
    ++modCount;
    // If the threshold value is exceeded, expand the capacity
    if (++size > threshold)
        resize();
    // Callback after adding node
    afterNodeInsertion(evict);
    // Return null
    return null;
}