One of the most accessible articles ever written about hashMaps

First look and then like, give yourself a bit of time to think, wechat search [Silent King 2] pay attention to this has the appearance level but pretend to rely on talent mediocre programmer. This article has been collected at GitHub github.com/itwanger, along with interview questions compiled by top companies, and my series of articles.

I’m almost done with the List series, and in a single-threaded environment the most important thing is ArrayList and LinkedList, and in a multi-threaded environment the most important thing is CopyOnWriteArrayList, so if you’re new, you can click on the link and review the List. Next, I will take HashMap to climb the mountain, not six peaks, purely to exercise the body, no, no, purely in order to get closer to HashMap, students pay attention not to lag behind.

As a cliche, a HashMap is a Map that stores key-value pairs, each of which can be mapped exactly to a value that can then be used to quickly find the value.

For a List, if you want to find a value, the time is O(n)O(n)O(n) O(n), and if the List is sorted, the time can be reduced to O(logn)O(log n)O(logn) (binary search), but if it’s a Map, in most cases, The time complexity can be reduced to O(1)O(1)O(1).

Take a look at the features of HashMap:

The keys of a HashMap must be unique and cannot be duplicated.
HashMap keys are allowed to be null, but only one such key can exist; The value can have more than one NULL.
A HashMap is unordered and does not guarantee any particular order of elements.
HashMap is not thread-safe; A multithreaded environment, it is recommended to use ConcurrentHashMap, or using the Collections. SynchronizedMap (hashMap) will hashMap to thread synchronization.
Only the associated key can be used to obtain a value.
A HashMap can only store objects, so the base data type should use its wrapper type, such as int, which should be Integer.
HashMap implements both Cloneable and Serializable interfaces, so it can be copied and serialized.

01. Important fields of the HashMap

A HashMap has five very important fields, so let’s take a look. (JDK version 14)

transient Node<K,V>[] table;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
Copy the code

1) Table is a Node array with a default length of 16. It is initialized when the resize() method is first executed.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
final HashMap.Node<K,V>[] resize() {
    newCap = DEFAULT_INITIAL_CAPACITY;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}
Copy the code

Node is an inner class of HashMap that implements the Map.Entry interface, which is essentially a key-value pair.

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

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

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

    public final int hashCode(a) {... }public final V setValue(V newValue) {... }public final boolean equals(Object o) {... }}Copy the code

2) Size is the actual number of key-value pairs stored in the HashMap, which is different from the length of the table.

To illustrate this, let’s look at the following code:

HashMap<String,Integer> map = new HashMap<>();
map.put("1".1);
Copy the code

Declare a HashMap, then put a key-value pair. Enter the put() method with a breakpoint, wait until the end of the method to add a watch (table.length), and observe the following results.

That is, the array size is 16, but the HashMap size is 1.

3) modCount is mainly used to record a HashMap the number of actual operation, so that the iterator to perform the remove () when operating quickly throw ConcurrentModificationException, Because HashMap, like ArrayList, is fail-fast.

More information about ConcurrentModificationException, please click on the link below to view what 03 section.

4) Threshold is used to determine the maximum number of key-value pairs that a HashMap can hold. Its value is equal to the array size * load factor. The default is 12 (16 * 0.75), when the resize() method is first executed.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75 f;

final HashMap.Node<K,V>[] resize() {
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
Copy the code

The default value of 0.75 is a balancing choice for space and time efficiency and is generally not recommended to change, as I have never changed this value for an experienced rookie like me who has been working for over a decade.

02. Hash algorithm of HashMap

What is the meaning of this Hash? An algorithm maps arbitrary length of data to a field of fixed length (hash value).

More intuitively, it is to mix a string of data Wang and output another fixed-length data ER — as the characteristics of data Wang. We usually use a bunch of fingerprints to map a person. Don’t underestimate a fingerprint-size one. It’s hard to find a second one in your area (good hashing algorithm, right?). .

It is extremely unlikely that any two different blocks of data will have the same hash value, that is, for a given block of data, it is extremely difficult to find a block with the same hash value. Furthermore, if you change even one bit of a block of data, the Hash value can change dramatically — that’s why Hash exists!

As you already know, the underlying data structure of a HashMap is an array, and it is crucial to locate the subscript of the array, whether adding, deleting, or finding key-value pairs.

How does a HashMap locate subscripts?

Step 1, the hash() method:

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

Step 2, a line from the putVal() method:

n = (tab = resize()).length;
i = (n - 1) & hash;
Copy the code

To make it easier to understand, I’ve combined these two steps together:

String [] keys = {"Heavy"."Silent"."The king"."二"};
for (String k : keys) {
    int hasCode = k.hashCode();
    int right = hasCode >>> 16;
    int hash = hasCode ^ right;
    int i = (16 - 1) & hash;
    System.out.println(hash + "Subscript: + i);
}
Copy the code

1) k.hashcode () is used to calculate the hashCode value of the key. For any given object, the hash() method always evaluates the same hash code as long as its hashCode() returns the same value.

To be able to do this requires that the object used as the key be immutable, and that the hashCode() method be clever enough to return as many hashCode values as possible, such as the String class.

public int hashCode(a) {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}
Copy the code

2) >>> is the unsigned right shift operator, the high position of the complement 0, move as many as how many zeros fill.

