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

HashMap source code parsing

HashMap is mainly used to store key-value pairs. It is implemented based on hash table Map interface. It is one of the common Java collections and is non-thread-safe.

A HashMap can store null keys and values, but only one key can be null and multiple values can be NULL.

HashMap hash method source

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

  • Ampersand: all 1 is 1, otherwise 0

  • | operation: as long as there is a 1 is 1

  • ^ (xor) : different is 1, same is 0

The HashMap uses the hash of the key’s hashCode to get the hash value, and then uses (n-1) &hash to determine where the current element is stored

When the list length is greater than the threshold (8 by default), the treeifyBin() method is first called. This method determines whether to convert to a red-black tree based on the HashMap array. The transform red-black tree operation is performed only if the array length is greater than or equal to 64 to reduce the search time. Otherwise, you just perform the resize() method to expand the array.

Basic properties of a HashMap

A HashMap is essentially an array of Nodes

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {// private static Final Long serialVersionUID = 362498820763181265L; Static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; Static final int MAXIMUM_CAPACITY = 1 << 30; // Default fill factor 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; static final int UNTREEIFY_THRESHOLD = 6; Static final int MIN_TREEIFY_CAPACITY = 64; static final int MIN_TREEIFY_CAPACITY = 64; // An array that stores elements, always a power of 2 the most important one ！！！！！！ transient Node<k,v>[] table; // Transient Set<map.entry<k,v>> entrySet; // The number of elements to store. Note that this does not equal the length of the array. transient int size; // Map count transient int modCount; // Threshold When the actual size (capacity x filling factor) exceeds the threshold, the system expands the capacity. Int threshold; // loadFactor final float loadFactor; }Copy the code

  • LoadFactor loadFactor

    The loadFactor controls the density of data stored in the array. The closer the loadFactor is to 1, the more entries stored in the array will be, and the denser it will be. In other words, the length of the linked list will increase. The fewer entries there are in the array, the sparser it is.

    Too large a loadFactor will result in inefficient element search, while too small will result in low array utilization and scattered data storage. The default value of loadFactor is 0.75F, which is officially a good threshold.

    Given a default capacity of 16 with a load factor of 0.75. When Map is used, data is continuously stored in it. When the amount of data reaches 16 x 0.75 = 12, the current capacity of 16 needs to be expanded. This process involves rehash and data replication, which consumes high performance.

  • threshold

    Threshold = capacity * loadFactor; if Size>=threshold, then we need to consider whether the array needs to be amplified.

  • The Node Node class

Map.Entry<K,V> static class Node<K,V> implements map. Entry<K,V> {final int hash; // Hash value, which is used to compare elements ina hashmap with other elements' hash values / / 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; } // Rewrite the hashCode() method 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 == this) return true; If (o instanceof map.entry) {// If the key is the same, the value is the same, which is the same map.entry <? ,? > e = (Map.Entry<? ,? >)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}Copy the code
  • The Tree node class
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; / / parent TreeNode < K, V > left; / / left TreeNode < K, V > right; / / right TreeNode < K, V > prev. // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next); } final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;) { if ((p = r.parent) == null) return r; r = p; }Copy the code

Constructor of HashMap

// Default constructor. public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted} // Constructor that contains another "Map" public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); Public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }Copy the code

PutMapEntries place key-value pairs from the map parameter into the table in the new map

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); If (s > 0) {if (table == null) {// pre-size // not initialized, Float ft = (float)s/loadFactor) + 1.0f; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // If the calculated T is greater than the threshold, initialize the threshold. If (t > threshold) threshold = tableSizeFor(t); Else if (s > threshold) resize(); if (s > threshold) resize(); // Add all elements in m to HashMap for (map.entry <? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); }}}Copy the code

The HashMapPutmethods

public V put(K key, V value) { 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; / / table uninitialized or length is 0, expansion the if ((TAB = table) = = null | | (n = TAB. Length) = = 0) / / there's a resize used to initialize, Then assign the length to n n = (TAB = resize()).length; // If the bucket is empty, If ((p = TAB [I = (n-1) & hash]) == null) TAB [I] = new Node(hash, key, value, null); / / if the barrels of already existing elements in the else {/ / * * * * * * * * * * * * * * * * * * the following is the barrel has a Node of * * * * * * * * * * * * * * * * * * * * * * * e / / here, is used to find the Node of the collision of the Node < K, V > e;  K k; // If the hash value of the first element in the bucket is the same as the hash(key) value passed in // and the key is the same as the address of the passed key or equals if (p.hash == hash && (k =) p.key) == key || (key ! = null && key.equals(k)))) // assign the first element to e, override e = p directly; // Hash values are not equal, that is, keys are not equal; Else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key, value); For (int binCount = 0; ; If ((e = p.ext) == null) {// insert newNode p.ext = newNode(hash, key, value, null); // When the number of nodes reaches the threshold (8 by default), execute the treeifyBin method, which determines whether to convert to a red-black tree based on the HashMap array. // Only if the array length is greater than or equal to 64, the conversion red-black tree operation is performed to reduce the search time. // Otherwise, just expand the array. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); // break the loop; } / / judgment chain the key value node in the table and insert the elements of the key values are equal if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) // equal, break loop; P = e; p = e; p = e; } // If (e! = null) {// record e value V oldValue = e.value; // onlyIfAbsent Is false or null if (! OnlyIfAbsent | | oldValue = = null) / / replace the old with the new value value e.v alue = value; AfterNodeAccess (e); // return oldValue; } / / * * * * * * * * * * * * * * * * * * the above are all barrels have Node of * * * * * * * * * * * * * * * * * * * * * * *} / / structural modification + + modCount; If (++size > threshold) resize(); // afterNodeInsertion insertion (evict); return null; }Copy the code

It is divided into the following steps

1. Check whether the Node array is empty, if so, call resize() to initialize it

2. Use hash & (n-1) to calculate the store location

3. If there’s nothing there, just put it in

4. If there is something at that location, check whether the hash value of the node is equal to the hash(key) passed to the put method and whether the key is equal to the address or equals of the passed key. If so, the hash value is equal. And the key is exactly the same, overwriting the original value

5. If a hash collision occurs and the keys are different, the node is probably already a linked list or red-black tree

6. For red-black trees, call putTreeVal to add a Node to the tree

If the hash value of a key is equal to the hash value passed in, and the hash value of the key is equal to or equals to the hash value passed in, then there is no key in the linked list. Insert directly into the tail node and determine if it is greater than TREEIFY_THRESHOLD. If so, convert to a red-black tree, otherwise replace the value of the node

8. If the array size exceeds the threshold, call resize() to expand the array

The HashMapGetmethods

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]) ! = null) {/ / if the node, which is the first node of the hash value, and the key in the same address and equals the if (first. The hash = = hash && ((k = first. Key) = = key | | (key! = null && key.equals(k)))) return first; // If ((e = first.next)! = null) {// Get if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreenode (hash, key); / / get the do in the linked list {the if (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

1. Check whether the Map Node array is empty. If so, return NULL

If the hash value is the same as that of the key, and the address of the key and equals are the same, then return the value directly

If it is the root of a red-black tree, call getTreeNode to get it. If it is a linked list, iterate over the nodes and return nodes with identical hash values and keys. If it cannot find any nodes, return NULL

The HashMapresize()methods

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // threshold Threshold If the actual size (capacity x padding factor) exceeds the threshold, the system will expand the capacity. Int oldThr = threshold; int newCap, newThr = 0; If (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; if (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; return oldTab; } // If the original size is twice smaller than the maximum capacity and the original capacity is larger than the default capacity, Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; Else {// newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // Calculate the new resize upper limit 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; if (oldTab ! = null) {// Move each bucket to the new buckets for (int j = 0; j < oldCap; ++j) { Node<K,V> e; If ((e = oldTab[j])! = null) {// Clear oldTab[j] = null; NewTab [e.hash & (newcap-1)] = e; // 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 { 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; } oldCap else {if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); // Put the index in the bucket if (loTail! = null) { loTail.next = null; newTab[j] = loHead; } // add oldCap to bucket if (hiTail! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

Reference: snailclimb. Gitee. IO/javaguide / #…