This article is participating in the “Java Theme Month – Java Brush questions card”, activity link
The title
HashMap simple source code analysis
knowledge
-
A HashMap is a hash table based on the map interface. It stores key-value mappings and both keys and values can be null. Because keys cannot be repeated, only one key can be null.
-
HashMap Uses the Hash algorithm to store and query data.
-
The implementation of HashMap uses an array + linked list + red-black tree structure, also known as hash bucket. Before JDK 1.8, it was all array + linked list structure, because in the linked list query operation is O(N) time complexity, if the number of nodes is large, it will improve the efficiency of the red black tree structure, because in the red black tree structure, add, delete, change and search are O(log N).
[Basic features]
-
HashMap hash tables are lazy loading mechanisms that are created on the first put
-
It stores data based on the hashCode value of the key, and in most cases its value can be located directly, thus providing fast access, but the traversal order is uncertain.
-
A HashMap allows a maximum of one record’s Key to be null and multiple records to be null.
-
Hashmaps are unordered and non-repetitive, and hashMaps are thread-unsafe.
-
By default, HashMap uses an Entry to represent key-value pairs. An array of entries is used to store all key-value pairs. Entry is linked to subsequent nodes in a linked list (after 1.8, the length of the linked list determines whether to convert it into a tree similar to TreeMap to save query time. Node takes the LinkedHashMapEntry property), which calculates the hash value of the key to determine which array (also known as Bucket) to map to.
-
A HashMap is not thread-safe, meaning that more than one thread can write a HashMap at any one time, which can lead to data inconsistencies.
-
If thread-safe is desired, the Collections synchronizedMap method can be used to make HashMap thread-safe, or ConcurrentHashMap can be used.
[Optimization point]
Time complexity (O(N) — > O(log(N)))
【 Principle Brief 】
【put 】
-
The input parameters
- Key value, value value
-
Operation process
-
First hash the Key against the incoming Key, then compute the subscript.
-
If there is no collision, it is directly put into the bucket. (Collision means that the hash values computed are the same and must be placed in the same bucket, indicating that they belong to the linked list.)
-
If hash values collide, they are linked to the back in a linked list.
-
If the list length exceeds the TREEIFY THRESHOLD (TREEIFY THRESHOLD==8), the list is converted to a red-black tree; if the list length falls below 6, the red-black tree is converted back to the list.
-
If the hashcode of the key is the same and the value is the same, the old value is replaced
-
If the bucket reaches the Threshold (initial capacity (16) and load factor (0.75)), it needs to resize (double capacity and rearrange (rehash and rearrange))
-
Data structure diagram
HashMap property code
First, keep in mind that one of the traditional patterns of JCF is to integrate AbstractXXX abstract classes and implement all of the base interfaces XXX, XXX (Map, List, Set, Collection, etc.) and implement serialization and cloning.
Property defaults
public class HashMap<K.V> extends AbstractMap<K.V>
implements Map<K.V>, Cloneable.Serializable {
// Serial number used for serialization
private static final long serialVersionUID = 362498820763181265L;
// The default capacity is 2 ^ 4, which is 16, and must be 2 ^ n (must be composite)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// The maximum capacity is 2 ^ 30.
static final int MAXIMUM_CAPACITY = 1 << 30;
// Load factor for capacity expansion.
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
// The threshold for the list to become a red-black tree. That is, when the length of the list (the number of elements in the bucket) exceeds this value when the hash table is expanded, the list is converted to a red-black tree
static final int TREEIFY_THRESHOLD = 8;
// The threshold for the red-black tree to become a linked list. That is, if the length of the linked list (the number of elements in the bucket) is found to be less than 6 during the expansion of the hash table, the red-black tree will be degraded to the linked list again
static final int UNTREEIFY_THRESHOLD = 6;
// When the number of elements in the entire hashMap is greater than 64, it is also converted to a red-black tree structure.
// The minimum tree capacity of a HashMap. This value means: the number at bin
// The minimum capacity of the Table to be stored in a red-black tree structure
// Minimum capacity threshold for a linked list to become a red-black tree) when the capacity in the hash table is greater than this value
// If there are too many elements in the bucket, the bucket will be expanded
// The value cannot be less than 4 *
// TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
}
Copy the codeThe property parameter
public class HashMap<K.V> extends AbstractMap<K.V>
implements Map<K.V>, Cloneable.Serializable {
transient Node<K,V>[] table;
// Convert data to another storage form of set. This variable is mainly used for iteration functions.
transient Set<Map.Entry<K,V>> entrySet;
// Number of elements
transient int size;
// Count the number of changes to the map, which records the number of changes to the internal structure of the HashMap. It is mainly used for the rapid failure mechanism of iteration
transient int modCount;
// Threshold of HashMap/expansion threshold, the number of key-value pairs that can be accommodated //
If size>=threshold, the system will expand capacity. The calculation method is as follows: Capacity * negative
// Load factor.
int threshold;
// Load factor
final float loadFactor;
}
Copy the code-
The Node [] table: LoadFactor is the loadFactor (DEFAULT_LOAD_FACTOR is 0.75 by default). Threshold is the maximum number of nodes (key-value pairs) that a HashMap can hold.
-
Threshold = length * loadFactor. That is, the larger the load factor, the greater the number of key-value pairs it can hold after the array has been defined.
-
The default loading factor is 0.75. When the number of elements stored in the HashMap is greater than (capacity × load factor), which is greater than 16*0.75=12, the HashMap expands **.
-
-
Size: This field is the number of key-value pairs that actually exist in the HashMap. Note the difference between table length and the maximum number of key-value pairs threshold.
-
The modCount: field is used to record the number of times the internal structure of a HashMap has changed, mainly for quick iteration failures. And again, internal structural change means structural change.
- Put Indicates a new key-value pair. If the value corresponding to a key is overwritten, this is not a structural change.
The internal functions of HashMap are realized in many ways. This paper mainly introduces representative points such as obtaining hash bucket array index position according to key, detailed execution of PUT method, and expansion process.
The constructor
The first one sets the default initialization + default load factor, the second one sets the initial capacity + initial default load factor, and the third one sets the initial capacity and load factor.
// Default initial capacity + default load factor
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// Customize initial capacity + default load factor
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// Customize the initialization capacity and load factor
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);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean
evict) {
// Get the actual length of the map
int s = m.size();
if (s > 0) {
// Check whether the table is initialized, if not
if (table == null) { // pre-size
/** +1 = 0; /** +1 = 0; /** +1 = 0; /** = 0; 22/0.75=29.3, the required capacity must be 30, some people ask if it is just enough to divide the whole number, if it is an integer, it does not matter if the capacity is 1 more **/
float ft = ((float)s / loadFactor) + 1.0 F;
// Determine whether the capacity exceeds the upper limit.
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
TableSizeFor (t) The method returns a value greater than t and the nearest power of 2. For example, if t is 29, the value is 32**/
if (t > threshold)
threshold = tableSizeFor(t);
}
// If the table is already initialized, expand the table. Resize () is used to expand the table.
else if (s > threshold)
resize();
// Go over the map to the 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 codeThe node object
TreeNode, the internal class of HashMap, is a red-black tree structure.
static final class TreeNode<K.V> extends
LinkedHashMap.LinkedHashMapEntry<K.V> {
// red-black tree links
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
// needed to unlink next upon deletion
TreeNode<K,V> prev;
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next); }}Copy the codeHashMap internal class Node, structured as a one-way linked list.
static class Node<K.V> implements Map.Entry<K.V> {
final int hash;
final K key;
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(a) { return key; }
public final V getValue(a) { return value; }
public final String toString(a) { return key + "=" + value; }
public final int hashCode(a) {
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 instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false; }}Copy the codeHash method
A Hash () method that resolves conflicting Hash methods. The Hash of a HashMap evaluates the hashCode() first and then performs a second Hash.
// Computes the quadratic Hash
int hash = hash(key.hashCode());
// Use Hash to find the array index
int i = hash & (tab.length-1);
static final int hash(Object key) {
int h;
// Get the hashCode of the key first, then perform the xor operation
// It is very complicated, but it is definitely to reduce hash collisions
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeThis method is very clever in that it always uses h &(table.length-1) to get the location of the object, while the length of the underlying array of the HashMap is always 2 to the power of n. When length is always a multiple of 2, h & (Length-1) would be a very clever design:
-
Assuming h=5 and length=16, then h & Length-1 will yield 5;
-
Assuming h=6 and length=16, then h & Length-1 will yield 6
-
Assuming h=15 and length=16, then h & Length-1 will yield 15;
-
But when h=16, length=16, then h & length-1 will be 0; When h=17 and length=16, then h & length – 1 will be 1. This ensures that the computed index value is always within the index of the table array.
Add elements
public V put(K key, V value) {
// Hash key hashCode()
return putVal(hash(key), key, value, false.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
* @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<K,V>[] tab; Node<K,V> p; int n, i;
// If the table is empty or length is 0, expand the table by default. N is the length of the table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
Table [I]==null
if ((p = tab[i = (n - 1) & hash]) == null)
// (n-1)&hash implements the same hash as Java7 indexFor. If the value of I is empty, create a new Node. Table [I] points to that Node.
// Insert directly
tab[i] = newNode(hash, key, value, null);
else {
// If the value of the I position is not empty, check whether the Node p in the current position has the same hash and key as the key to be inserted
Node<K,V> e; K k;
// Overwrite value if the node key exists
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
Table [I] = table[I] = table[I
else if (p instanceof TreeNode)
// If the node p in the current position is already an instance of TreeNode, insert a new node into the tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// table[I] This link is a common linked list, which can be inserted into the list
else {
// Find the position where P.ext is null in the list at position I, and binCount calculates the length of the current list. If continuing to insert conflicting nodes into the list will make the length of the list greater than the tree threshold, then the list will be converted to a tree.
for (int binCount = 0; ; ++binCount) {
// If the last node is traversed, there is no matching key. Create a new node and add it to the end
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// List length greater than 8 is converted to red black tree for processing
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// If the key already exists, override the value and jump out of the loop
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// If the key already exists, set the value of the corresponding node to the new value
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// After the insert is successful, check whether the actual number of key value pairs size exceeds the maximum capacity threshold. If so, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codePutVal method of red-black tree structure
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) { Class<? > kc =null;
boolean searched = false; TreeNode<K,V> root = (parent ! =null)? root() :this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if((pk = p.key) == k || (k ! =null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if(! searched) { TreeNode<K,V> q, ch; searched =true;
if(((ch = p.left) ! =null&& (q = ch.find(h, k, kc)) ! =null) || ((ch = p.right) ! =null&& (q = ch.find(h, k, kc)) ! =null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if(xpn ! =null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null; }}}Copy the codeThe general idea of put() method is as follows:
-
Hash key hashCode(), then evaluate index;
-
If you don’t hit it, you put it in the bucket;
-
If they collide, they should be stored behind buckets in a linked list.
-
If the collision causes the list to be too long (greater than or equal to TREEIFY_THRESHOLD=8), the list is converted to a red-black tree;
-
Replace old value if the node already exists
-
If the bucket is full (exceeding load factor*current capacity), resize is required.
The specific steps are
-
If without the table used (TAB = table) = = null | | (n = TAB. Length) = = 0, the default size on a resize.
-
Hash = TAB [I]; hash = TAB [I]; hash = TAB [I]; hash = TAB [I
- Check that the first element of the bucket is equal to the inserted key (equals if it is the same object).
- If it’s not equal and it’s a TreeNode, call TreeNode put or loop through the tree,
- If it finds the same key it breaks out of the loop otherwise when it reaches the last node the new node is added to the list and finally, if it finds the same key at the front it replaces the value of that node with the new value.
- Finally, if a key-value pair is added, the size is increased and the threshold is determined. If the threshold is exceeded, resize is required
Expansion size
-
Resize is the process of adding more and more elements to a HashMap. When the array inside a HashMap cannot hold any more elements, the object needs to increase the array size to accommodate more elements.
-
Of course, arrays in Java cannot be automatically expanded by replacing a small array with a new one, just as we use a small bucket of water to hold more water, so we have to replace it with a larger bucket.
-
The resize method is a bit more complex than in JDK7 because of the need to consider whether hash conflict resolution is a linked list or a red-black tree.
-
Rehashing trigger conditions:
- Exceeding the default capacity * load factor;
- Loading factors are unreliable, such as much more than 1.
When a HashMap is expanded, it is doubled and the data at the hash collision is redistributed, with some remaining “in place” according to the new hash index value and some being moved to the new place with an offset.
- The specific steps are as follows:
- First, calculate the new capacity and threshold values after resize().
- If the original capacity is greater than zero, double the capacity. Otherwise, set the capacity to the default value.
- Create a new array of capacity size
- Puts the elements of the old array into the new array
final Node<K,V>[] resize() {
// Copy field references to the local variable table to reduce the need for the getField directive in later use
Node<K,V>[] oldTab = table;
// oldCap is the size of the original array or 0 when empty
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// If the table capacity exceeds 1>>30, the table cannot be expanded. You can only change the threshold
threshold = Integer.MAX_VALUE;
return oldTab;
}
// The new array is twice the size of the old one
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// When the old array size is greater than or equal to the default size, threshold is doubled
newThr = oldThr << 1;
}
else if (oldThr > 0)
// initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
// Initialize the operation
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"})
// Create newTab with capacity newCap and migrate nodes from oldTab. Consider both list and tree.
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// Copy the array from the original array into the new array
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)
// If e is the only element of the bucket, it is directly assigned to the new array
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// The split method will split the tree into lower and upper trees. If the number of nodes in the subtree is less than UNTREEIFY_THRESHOLD, the tree will be untreeify and the nodes will be stored in newTab.
// In the case of TreeNode, use the split method in TreeNode to split the tree into two small trees
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// Otherwise, create two lists to store the data to be placed, hash 0 and oldCap 0 (oldCap 1 and oldCap 1 are both hash 1 and hash 1) low, In this way, the old data is divided into two linked lists and then placed in their respective remainder positions
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// Put after loTail or hiTail according to the e.dash value
if ((e.hash & oldCap) == 0) {
// The element whose operation result is 0 is recorded with LO and joined into a new linked list
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// If the operation result is not 0, use li to record the data
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
// Put it in a new array
if(loTail ! =null) {
loTail.next = null;
// Lo is still in the "original" position, which is calculated based on the new hash value
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
// Li is in the j+oldCap position
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the codeAccess to elements
First = TAB [hash&(n-1)] first= TAB [hash&(n-1)] first= TAB [hash&(n-1)] Instead of iterating through the list to find the same key Value, return the corresponding Value.
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
* @param hash 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;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
// If it is a header, return the header directly
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
// Check if it is a red-black tree
if (first instanceof TreeNode)
// If it is a red-black tree, go to the red-black tree and return
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// If not, it is a list node, iterate through the list, find the node, and return
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the codeRed-black tree structure
static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
TreeNode<K,V> parent; // Red-black tree links parent node
TreeNode<K,V> left; / / the left subtree
TreeNode<K,V> right; / / right subtree
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // Color attributes
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next); }}Copy the codeTree operation
Determine whether to expand or tree based on the number of elements in the hash table. If you tree through the bucket, create the same number of tree nodes, copy the contents, establish the connection, and then make the first element of the bucket point to the new tree head. // The value of MIN_TREEIFY_CAPACITY is 64. If the current table length is insufficient, resize() // Replaces all the linked list nodes in the bucket with red-black tree nodes
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// If the current hash table is empty, or the number of elements in the hash table is less than the tree threshold (default: 64), create a new hash table.
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// If the number of elements in the hash table exceeds the tree threshold, tree
// e is the list node in the bucket at the specified position in the hash table, starting from the first one
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
// The first and last nodes of a red-black tree
TreeNode<K,V> hd = null, tl = null;
do {
// Create a new tree node with the same contents as the current list node e
TreeNode<K,V> p = replacementTreeNode(e, null);
// Determine the tree head node
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while((e = e.next) ! =null);
// Make the first element of the bucket point to the head of the new red-black tree
if((tab[index] = hd) ! =null) hd.treeify(tab); }}TreeNode<K,V> replacementTreeNode(Node
p, Node
next)
,v>
,v>{
return new TreeNode<>(p.hash, p.key, p.value, next);
}
Copy the codeRemove elements
Now let’s look at the remove method.
public V remove(Object key) {
// Temporary variables
Node<K,V> e;
/** Call removeNode(hash(key), key, null, false, true) with the third value null to remove the key
return (e = removeNode(hash(key), key, null.false.true)) = =null ?
null : e.value;
}
/** the first parameter is the hash value, the second parameter is the key, the third parameter is the value, the fourth parameter is true, the corresponding value of the key is not deleted, the fourth parameter is false, the node is not moved **/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// TAB hash array, p array index node, n length, index current array index
Node<K,V>[] tab; Node<K,V> p; int n, index;
// The hash array is not null, and the length is greater than 0, and the index position of the node whose key is to be removed is obtained
if((tab = table) ! =null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) ! =null) {
//nodee stores the node to be deleted, e temporary variable, k current node key, v current node value
Node<K,V> node = null, e; K k; V v;
// If the array subscript happens to be the node to be deleted, assign the value to the temporary variable node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
// The node to be deleted is a red-black tree or a linked list
else if((e = p.next) ! =null) {
if (p instanceof TreeNode)
// Walk through the red-black tree, find the node and return
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // represents a linked list node, the same traversal to find the node
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
node = e;
break;
}
/** note that if you are traversing the list, p is no longer the node of the array subscript, but the last node of the node **/
p = e;
} while((e = e.next) ! =null); }}// After finding the node to delete, judge! MatchValue, our normal remove remove,! MatchValue to true
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
// If the node to be deleted is a red-black tree, delete it from the red-black tree
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// If the list structure is linked and the node removed is the array subscript node (i.e. the header node), let the next node be the header
else if (node == p)
tab[index] = node.next;
else /** the next node to be deleted is set to the next node of the previous node **/
p.next = node.next;
// Modify the counter
++modCount;
// The length is reduced by 1
--size;
/** This method is implemented by subclasses of hashMap to handle the list relationship after deleting nodes **/
afterNodeRemoval(node);
// Returns the deleted node
returnnode; }}// If null is returned, the node does not exist and cannot be deleted
return null;
}
Copy the codeDelete the clear method, which sets all array subscript elements to null.
The size () method
The size of a HashMap is simple. It is not calculated in real time, but increases each time a new Entry is added. Decrement when you delete. Space for time. Because it’s not thread-safe. You can do that. It’s efficient.
Stretch out in all directions
capacity
-
There are two important parameters in a HashMap, the initial capacity and the load factor. When a HashMap is first initialized, using the default constructor, an empty table is returned and theshold (capacity threshold) is 0.
-
Therefore, the default value for the first expansion will be 16, and the default load factor is 0.75. Multiply the array capacity by the load factor to get a value. Once the number of elements stored in the array exceeds this value, the rehash method will be called to increase the array capacity to twice the original value, and the threshold will also become twice the original value.
-
During capacity expansion, a new array is generated, and all the original data needs to be recalculated and reassigned to the new array. Therefore, capacity expansion consumes a lot of performance.
So, if you know that the amount of data to be stored is large, you can specify a large amount of data when creating a HashMap, or you can extend the question whether to insert or expand the HashMap first:
After the initialization of HashMap, when data is inserted for the first time, resize will occur first and then data will be inserted. After that, when the number of inserted data reaches the threshold, resize will occur. In this case, data will be inserted first and then resize. Is a capacity expansion in a HashMap done before or after element insertion
-
In JDK1.7, this is done before element insertion
-
In JDK1.8, you add elements first and then decide whether to proceed
In JDK1.7, capacity expansion is performed only when the number of storage elements exceeds the threshold and the current storage location is not null. In JDK1.8, capacity expansion is performed.