Introduction of a HashMap

  • A HashMap is a typical key-vlaue hash table that accesses records by mapping the hash value of a key to a location in the array

  • As shown in the figure, there are two types of storage in the HashMap array: linked list nodes and red-black tree nodes

  • Linked lists are used to handle hash collisions caused by different nodes that map to the same location in the array

  • Red-black trees are used to avoid long lists that violate the speed of hash table O(1) lookup

A HashMap properties

  • Node: data structure for storing key-values

  • The Node < K, V > [] : a hash table

  • LoadFactor: loadFactor, which can be passed in the constructor to adjust the true capacity of the hash table

  • Threshold: Capacity expansion threshold, calculated by array length x load factor. The role of threshold in the constructor is written later

	//table array default size static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //table Max length static final int MAXIMUM_CAPACITY = 1 << 30; // Load factor (default, can also be set by constructor) 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; // Tree threshold: The number of hash table elements must reach 64. static final int MIN_TREEIFY_CAPACITY = 64; //key-vlaue static class Node implements map. Entry {// Hash value: used to determine where the Node is in the array final int hash; final K key; V value; //next Node next; Node(int hash, K key, V value, Node 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; } 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 instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }} // A transient Node storing key-value nodes [] table; // Number of key-value nodes in current table transient int size; // Transient int modCount used for FAIL fast; // Capacity expansion threshold: triggering capacity expansion condition int threshold; // loadFactor: calculate threshold final float loadFactor;Copy the code

