About the author: Wang Lei, former 360 technology expert. This text is from: Hook Education
Java Source Code Analysis lecture 34

Hello, I’m Wang Lei, your Java interview teacher. Welcome to the content of class 02: “What is the underlying implementation principle of HashMap? What has it been optimized for?”

HashMap is one of the most commonly used types and one of the most frequently asked interview questions. This is because there are a lot of HashMap knowledge points and it is part of Java basics, so it is often asked in interviews.

The interview question for this class is, how is the underlying implementation of HashMap? What optimizations have been made in JDK 1.8?

The typical answer

In JDK 1.7, HashMap is composed of an array plus a linked list. After JDK 1.8, we added a red-black tree structure. When the list is larger than 8, the list structure will be converted into a red-black tree structure, as shown in the following figure:

The elements of the array are called hash buckets and are defined as follows:

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


    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }


    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }


    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }


    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }


    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if(o instanceof Map.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    Copy the code

You can see that each hash bucket contains four fields: Hash, key, value, and next, where next represents the next node in the list.

The reason why JDK 1.8 adds red-black trees is that if the list is too long, the performance of HashMap will be seriously affected. Red-black trees can be used to quickly add, delete, modify, and query the list, which can effectively solve the problem of slow operation when the list is too long.

This text is selected from: Pull hook education “Java source code analysis 34”

The test analysis

The above Outlines the structure of a HashMap, but interviewers may want to know more than that. Here are a few more HashMap related interview questions:

  • What are the optimizations for JDK 1.8 HashMap expansion?
  • Why is the loading factor 0.75?
  • How does a HashMap find and confirm elements when there are hash conflicts?
  • What are the important methods in the HashMap source? Intellectual development

1. Source code analysis of HashMap

Note: This series of courses, without special explanation, will use the current mainstream JDK version 1.8 as an example for source code analysis.

The HashMap source code contains the following attributes:

Static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; Static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824 // The default loading factor (expansion factor) is static finalfloatDEFAULT_LOAD_FACTOR = 0.75 f; Static final int TREEIFY_THRESHOLD = 8; static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; static final int UNTREEIFY_THRESHOLD = 6; Static final int MIN_TREEIFY_CAPACITY =Copy the code

What is a load factor? Why is the loading factor 0.75?

If the load factor is 0.5 and the initial capacity of the HashMap is 16, then the HashMap will be expanded when there are 16*0.5=8 elements in the HashMap.

So why is the loading factor 0.75 and not 0.5 or 1.0?

This is a trade-off between capacity and performance:

  • When the load factor is larger, the threshold of the expansion was improved and expansion of frequency is lower, the amount of space will be small, but the chance of Hash conflict will increase, so we need more complex data structure to store the elements, this will increase to the operation of the element of time, efficiency will also reduce;
  • When the loading factor value is small, the threshold for expansion is low, so more space will be occupied. In this case, the storage of elements is sparse, and the possibility of hash conflict is low, so the operation performance is high.

Therefore, an average of 0.75 from 0.5 to 1.0 was taken as the loading factor.

There are three important methods in the HashMap source code: query, add, and data expansion.

First look at the query source:

public V get(Object key) { Node<K,V> e; // Hash the keyreturn (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; // Non-null judgmentif((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) &hash])! = null) {// Determine if the first element is the element to be queriedif (first.hash == hash&& // always check first node ((k = first.key) == key || (key ! = null && key.equals(k))))returnfirst; // The next node is not nullif((e = first.next) ! = null) {// If the first node is a tree, use getTreeNode to get the corresponding data directlyif (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do{// non-tree structure, loop node judgment //hashEqual and with the same key, this object is returnedif (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}Copy the code

As can be seen from the above source code, when hashing conflicts, we need to determine whether the key value is equal to determine whether the element is the one we want.

OK, so that’s it, and next time I’m going to share “What are the states of threads? How does it work?” Remember to come to class on time.

This text is selected from: Pull hook education “Java source code analysis 34”

Copyright notice: The copyright of this article belongs to Pull hook education and the columnist. Any media, website or individual shall not be reproduced, linked, reposted or otherwise copied and published/published without the authorization of this agreement, the offender shall be corrected.