HashMap

What is a HashMap

In java1.8, a HashMap is a data structure consisting of an array, a linked list, and a red-black tree.

A HashMap stores data based on the hashCode value of the key, and in most cases can be directly located to reverse its value, thus providing fast access, but the convenience order is uncertain. A HashMap allows at most one record to have a null key and multiple records to have a NULL value. HashMap is not thread-safe, that is, multiple threads can write HashMap at any time, which may lead to data inconsistency. If thread safety is required, the synchronized method of Collecionts can be used to make HashMap thread-safe. Or use ConcurrentHashMap.

Hash method details

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

If the key is not null, the hashCode method of the Object base class will generate the hash value and move it 16 bits to the right

Note: When the results of the hash algorithm are more dispersed and uniform, the probability of hash collision is smaller and the access efficiency is higher

What if I run into a hash conflict?

There are two ways to resolve hash conflicts

Open addressing

Open addressing method: also known as open addressing method, when the hash collision occurs, starting from the element of the collision, according to a certain order, from the hash table to find a free cell, and then put the conflicting elements into the cell. This free cell is also called an open cell or a blank cell. If a blank cell is detected, that is, there is no keyword in the table to be searched, the search fails

Chain address method

Chain address method: array and linked list combination, each array element is a linked list structure, when the key is hash, the array subscript, put the array on the linked list of the corresponding subscript element.

Triggering conditions for capacity expansion

The triggering condition of capacity expansion is controlled by a parameter called threshold, which is calculated by the formula of array length threshold = Capacity x loafFactor.

Capacity: Default is 16 length, growth is old array length *2.

Liability factor: an important condition that dictates when to expand capacity.

Hashmap expansion mechanism?

Through source code interpretation

Final Node<K,V>[] resize() {// Get a reference to the old array Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; If (oldCap > 0) {// If (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; Return oldTab; } // Do not exceed the maximum value, Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1;  Double threshold} else if (oldThr > 0) newCap = oldThr; Else {// Initialize the default value newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // New threshold ==0 resize if (newThr ==0) {float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // set threshold = newThr; @suppressWarnings ({"rawtypes","unchecked"}) // Create a new array Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab ! For (int j = 0; j < oldCap; ++j) { Node<K,V> e; If ((e = oldTab[j])! OldTab [j] = null; NewTab [e.hash & (newcap-1)] = e; newTab[e.hash & (newcap-1)] = e; newTab[e.hash & (newcap-1)] = e; Else if (e instanceof TreeNode) // Assign a value to the red-black tree ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); Else {// List > 8 < 1 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; If ((e.hash & oldCap) == 0) {if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); // Put the index into the bucket if (loTail! = null) { loTail.next = null; newTab[j] = loHead; } // old index + oldCap into bucket if (hiTail! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

It is observed that we are using an extension of two powers, so that the element is either in its original position or moved by two powers from its original position.

Why is the threshold for list to red black tree 8? Why do lists become red black trees?

Jdk1.7 is made up of arrays and linked lists.

First of all, red-black tree advantages: increase, delete, modify and check efficiency. High linked list data volume will improve the row performance if it is operated by red-black tree.

However, linked list conversion to red-black tree is a time-consuming operation that requires the traversal of linked list and insertion of red-black tree. It is reasonable that the performance after conversion should be greater than the cost. The threshold setting of 8 should be the value obtained by the development project after balancing the time and space complexity through strict system testing.

The process of adding elements to a HashMap

Public V put(K key, V value) {// Hash return putVal(Hash (key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; / / 1. The TAB is empty, create the if ((TAB = table) = = null | | (n = TAB. Length) = = 0) n = (TAB = the resize ()). The length; If ((p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); else { Node<K,V> e; K k; / / 3. The key nodes exist directly cover the if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; Else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key, value); Else {//5. List for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); If (binCount >= treeIFy_threshthreshold -1) // -1 for 1st treeifyBin(TAB, hash); break; } / / 5.2 list already exists and the hash value and the key values are equal, first for reference, used to replace values behind the if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! OnlyIfAbsent | | oldValue = = null) / / replace the original value unified e.v alue = value; afterNodeAccess(e); // return oldValue; } } ++modCount; If (++size > threshold) resize(); // Step 6. afterNodeInsertion(evict); return null; }Copy the code

Why is hashMap designed this way?

Jdk1.8 introduces red black tree, an enterprise-level data structure that optimizes the query and modification efficiency of red black tree, greatly improving the efficiency.