1^0 = 1, 1^1 = 0, 0^1 = 1, 0^0 = 0.

4) &is the bitwise and operator. The operation rule is to convert the numbers on both sides to binary bits and then calculate the final value. The operation rule is that (if two are true, it is true) 1&1=1, 1&0=0, 0&1=0, 0&0=0.

The >>>, ^, & operators, which involve binary, are not covered in depth in this article. Interested students can do their own research.

If four strings are “sink “,” silence “,” king “, and” two “, their values and subscripts are computed using the hash() method as follows:

27785 index: 9 40664 index: 8 29579 index: 11 20108 index: 12Copy the code

It should be said that this hash algorithm is very clever, especially the second step.

The length of the underlying array of a HashMap is always 2 to the power of n. When length is always 2 to the power of n, (length-1) & hash is equivalent to modulo the length of the array, i.e. hash%length, but & is more efficient than %.

03, HashMap`put()`methods

We understand the hash algorithm of the HashMap, but there seems to be a bit of doubt. What if the calculated hash value conflicts?

For example, the hash value of “sink X” is 27785, and its subscript is 9, placed at 9 in the array; After a while, another “sink Y” hash value is 27785, the subscript is 9, also need to put in the position of 9, what should I do?

To simulate this situation, let’s create a new custom key class.

public class Key {
    private final String value;

    public Key(String value) {
        this.value = value;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null|| getClass() ! = o.getClass())return false;
        Key key = (Key) o;
        return value.equals(key.value);
    }

    @Override
    public int hashCode(a) {
        if (value.startsWith("Heavy")) {
            return "Heavy".hashCode();
        }
        returnvalue.hashCode(); }}Copy the code

In the hashCode() method, a judgment is added to return the hashCode value for sink if the key begins with sink, which means that sink X and sink Y will appear on the same index in the array.

HashMap<Key,String> map = new HashMap<>();
map.put(new Key(Sink "X"),"Silent King 2 X");
map.put(new Key(Sink "Y"),"Silent King TWO Y");
Copy the code

Put () = put();

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

The put() method first calls the hash() method to compute the hash value of the key, and then calls the internal putVal() method:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    // if table is null, call resize to create array with default size
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Calculate the subscript, if there is no value, then fill
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        HashMap.Node<K,V> e; K k;
        // if the key already exists and the hash value is the same, overwrite it directly
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // 4, red black tree processing
        else if (p instanceof HashMap.TreeNode)
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // add a linked list to handle hash conflicts
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // If the list length is greater than 8, it is converted to red-black tree processing
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Overwrite if the key already exists and the hash value is the same
                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;
    // If the capacity exceeds the limit, expand the capacity
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

I’ve added some comments to the code, so make sure you take a moment to look at them.

If the hashes conflict, execute the corresponding else statement (②), first check whether the key is equal, if so, directly overwrite; Otherwise, perform (4) to perform red-black tree processing. If not, perform ⑤ to assign the next of the previous Node to the new Node.

That is, if hashes collide, the list will be added to the same place in the array, and if the list is larger than 8, it will be converted to a red-black tree for processing.

Java 8 adds a red-black tree (O(logn)O(log n)O(logn) O) to the list.

If the key is null, where is the key-value pair stored?

04, HashMap`get()`methods

The get() method is easy to understand once you understand the hash algorithm and the put() method of a HashMap.

public V get(Object key) {
    HashMap.Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code

First compute the hash value of the key, and when the hash value is determined, the subscript position of the key-value pair in the array is determined, and then call getNode() :

final HashMap.Node<K,V> getNode(int hash, Object key) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
    if((tab = table) ! =null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) ! =null) {
        if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        if((e = first.next) ! =null) {
            if (first instanceof HashMap.TreeNode)
                return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    return e;
            } while((e = e.next) ! =null); }}return null;
}
Copy the code

First = TAB [(n-1) &hash]; hash = TAB [(n-1) &hash]; hash = TAB [(n-1) &hash]; If the hashes of the keys conflict, we determine if it’s a red-black tree, and if it’s not, we iterate through the list.

05, finally

To be honest, before writing this article, I did not have such a deep understanding of HashMap, but after writing this article, I dare to pat my chest and say: “HashMap I really master, students who ask me again in the future, can throw this article to him.”

Although the mountain climb is very tired, but it is really a great harvest, value!

I am the Silent King 2, a programmer with good looks who pretends to be inferior to his talent. Attention can improve learning efficiency, don’t forget three even ah, like, collect, message, I don’t pick, Ollie to 🌹.

Note: If there are any problems with the article, please kindly correct them.

If you feel that the article is helpful to you, welcome to wechat search “Silent King two” for the first time to read, reply to the keyword “xiaobai” can be free to get my liver 40,000 + words “Java Xiaobai from the entry to wunky” 2.0 version; This article has been included at GitHub github.com/itwanger.

One of the most accessible articles ever written about hashMaps

01. Important fields of the HashMap

02. Hash algorithm of HashMap

03, HashMapput()methods

04, HashMapget()methods

05, finally

Related Posts

How to select MySQL index and index optimization combat

Spring Boot 16, hot deployment only know devTools? Doesn’t JRebel smell good?

Deep understanding of the JVM – actual JVM tools (under) | August more challenges

03, HashMap`put()`methods

04, HashMap`get()`methods