Collection of articles: gitee.com/mydb/interv…

HashMap is one of the most frequently used data types and one of the must-ask questions in an interview. In particular, its underlying implementation principle is both a common interview question and the cornerstone of understanding HashMap, so its importance is self-evident.

Underlying implementation of HashMap

The underlying implementation of HashMap in JDK 1.7 and JDK 1.8 is different,In JDK 1.7, HashMap was implemented using arrays + linked lists, whereas in JDK 1.8 it was implemented using arrays + linked lists or red-black trees. The implementation of HashMap in JDK 1.7 looks like this:The implementation of HashMap in JDK 1.8 looks like this:This article focuses on HashMap in the mainstream JDK 1.8. Each element in a HashMap is called a hash bucket, which contains four items:

  • Hash value
  • key
  • value
  • Next (Next node)

HashMap insert process

The source code for HashMap elements is as follows:

public V put(K key, V value) {
    // Hash the key
    return putVal(hash(key), key, value, false.true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // create table if hash table is empty
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Calculate the array index I to insert based on the hash value of key
    if ((p = tab[i = (n - 1) & hash]) == null)
        // If table[I] is null, insert it directly
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // Override value if key already exists
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // If the key does not exist, check whether it is a red-black tree
        else if (p instanceof TreeNode)
            // Red-black tree inserts key-value pairs directly
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // For a linked list structure, loop ready for insertion
            for (int binCount = 0; ; ++binCount) {
                // The next element is empty
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // Convert to a red-black tree for processing
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Key already exists overwriting value directly
                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;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // Expand the capacity when the capacity exceeds the upper limit
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

To put it simply, the element adding process of HashMap is as follows: first hash the key value to obtain the hash value, and judge whether the element position is empty according to the hash value to the element position. If it is empty, insert it directly; if it is not, judge whether it is a red-black tree; if it is a red-black tree, insert it directly. Otherwise, judge whether the linked list is greater than 8 and the array length is greater than 64. If the two conditions are met, turn the linked list into a red-black tree and insert elements. If either of the two conditions is not met, traverse the linked list for insertion, as shown in the following figure:

Why would you want to turn a linked list into a red-black tree?

A new data structure, red-black trees, was introduced in JDK 1.8 to implement HashMap, primarily for performance reasons. Because the query efficiency will be very low after the linked list exceeds a certain length, its time complexity is O(n), while the time complexity of red-black tree is O(logn), so the introduction of red-black tree can speed up the query efficiency of HashMap in the case of large data volume.

Hash algorithm implementation

HashMap hash algorithm implementation source code is as follows:

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

Key.hashcode () is a Java hashCode() method that returns a hash of type int, and then moves the hashCode 16 bits to the right, exactly half of the 32bit value. The main purpose is to mix the high and low hash values and increase the randomness of the low values, so that the hash algorithm of HashMap is realized.

conclusion

In JDK 1.7, HashMap was implemented using arrays and linked lists. In JDK 1.8, HashMap was implemented using arrays and linked lists or red-black trees, which were introduced for performance reasons. When a HashMap is inserted, it determines whether the current list length is greater than 8 and the array length is greater than 64. If these two conditions are met, the list will be converted to a red-black tree for insertion, otherwise the list will be traversed.

Reference documentation

Tech.meituan.com/2016/06/24/…

Judge right and wrong from yourself, praise to listen to others, gain and loss in the number.

Public account: Java Chinese Community