Reference: juejin.cn/post/684490…
Well, this should count as Java source
The point to summarize
1. The internal data elements of HashMap (map. Entry<key,value>) are stored in the form of array + linked list + red-black tree (newly added in JDK8), and the storage order is out of order, as shown in Figure 1. The number of elements in each node of the array is not necessarily the same. Implement Map<K,V>, Cloneable, Serializabl interface;
2. The so-called “hash collision”, from the perspective of figure 1 storage, means that multiple elements are mounted at the same location on the array, for example, index 0 has two hash collisions, index 3 has one hash collision;
3. The formula for storing the index of an element is (n-1)&hash, where N is the current hash capacity of the table and hash is the element key obtained by a specific hash operation. The calculation process can be seen from Figure 2.
4.HashMap is non-thread-safe, which may lead to data inconsistency in the case of multi-thread access; Allow null key and null value;
5. In JDK8(i.e. JDK1.8), when the length of the linked list reaches 8, it will be converted into a red-black tree to improve query and insert efficiency;
6. When the conditions for expansion are met, the hash table is doubled for expansion. However, each expansion requires recalculation of the position of each element.
7. The load factor can be modified and can be greater than 1, but it is recommended not to change it lightly unless the situation is very special.
8. Red-black tree is introduced in JDK8, and part of the calculation is replaced by bit operation instead of the original % operation, which improves efficiency
Source code analysis
The constructor
HashMap provides four constructors:
HashMap<String,String> map=new HashMap<String,String>(); Map2 =new HashMap<String,String>(16); Map3 =new HashMap<String,String>(16,0.5f); Map4 =new HashMap<String,String>(new HashMap<String,String>())); The following is the source code constructor:Copy the code/** /** The number of elements in a HashMap. Hashmap.size () returns The size * The number of key-value mappings contained in The listinthis map. */ transient int size; /** Default initial hash table size is 16, The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4. 2^30=1073741824 * The maximum capacity, usedifa higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; The load factor used when none specified is specified. /** The load factor used when none specified is specifiedin constructor.
*/
static final floatDEFAULT_LOAD_FACTOR = 0.75 f; /** The actual load factor. If not specified, DEFAULT_LOAD_FACTOR 0.75f * The load factorfor the hash table.
*
* @serial
*/
final floatloadFactor; /* ** important! Important! Important! ** *** Threshold of the number of elements in the hash table. When the number of elements exceeds this threshold, the hash table will automatically expand resize(); ** * Threshold calculation method = Capacity * load factor: hash table capacity* Load factor Capacity * The next size value atwhich to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, ifthe table array has not been allocated, this // field holds the initial array capacity, or zero signifying // DEFAULT_INITIAL_CAPACITY.) int threshold; /** ** important! Important! Important! ** hash bucket ** hash bucket ** hash bucket ** hash bucket ** hash bucket ** hash bucket ** * Initialize when first used, and resize() when needed; * The size is always 2^n or 0; * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zeroinsome operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K,V>[] table; Construction method 1: * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentExceptionif the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, floatLoadFactor) {// The initial capacity cannot be less than 0if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if(initialCapacity > MAXIMUM_CAPACITY) // the initialCapacity cannot be greater than 2^30.if(loadFactor < = 0 | | Float. IsNaN (loadFactor)) / / load factor must be greater than zero effective digital throw new IllegalArgumentException ("Illegal load factor: "+ loadFactor); // This. LoadFactor = loadFactor; // set the threshold based on the initialCapacity. This. threshold = tableSizeFor(initialCapacity); }} /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentExceptionif*/ public HashMap(int initialCapacity) {public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }} /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ publicHashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted} /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is Created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappingsin the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException ifthe specified map is null */ public HashMap(Map<? extends K, ? Extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m,false);
}
Copy the codeData in HashMap is actually stored in the form of linked list, namely transient Node<K,V>[] table. For this, we first check and analyze the structure of Node
The Node linked list class implements the map. Entry<K,V> element interface for storing HashMap content
/** *
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; / / nodehashFinal value K key; Map.put(key,value) key V value; Put (key,value) value Node<K,V> next; // The next element that the list points to is 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; } // For each nodehashThe value is the keyhashCode and the valuehashCode xor obtained. public final inthashCode() {
returnObjects.hashCode(key) ^ Objects.hashCode(value); } // Set value and return old value public final VsetValue(V newValue) {
V oldValue = value;
value = newValue;
returnoldValue; } public final Boolean equals(Object o) {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; }}Copy the codeConstructor 1 :HashMap(int initialCapacity, float loadFactor) This. threshold = tableSizeFor(initialCapacity); TableSizeFor (initialCapacity) method:Copy the codeTableSizeFor Function that obtains the hash bucket threshold based on the expected capacity
/** * bit operations on this side will end up with a >= expected capacitycapThe nearest value of 2 to the n; * Returns a power of two size. * Returns a power of two sizefor the given target capacity.
*/
static final int tableSizeFor(int cap) {// After the following or and displacement operations, n ends up with 1 bits. 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 codePublic HashMap(Map<? extends K, ? Extends V> m) calls putMapEntries(m, false); To perform an initial assignment to the hash table
PutMapEntries function, initial assignment via Map
/** * implements map. putAll and Map constructor 4, where the evict parameter is passed in the constructor asfalse, other places aretrue
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true(relayed to method afterNodeInsertion). */ final void putMapEntries(Map<? extends K, ? Extends V> m, Boolean evict) {extends V> m, Boolean evict) {int s = m.size(); // The hash table passed in is not emptyif(s > 0) {// If the current linked list table is empty, that is, it has not been used.if(table == null) {// pre-size // Get the initial size of the linked tablefloat ft = ((float)s/loadFactor Int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // If the required size is greater than threshold, run tableSizeFor(see the preceding analysis) to obtain the thresholdif(t > threshold) threshold = tableSizeFor(t); } // If the current list is not empty (for example, add elements through map.putall again during use) // The current size of the element to be added is greater than the threshold, then expand the operation resize()else if(s > threshold) resize(); // loop through m and add elements one by one using putValfor (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 codeResize method, which extends the capacity of the HashMap
When the size of the elements added to the table is about to exceed the threshold, the system expands the hash table to store the elements. Node
[]
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resizeNode<K,V>[] oldTab = table; Int oldCap = (oldTab == null)? 0 : oldTab.length; Int oldThr = threshold; Int newCap, newThr = 0; // If the original hash bucket size >0if(oldCap > 0) {// The current capacity has reached the maximum size of MAXIMUM_CAPACITYif (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
returnoldTab; /* If the current capacity has not reached the maximum, the capacity after expansion is 2*oldCap, (newCap = oldCap << 1, newCap = oldCap *2), If newCap is smaller than MAXIMUM_CAPACITY and oldCap is larger than DEFAULT_INITIAL_CAPACITY(16), the new threshold is oldThr*2 */else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // Double threshold} // If the original hash bucket has no size and a threshold has been set, the size of the new capacity is equal to the old thresholdelse if (oldThr > 0) // initial capacity was placed inthreshold newCap = oldThr; // If the original hash bucket has no size and the threshold has not been set (for example, when it was first created using the constructor three new HashMap()), // the new capacity defaults to 16, and the new threshold is calculated by defaultelse{ // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // If the new threshold newThr size is 0, newThr is assigned based on newCap and the load factorif (newThr == 0) {
float ft = (float)newCap * loadFactor; NewThr = (newCap < MAXIMUM_CAPACITY &&ft < (newCap < MAXIMUM_CAPACITY &&ft < (newCap < MAXIMUM_CAPACITY &&ft < (newCap < MAXIMUM_CAPACITY &&ft < (newCap < MAXIMUM_CAPACITY &&ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // After the calculation, reset the threshold of the HashMap. Threshold threshold = newThr; // Re-create array Node<K,V>[] @suppressWarnings ({"rawtypes"."unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // Assign the newly created array to the HashMap hash bucket table = newTab; // Copy the elements in the hash bucket one by oneif(oldTab ! = null) {for(int j = 0; j < oldCap; ++j) {// loop over old hash bucket Node<K,V> e; // If there are elements in the current bucket, it will be prepared to assign them to the new bucketif((e = oldTab[j]) ! = null) { oldTab[j] = null; // Set the element in the old bucket (old list) to null for subsequent GC collection. // Assign a header element from the old list to the new listifNewTab [e.hash & (newcap-1)] = e; newTab[e.hash & (newcap-1)] = e; newTab[e.hash & (newcap-1)] = e; // If a hash collision occurs and the number of nodes exceeds 8, it is converted to a red-black treeelse if(e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // If a hash collision occurs and the number of nodes is not more than 8, the new hash bucket will be placed in the corresponding subscript position according to the hash value of each node in the list.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; // The previous version is calculated ashash& (newCap - 1); Here is another efficient point using bit operation instead of conventional operation: using hash value and old capacity, we can get whether the hash value after modulo removal is greater than or less than oldCap, 0 means less than oldCap, and it should be stored in the low place, otherwise, it should be stored in the high placeif ((e.hash & oldCap) == 0) {
//whileLoop through the linked list of elements that need to be stored in the lower levelif (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//whileLoop through the linked list of elements that need to be stored highif (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! = null);if(loTail ! Next = null; lotail.next = null; lotail.next = null; newTab[j] = loHead; }if(hiTail ! = null) {// Assign the high list to the new hash bucket j+oldCap index hitail. next = null; newTab[j + oldCap] = hiHead; } } } } }returnnewTab; // return the hash bucket with the old element created and added}Copy the codeAdd, modify
1. Put (k,v) method to add or overwrite the element corresponding to the update key to the hash table, call putVal implementation
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
Copy the code2. PutIfAbsent (K,v) method (new API in JDK8) to add a new element corresponding to the key to the hash table. If the element corresponding to the key already exists, putVal is called
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
Copy the codeReplace (k,v) method (JDK8 new method) : replace(k,v) method (JDK8 new method) : replace(k,v) method
default V replace(K key, V value) { V curValue; if (((curValue = get(key)) ! = null) || containsKey(key)) { curValue = put(key, value); } return curValue; }Copy the codeReplace (K key, V oldValue, V newValue); replace(K key, V oldValue, V newValue); replace(K key, V oldValue, V newValue);
default boolean replace(K key, V oldValue, V newValue) { Object curValue = get(key); if (! Objects.equals(curValue, oldValue) || (curValue == null && ! containsKey(key))) { return false; } put(key, newValue); return true; }Copy the code5.putAll(Map<? extends K, ? Extends V> m), adds all elements that exist in M to the hash table, as described earlier with putMapEntries
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
Copy the code/** * onlyIfAbsenttrueIndicates that the element corresponding to the key does not exist. If it already exists, the value that updates the old element will not be overwritten;false* * evict is overwritten each time it is updatedfalseAnd the rest fortrue* When put(K,V) is used,onlyIfAbsent=false ,evict=true* When putIfAbsent(K,V) is used (in JDK8),onlyIfAbsent=true ,evict=true
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value, true means that if the element already has the key, @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node
[] tab; Node
p; int n, i; // If the original hash bucket is not created or its size is 0, it is initialized. And get the expansion after the size of n the if ((TAB = table) = = null | | (n = TAB. Length) = = 0) n = (TAB = the resize ()). The length; Hash (n-1) hash (n-1) hash (n-1) hash (n-1) hash (n-1) If ((p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); Else {Node
e; K k; / / if the original indexes root in line with the new elements to the hash and the key position element, directly to cover the value 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); // Insert a normal list node if it is not overridden else {// Iterate over the list at that position for (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {// go to the end and append the newNode to the end. // If (binCount >= treeify_threshold-1) // -1 for 1st treeifyBin(TAB, hash); break; } / / if the if found to cover the node (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; }} // If the value is not empty, you need to update the value that overwrites the old element. = null) { // existing mapping for key V oldValue = e.value; if (! OnlyIfAbsent | | oldValue = = null) / / onlyIfAbsent parameters determine e.v alue = value; // This is an empty implementation function used for the LinkedHashMap rewrite. afterNodeAccess(e); return oldValue; }} // If it reaches this point, a new node is inserted, so modCount is modified and null is returned. Modcout ++modCount; If (++size > threshold) resize(); // This is an empty implementation function used for the LinkedHashMap rewrite. afterNodeInsertion(evict); return null; }
,v>
,v>
,v>
,v>Copy the codedelete
1. Remove (k) method to remove the element corresponding to the specified key from the hash table
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false.true)) == null ?
null : e.value;
}
Copy the code2. Remove (k,v) method (JDK8 new API), remove the specified key from the hash table and value matches the corresponding element
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true.true) != null;
}
Copy the code2. Clear all elements of the hash table
Size =0 public void set hash index to null; void set hash index to nullclear() {
Node<K,V>[] tab;
modCount++;
if((tab = table) ! = null && size > 0) { size = 0;for(int i = 0; i < tab.length; ++i) tab[i] = null; }}Copy the code/** returns the removed element Node<K,V> * parameter matchValue, which means value also needs to be equal to delete * if the movable parameter isfalse* Implements Map. Remove and related methods * * @paramhash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; // If the current hash table is not empty, delete the table. Obtain the table header element p where the key should be storedif((tab = table) ! = null && (n = tab.length) > 0 && (p = tab[index = (n - 1) &hash])! = null) { Node<K,V> node = null, e; K k; V v; // Node =p if the list header p is the element to be deletedif (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) node = p; // If the list header p is not the element to delete, the list is iteratedelse if((e = p.next) ! = null) {ifNode node = ((TreeNode<K,V>)p).gettreenode (hash, key);
else {
do {
if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k)))) { node = e; // Get the element node to be deletedbreak;
}
p = e;
} while((e = e.next) ! = null); }} // If there is a key matching element node to deleteif(node ! = null && (! matchValue || (v = node.value) == value || (value ! = null && value.equals(v)))) {if(Node instanceof TreeNode) // Red black tree, delete element node ((TreeNode<K,V>)node).else ifTAB [index] = node.next; (node == p) // Instead of removing the root element, you need to point p (p) from node to node.next (p)elsep.next = node.next; ++modCount; // Change times --size; // Dynamically reduce the number of valid elements in the room; vivienemoval (node); // empty operation,LinkHashMap overridden withreturnnode; }}return null;
}
Copy the codeThe query
1. The get method is used to obtain the Value of the element corresponding to the specified key. If the Value is saved, the Value is returned; otherwise, null is returned
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code2. GetOrDefault (K key,V defaultValue), a method provided by JDK8 to obtain the value of the element corresponding to the specified key, if there is a value, return the corresponding value, otherwise return defaultValue
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
Copy the code3. ContainsKey method, which checks whether all keys in the hash table contain the key. The value is true if the key exists, and false if the key does not exist
public boolean containsKey(Object key) { return getNode(hash(key), key) ! = null; }Copy the code3. ContainsValue method, check whether all values in the hash table contain the value, return true if there is, return false if there is no, in the source code, all nodes are iterated over, if there are equal values, stop
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if((tab = table) ! = null && size > 0) {for (int i = 0; i < tab.length; ++i) {
for(Node<K,V> e = tab[i]; e ! = null; e = e.next) {if((v = e.value) == value || (value ! = null && value.equals(v)))return true; }}}return false;
}
Copy the code/** Return null * Implements Map. Get and related methods ** @param; /** return null * Implements Maphash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // Like removeNode, check that the hash table is not empty and get the first element at index positionif((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) &hash])! // Return first if first is the element to be queriedif (first.hash == hash&& // always check first node ((k = first.key) == key || (key ! = null && key.equals(k))))returnfirst; // Loop through the list to queryif((e = first.next) ! = null) {if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))return e;
} while ((e = e.next) != null);
}
}
return null;
}
Copy the codeIterator traversal of the query
1. KeySet (), traversal by key
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
Copy the code2. Values (), traversal according to value
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
Copy the code3. EntrySet (), traversal by element node
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
Copy the code