HashMap constructor

  • The parameter initialCapacity: will be calculated and assigned to threshold. It will be treated as the array length during initialization and threshold will be recalculated

  • The loadFactor parameter is assigned to the loadFactor to calculate the expansion threshold

  • Instead of initializing the Node array, the constructor waits for the PUT operation and initializes it during expansion

	Constructor public HashMap(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); // Return a value greater than or equal to the first power of 2 of cap. } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // default loadFactor :0.75 // default table length :16 public HashMap() {this.loadfactor = DEFAULT_LOAD_FACTOR; } public HashMap(Map m) {this.loadfactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }Copy the code

  • Hash (): Computs the hash value using the key, encapsulates it in Node, and determines the array position using the mod, which is optimized to the and because the array length is always a power of 2, for example, 17% 16 = 17&(16-1) = 1

  • TableSizeFor (): Calculates a number to the power of 2, which initializes the length of the array

	Static final int hash(Object key) {int h; static final int hash(Object key) {int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); Static final int tableSizeFor(int cap) {int n = cap - 1; int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }Copy the code

One minor detail: When the key is null, the hash value is 0

Parsing the get ()

  • The get() method is used to look up the key in the hash table and determine where the key is in the array based on the hash value of the key and the length of the array minus one (essentially taking the remainder)

  • After finding the array location corresponding to the key, the current location is searched according to whether the linked list or red-black tree

	Public V get(Object key) {Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) {// TAB: current hash first: current hash first n: array length e: temporary hash k: temporary hash Node[] TAB; Node first, e; int n; K k; If ((TAB = table)! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) {// case 1: The first node key as the if (first) and to find the key to the 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)first).getTreenode (hash, key); / / case 3: chain table lookup do {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

Parsing the put ()

  • The put() operation is used to add a node to the hash table and locate the array based on the hash value of the node’s key

  • After finding the array location corresponding to the key, add nodes based on the current location

	Public V put(K key, V value) {return putVal(hash(key), key, value, false, true); } //onlyIfAbsent false: When the same key is present, the put operation replaces the old value. Final V putVal(int hash, K key, V value, Boolean onlyIfAbsent, Boolean evict) {// TAB: reference to the current hash table p: element of the current hash table n: length of the current hash table I: index of the current hash table Node[] TAB; // TAB: reference to the current hash table p: element of the current hash table n: length of the current hash table I: index of the current hash table Node[] TAB; Node p; int n, i; / / lazy initialization, the first putVal will initialize the hash table if ((TAB = table) = = null | | (n = TAB. Length) = = 0) n = (TAB = the resize ()). The length; If ((p = TAB [I = (n-1) & hash]) == null) // Insert TAB [I] = newNode(hash, key, value, null); Else {//e: temporary element k: key Node e of the temporary element; K k; / / case 2: the key value of the corresponding to the location of the equal and insert the key, says the subsequent need to assign a value covering 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)p).puttreeval (this, TAB, hash, key, value); Else {for (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {p.ext = newNode(hash, key, value, null); If (binCount >= treeify_threshold-1) // -1 for 1st // treeifyBin(TAB, hash); break; } / / iteration to an element of the key, and insert the key, the same said need assignment covering 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) e.value = value; afterNodeAccess(e); return oldValue; ++modCount; If (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the code

Parsing the resize ()

  • When the first PUT () operation is triggered, the expansion operation initializes the Node array. In the constructor, threshold becomes the length of the array, and the actual expansion threshold is calculated and assigned to threshold

  • When the PUT () operation ends, the capacity expansion operation is triggered if the number of nodes exceeds the capacity expansion threshold

	// Final Node[] resize() {// Node[] oldTab = table; Int oldCap = (oldTab == null)? 0 : oldTab.length; // Capacity expansion threshold before capacity expansion int oldThr = threshold; Int newCap, newThr = 0; If (oldCap > 0) {if (oldCap > 0) {if (oldCap > 0) { Set the capacity expansion threshold to the maximum value int if (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; return oldTab; } // Condition 1: the new length is less than the maximum value Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // Double the new threshold newThr = oldThr << 1; // double threshold} //oldCap = 0: hash table is not initialized // case 1: new HashMap(initCap,loadFactor) // case 2: New HashMap(initCap) else if (oldThr > 0) // Initial capacity was placed in threshold = oldThr; //new Hashmap() else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); If (newThr == 0) {float ft = (float)newCap if (newThr == 0) {float ft = (float)newCap 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"}) // Create new array Node[] newTab = (Node[])new Node[newCap]; table = newTab; // The old array is already initialized if (oldTab! = null) {, for (int j = 0; j < oldCap; ++j) {// Node e; If ((e = oldTab[j])! OldTab [j] = null; NewTab [e.hash & (newcap-1)] = e; if (e.ext == null) newTab[e.hash & (newcap-1)] = e; Else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); LoHead = null, loTail = null; // Preserve order = // preserve order = // Node hiHead = null, hiTail = null; Node 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); // Place the list if (loTail! = null) { loTail.next = null; newTab[j] = loHead; } // Place the linked list if (hiTail! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

Parsing the remove ()

  • The remove() method is used to remove a node and locate the array based on the hash value of the node’s key

  • After finding the array location corresponding to the key, the current location is searched and removed based on whether the current location is a linked list or a red-black tree

	RemoveNode public V remove(Object key) {Node e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node removeNode(int hash, Object key, Object value, boolean matchValue, Boolean movable) {// TAB: current hash table p: current Node n: array length index: key corresponding hash table index Node[] TAB; Node p; int n, index; If ((TAB = table)! = null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! = null) {//node: query result e: temporary node k: key v: value node node = null, e; K k; V v; / / condition 1: find the first element is to delete the elements of the if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) node = p; else if ((e = p.next) ! = null) {// case 2: red black tree if (p instanceof TreeNode) node = ((TreeNode)p).getTreenode (hash, key); The else {/ / situation 3: list the do {the if (e.h ash = = hash && ((k = e.k ey) = = 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)))) {// case 1: Red black tree (upper case 2) if (node instanceof TreeNode) ((TreeNode)node).removeTreenode (this, TAB, movable); Else if (node == p) // Place the next element of this node in the array TAB [index] = node.next; Elseif p = next; elseif p = next; elseif p = next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }Copy the code