Overview

HashMap is a K/V key-value pair data structure with fast search and good insertion and deletion performance. It is implemented based on the Map interface of the hash table. It is one of the commonly used Java collections and is non-thread safe.

Data Structure

JDK1.7

The bottom layer uses array (Entry<K, V>) + linked list. Use size & hash to find the array index position. If there is a conflict, use the zipper method to resolve the conflict.
Open hashing: Simply put, it combines a linked list and an array. That is to say, create a linked list array, and each cell in the array is a linked list. If a hash conflict is encountered, the conflicting value is added to the linked list. As shown below

JDK1.8

The underlying initial data structure still uses array + linked list. When the length of a bucket linked list is greater than 8, and the array length is greater than or equal to 64, if so, the red-black tree conversion operation is performed. As shown below

Source code analysis

1.Let’s analyze it first from the source code of JDK1.7. The main core method in this version is the put method. During the put process, the HashMap will be expanded. The default size is 16. The expansion factor is 0.75, that is, when the length of the HashMap reaches 12 The size will be expanded to 2 times the original size. We will explain this method in detail. The source code comments are as follows.
code analysis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public V put(K key, V value) {
    if (key == null)
        //Determine whether the key is null. If key == null, put the key-value pair in table [0] (essence: when key = Null, the hash value = 0, so it is stored in table [0])
        return putForNullKey(value);

    //If key ≠ null, calculate the position (subscript, index) in the stored array table
    //Calculate hash value
    int hash = hash(key);

    //Pass in the hash value and table length to calculate the index
    int i = indexFor(hash, table.length);

    //Traverse the linked list corresponding to table[indexFor] to determine whether the value corresponding to the key already exists
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //If the key already exists (i.e. key-value already exists), replace the original value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    //If the key does not exist, add key-value to the table
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // Determine whether expansion is needed before inserting
    // If the number of elements >= expansion threshold and the corresponding array subscript is not empty
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //Expand capacity by 2 times
        //Distribute elements evenly in the hashmap to reduce hash collisions.
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

2.For JDK1.8 and later, the underlying structure of HashMap has changed to adopt the structure of array + linked list + red-black tree. Why is there such a modification? When there are a large number of elements in the HashMap stored in the same bucket, there is a long linked list under the bucket. At this time, the HashMap is equivalent to a singly linked list. If the singly linked list has n elements, the time complexity of traversal is O(n), completely losing its advantage. Because there will be a process of converting a linked list to a red-black tree and a red-black tree to a linked list,so we need to analyze the putVal and removeNode methods for the JDK1.8 code. The code and some comments are as follows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, i;
    //Determine when the table is null or the length of the tab is 0, that is, the table has not been initialized. At this time, the initialized table is obtained through the resize() method.
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //Here, the value calculated by (n - 1) & hash is used as the subscript i of tab, and p represents tab[i], which is the position of the first node of the linked list. and determine whether p is null
    if ((p = tab[i = (n - 1) & hash]) == null)
        //When p is null, it means that there is no element on tab[i], then new the first Node node, call the newNode method to return the new node and assign it to tab[i]
        tab[i] = newNode(hash, key, value, null);
    else {
        //Next, enter the situation where p is not null. There are three situations: p is a linked list node; p is a red-black tree node; p is a linked list node but the length is the critical length TREEIFY_THRESHOLD. If you insert any element, it will become a red-black tree.
        java.util.HashMap.Node<K,V> e; K k;
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            //The condition for judging the same key in HashMap is that the hash of the key is the same and conforms to the equals method. Here it is judged whether p.key is equal to the inserted key. If equal, the reference of p is assigned to e.
            e = p;
        else if (p instanceof java.util.HashMap.TreeNode)
            //Now let's start with the first case. p is a red-black tree node, so it will definitely still be a red-black tree node after insertion, so we directly force the transformation of p and then call the TreeNode.putTreeVal method, and the returned reference is assigned to e
            e = ((java.util.HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //Next is the case where p is a linked list node, which is the other two types of situations mentioned above: it is still a linked list after insertion/it turns to a red-black tree after insertion. In addition, the upstream transformation code also shows that TreeNode is a subclass of Node.
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //After the insertion is successful, it is necessary to determine whether it needs to be converted to a red-black tree. Because the length of the linked list increases by 1 after the insertion, and binCount does not contain new nodes, the critical threshold must be reduced by 1 when making the judgment.
                        treeifyBin(tab, hash);
                    break;
                }
                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 (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final java.util.HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
                                             boolean matchValue, boolean movable) {
    java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, index;
    // Find the location based on hash
    // If the bucket mapped to the current key is not empty
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
        java.util.HashMap.Node<K,V> node = null, e; K k; V v;
        //If the node on the bucket is the key you are looking for, point the node to the node.
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof java.util.HashMap.TreeNode)
                //Indicates that this node is a node of a red-black tree, and obtains the node that needs to be deleted from the red-black tree.
                node = ((java.util.HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                //Traverse the linked list to obtain the corresponding node
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key ||
                                    (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                (value != null && value.equals(v)))) {
            if (node instanceof java.util.HashMap.TreeNode)
                //Delete nodes by calling the red-black tree method
                ((java.util.HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // Linked list deletion
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

final void removeTreeNode(java.util.HashMap<K,V> map, java.util.HashMap.Node<K,V>[] tab,
                          boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        return;
    int index = (n - 1) & hash;
    java.util.HashMap.TreeNode<K,V> first = (java.util.HashMap.TreeNode<K,V>)tab[index], root = first, rl;
    java.util.HashMap.TreeNode<K,V> succ = (java.util.HashMap.TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        root = root.root();
    if (root == null
            || (movable
            && (root.right == null
            || (rl = root.left) == null
            || rl.left == null))) {
        //Convert red-black tree to linked list
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    java.util.HashMap.TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if (pl != null && pr != null) {
        java.util.HashMap.TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) // find successor
            s = sl;
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        java.util.HashMap.TreeNode<K,V> sr = s.right;
        java.util.HashMap.TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            java.util.HashMap.TreeNode<K,V> sp = s.parent;
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        p.left = null;
        if ((p.right = sr) != null)
            sr.parent = p;
        if ((s.left = pl) != null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        replacement = pl;
    else if (pr != null)
        replacement = pr;
    else
        replacement = p;
    if (replacement != p) {
        java.util.HashMap.TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            (root = replacement).red = false;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }

    java.util.HashMap.TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    if (replacement == p) {  // detach
        java.util.HashMap.TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        moveRootToFront(tab, r);
}

Summarize

1.The default initial length of HashMap’s hash bucket Length is 16, and the default load factor loadFactor is 0.75. The threshold is the number of Node nodes with the maximum amount of data that HashMap can accommodate, threshold=Length*loadFactor

2.When the number of elements stored in HashMap exceeds the threshold, the reseize expansion operation will be performed. The expanded array capacity will be twice the previous one; but expansion is a particularly performance-consuming operation, so when we use HashMap When , you can estimate the size of the Map and specify a rough value during initialization, which can reduce the number of frequent expansions of the Map.

3.The size of the HashMap hash bucket is a power of 2. Each expansion is also 2 times. The purpose is to spread the elements evenly in the hashmap and reduce hash collisions.

4.JDK1.8 introduces red-black tree operation. When the length of the linked list reaches 8 and the number of HashMap is greater than or equal to 64, it will be converted into a red-black tree.Convert the red-black tree to a linked list 1) Delete the node that is the root node of the red-black tree or the left or right node of the root 2) Recalculate the number inside the bucket <= 6 during expansion