Analysis of the underlying mechanism and source code of HashMap

1. Schematic diagram:

1. < K, V > is to use HashMap$Node to realize map Entry<K,V>.
2. The bottom layer of HashMap is JDK7 0 is implemented in [array + list]. jdk8. After 0, it will be realized by [array + list + red black tree]. When the list reaches a certain length, it will be treelized.

2. Capacity expansion mechanism:

1. The array table of Node type maintained by the bottom layer of HashMap is initialized to null
2. When creating an object, initialize the load factor to 0.75
   3. When adding key - value, find the index position inserted in the table through the hash value of the key. If there is no element in the index position, add it directly. If there is an element, judge whether the key value of the element is the same as the key value of the element to be added. If it is the same, directly replace the value. If it is different, judge whether it is a tree structure or a table structure, Then make the corresponding processing. If the capacity is insufficient, it needs to be expanded.
3. First, when adding nodes, the capacity of the table (array) is expanded to 16, and the so-called critical value = 16 * 0.75 (loading factor)
4. If the array uses a critical value, it will expand to 16 * 2 = 32. The new critical value is 32 * 0.75 = 24, and so on
5. In Java 8, if the number of elements of a linked list in the table table reaches the default value of 8, and the size of the table > = 64, the linked list will be number tree (become red black tree), otherwise the array expansion mechanism will be adopted.

Interpretation of source code:

1. Execute the constructor and initialize the loading factor of 0.75

 - (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

2. Call the put() method and calculate the hash value through the key value: algorithm: (H = key. Hashcode()) ^ (H > > > 16)

  public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

3. Core:

• The initialization table is null, the capacity is expanded to 16 through the capacity expansion function, and the type of the table is node < K, V >
• Calculate the index position added for the first time through the hash value, and add the first node
• During the second addition, judge that if the hash value of the index position in the tableb table is the same as the hash value of the key to be added, and they are the same object or equals() returns true, then they can not be added as a new K-V artificially
• Judge whether it is a red black tree (call the tree function if the conditions are met), and judge whether it is a linked list (compare with the nodes in the linked list to judge whether it can be added)
• Finally, if the same value is found, it will not be added and its value value will be replaced directly

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;//Auxiliary variable
        //If the underlying table is null or the length is 0, the capacity will be expanded to 16
        if ((tab = table) == null || (n = tab.length) == 0)//First judge whether the table is empty
            n = (tab = resize()).length;//The size() function is shown in the following figure:
            //Calculate the position of the index in the table through the hash value. If it is empty, add < K, V >
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;//Auxiliary variable
            //
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//Judge whether it is a tree
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//Adding red black tree
            else {//Judge whether it is a linked list for cyclic comparison
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//If there is no same in the linked list, it will be added to the end of the linked list
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                        //After adding, it will judge whether the length of the linked list has reached 8
                        //Call the tree function treeifyBin(tab, hash);
                            treeifyBin(tab, hash);
                        break;//
                    }
                    //If you find the same when traversing the linked list, you can replace the value value without adding it
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//Replace the value value
                afterNodeAccess(e);
                return oldValue;
            }
        }

 newCap = DEFAULT_INITIAL_CAPACITY;//The new capacity is initialized to 16

  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  //table is created for the first time. Its size is 16 and its type is node < K, V >

4. Judgment of capacity expansion: threshold = 16 * 0.75 = 12 (critical value)

       ++modCount;
        if (++size > threshold)//size is greater than the critical value, capacity expansion
            resize();
        afterNodeInsertion(evict);
        return null;
    }