🧭 Implementation class of Map interface HashMap

🚀HashMap

HashMap is an implementation class of Map interface, which is displayed in blog Java Map interface We have used HashMap to summarize the commonly used methods.

1. HashMap is the most frequently used implementation class of Map interface.
2. HashMap stores data in the form of key value pairs.
3. key cannot be repeated, but value can be repeated; Null keys and null values are allowed.
4. The order of mapping cannot be guaranteed, that is, the order of inserted data and extracted data cannot be guaranteed to be consistent, because the bottom layer adopts the way of hash table to store.
5. HashMap does not realize synchronization because it is thread unsafe. The method does not synchronize and mutually exclusive operations and is not synchronized.

🛸 HashMap underlying mechanism

🚗 Schematic diagram of ground floor

1. (k,v) is a Node class, which implements map Entry<K,V>.
2. In jdk8 The data structure of array + linked list + red black tree is adopted in the bottom layer of jdk7.0 0 uses the data structure of array + linked list. Today we introduce jdk8 0

🚓 Underlying mechanism

1. The underlying layer of HashMap maintains the array table of Node type, which is null by default.
2. When an object is created, the load factor is initialized to 0.75.
3. When adding a key value pair, find the index position on the table through the hash value of the key. Then judge whether there are elements in the index. If there are no elements, add them directly; If there is an element in the index, continue to judge whether the key of the element is equal to the key of the key value pair to be added. If it is equal, directly replace the value value. If it is not equal, first judge whether it is a tree structure or a linked list structure, and then make corresponding processing.
4. For the first addition, the capacity of the table needs to be expanded to 16. At this time, the threshold is 12.
5. When adding elements, if it is found that the table capacity reaches the threshold, it needs to be expanded twice, and the critical value becomes 0.75 times the length of the current array. Or if there are 8 linked list elements in an index position of the table and the capacity of the array table does not reach 64, the capacity will be doubled.
   6. In java8, if the elements of a linked list exceed TREEIFY_THRESHOLD(8 by default), and the current table size > = min_ TREEIFY_ Capability (64 by default) will be trealized [red black tree].

🚁 Source code analysis

🚕 About adding

1. The put method of HashMap adds elements by calling the putVal method.

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

1. The hash value of the key that needs to be passed in the putVal method is obtained through the hash() method.

  static final int hash(Object key) {
        int h;
        //If the key is null, 0 is returned
        //Not null, return key Hashcode() ^ (H > > > 16), i.e. hash value
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

1. putval method is explained in detail by adding comments in the following source code.

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;// Define auxiliary variables
        //If the current table array is null or length = 0, it will be expanded to 16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; //resize() expansion function
            
        //(n - 1) & hash to get the index position of the array to be inserted
        //If the current location is null, create a new node and join the location
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        //The current location is not null
            Node<K,V> e; K k;
            //If the hash of the key at the table index position is the same as the hash of the key of the key value pair to be added
            //And if the key of the index location node and the key of the key value pair to be added are the same object or
            //equal returns true. The key value pair cannot be added. Replace its value value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
            //If the current index position is already a red black tree, it will be processed in the way of red black tree
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //The first two are not satisfied (followed by a linked list). Traverse the linked list to find the location
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//If the entire linked list is traversed and there is no corresponding hash, it will be added to the back of the linked list
                        p.next = newNode(hash, key, value, null);
                        //After being added to the last side of the linked list, if the number of elements on the current linked list reaches 8
                        //Call treeifyBin() method to convert red black tree
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //If the same is found during the loop traversal comparison,
                    //break out of the loop and replace the original value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
			//If the current node is not null, replace the value value at the node and return the original value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//Version number + 1
        if (++size > threshold)
        //After adding elements, if the number of elements on the current table is greater than the expansion threshold, the array will be expanded
            resize();
        afterNodeInsertion(evict);
        return null;
    }

🚙 About tree transformation (turning into red black tree)

If the current table is null or the capacity of the table has not reached MIN_TREEIFY_CAPACITY, i.e. 64, will not be treed temporarily, but double the capacity expansion.

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)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            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);
        }
    }

🛩️ Simulate HashMap to trigger capacity expansion tree

To tree the linked list at an index position on the table array, you need to add elements to the position, make the number of linked list elements at this position greater than 8, and trigger the treeifyBin method. To make the elements hang on the linked list at an index position on the table array, you need to make the hash values of the added keys the same and the values different. Therefore, I define a Class A as the key value in the key value to be added, rewrite the hashcode() method of this class a, and make all instantiated objects of class a return the same hashcode value, In this way, the added elements can be hung on the linked list at the same table index position one by one.

Class A

import java.util.Objects;

public class A {
    int num;

    public A(int num) {
        this.num = num;
    }

    @Override
    public int hashCode() {
        return 100;
    }
}

HashMapTest test class

import java.util.HashMap;

@SuppressWarnings({"all"})
public class HashMapTest {
    public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        for (int i = 0;i < 12;++i) {
           hashMap.put(new A(i),i);
        }
    }
}

Observe the tree process through Debug
1) When there are 8 linked list elements at an index position of table (the index subscript in the figure below is 4), it is still of Node type.

2) Add another element. At this time, there are 9 linked list elements at the position where the table index is 4, which are still of Node type and are not treelized.

3) Add another one, double the capacity again, re hash, and do not tree.

4) Add another one. At this time, the number of elements on the linked list reaches 8, and the size of the array table reaches 64. Tree it.

🚎 summary

When the number of linked list elements at an index position on the table array reaches 8, the red black tree transformation will not be carried out immediately. Instead, judge whether the size of the array reaches 64 first. If it reaches 64, it will be trealized immediately. If not, double the capacity expansion will be carried out.

🙆‍♀️ Note: the capacity of the table will be doubled in two cases.
1, When the size of the array reaches the threshold (0.75 times the current array size), it will double the capacity, 16, 32, 64128... Until MAXIMUM_CAPACITY(1073741824).
2, When the number of linked list elements at an index position on the table array reaches 8 and the size of the array is not 64, double the capacity.
In fact, in rare cases, the number of elements on the linked list of an index position of the array reaches 8. In most cases, the capacity will be expanded according to the first method. Guys, don't confuse these two expansion methods~~ 😀