“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

1. A HashMap overview

A HashMap is a hash table that stores a key-value mapping. HashMap implements the Map interface, stores data according to the HashCode value of the key, has fast access speed, allows a maximum of one record key to be null, and does not support thread synchronization. The HashMap is unordered, that is, the order of the inserts is not recorded. HashMap extends AbstractMap and implements Map, Cloneable, java.io.Serializable interfaces.Copy the code

Static variables

Static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; Static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; Static final int TREEIFY_THRESHOLD = 8; static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; // The minimum table size of the container can be tree. There should be at least 4*TREEIFY_THRESHOLD to avoid conflicts between resizing and the tree threshold. static final int MIN_TREEIFY_CAPACITY = 64;Copy the code

3. Main methods

3.1 Adding PUT (K Key, V Value)

The put method of HashMap is shown below

Public V put(K key, V value) {// Hash 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; If ((TAB = table) = = null | | (n = TAB. Length) = = 0) / / resize () is not only used to adjust the size, initial configuration is used for n = (TAB = the resize ()). The length; // Determine if there are elements in the hash position, If (p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); if (p = TAB [I] = (hash, key, value, null); else { Node<K,V> e; K k; // The first node key is the same as the insert node key. Determine whether need to replace the if (p.h behind ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; // The first node does not match and is already a tree structure, Else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key, value); 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; } / / if found the key to matching nodes, node, is used to determine whether to replace the if (e.h behind 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) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; If (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the code

In the put method, it uses the hashCode() and equals() methods. When we call the put method by passing the key-value pair, the HashMap uses the key hashCode() and hash algorithm to find the index that stores the key-value pair. If the index is empty, insert it directly into the corresponding array; otherwise, judge whether it is a red-black tree; if it is, insert it into the red-black tree; otherwise, walk through the linked list; if the length is not less than 8, turn the list into a red-black tree, and insert it after the conversion is successful.

3.2 Obtaining the Get (Object Key)

The source code for the HashMap get method is as follows

public V get(Object key) { Node<K,V> e; return (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; if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! //// compares hash values. If the hash values are the same, the keys are the same. If the keys are the same, the object is returned. if (first.hash == hash && // always check first node ((k = first.key) == key || (key ! = null && key.equals(k)))) return first; If ((e = first.next)! If (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreenode (hash, key); Do {/ / cycle to find the next node, until you find the hash and the key of the same node at the same time, if return to node (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }Copy the code

The general process of get method:

Calculate the hash value of the key. 2. Calculate the key subscript I 3 based on the hash value. Check whether table[I] is null; Table [I]=null; 3.2. If table[I]! Key == key; if table[I]. Key == key; Return table[I] to check whether table[I] is a TreeNode node. If table[I] is a TreeNode node, call getTreeNode to find TreeNode, return NULL if table[I] is a TreeNode node. Node iterates through the node list, returns node if found, returns null if not found

3.3 Expanding resize()

The source code for the HashMap resize method is as follows

Final Node<K,V>[] resize() {// Create a new Node and point to the old table Node<K,V>[] oldTab = table; Int oldCap = (oldTab == null) int oldCap = (oldTab == null)? 0 : oldTab.length; // Old capacity threshold int oldThr = threshold; Int newCap, newThr = 0; If (oldCap > 0) {// If (oldCap > 0) { If (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; return oldTab; } // Move oldCap one bit to the left and assign the value to newCap, if newCap is less than the maximum capacity, Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // Double the capacity newThr = oldThr << 1; // double threshold} // If oldThr =0 and oldThr =0, then oldThr =0 and oldThr =0 Else if (oldThr > 0) // Initial capacity was placed in threshold newCap = oldThr; //// at this point oldCap=0, oldThr=0, then there is no initialization, NewCap and newThr assign default values else {// Zero initial threshold using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; Table = newTab; oldTab = newTab; if (oldTab ! = null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) ! = null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order 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); // add index if (loTail! = null) { loTail.next = null; newTab[j] = loHead; } // Add the high index list to the high index index, and 31, equivalent to +16, oldCap if (hiTail! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

HashMap capacity expansion can be divided into three situations:

The first: initialize the HashMap using the default constructor. As you can see from the previous article, HashMap initially returns an empty table with thershold of 0 when initialized. Therefore, the default capacity for the first expansion is DEFAULT_INITIAL_CAPACITY, which is 16. Meanwhile, threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12.

Second: initialize the HashMap with a constructor that specifies the initial capacity. Threshold = current capacity (threshold) * DEFAULT_LOAD_FACTOR

Third: HashMap is not the first expansion. If the HashMap has been expanded, the capacity of each table and threshold will be doubled.