Introduction to HashMap terminology
Bin: a linked list or tree structure attached to an array Node: a common Node TreeNode: Capacity: the default value is 16. MIN_TREEIFY_CAPACITY: the default value is 64, which is converted to a red-black tree. Minimum table size TREEIFY_THRESHOLD: the default value is 8, which is converted to a red-black tree. The default value is 0.75. If the actual length of the table is greater than or equal to capacity* loadFactor, the capacity will be expanded. Threshold: capacity* loadFactor
Source code analysis
The Node Node
- General nodes in a HashMap are nodes, which are basic Hash bin nodes. Only after the linked list tree on a bin is converted into a TreeNode Node.
- A Node consists of four elements
- Hash: indicates the hash value
- Key: a key
- Value: the value
- Next: pointer to the next node in the list
HashMap capacity normalization
- TableSizeFor. The capacity of a Map must be a power of 2. If the capacity is not a power of 2, tableSizeFor of the Map automatically converts a customized capacity to a capacity greater than the minimum power of 2.
static final int tableSizeFor(int cap) {
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 codeThe constructor
- There are four constructors
- HashMap(int initialCapacity, float loadFactor) : sets the initialCapacity and loadFactor
- HashMap(int initialCapacity) : sets the initialCapacity and uses the default load factor
- HashMap() : Empty parameter construct, using the default load factor of 0.75
- HashMap(Map
m) : Passes a Map and converts it to a hashMap
hash()
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeGet the hashCode of the key first, then shift it and perform xor, xOR to reduce hash collisions.
map.get(Object key)
- If there is a key, return the corresponding value; If it does not exist, null is returned
- Concrete implementation:
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// is a header
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
// Always check the first node in the bin list, if so, return the header directly
if(first.hash == hash && ((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// This is not a header case
if((e = first.next) ! =null) {
//bin has a red-black tree structure
if (first instanceof TreeNode)
// Go to the red and black tree to find the node
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {// List structure, traverse the list, find the 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 codeCheck whether the hash of the first Node of the linked list in each bin of the table is equal to the hash of the key we are looking for, and check whether the key is equal. If the key is equal, the Node is returned directly.
The next step is to follow the list to Next. (If the first node is a TreeNode, use getTreeNode() as a tree traversal, otherwise use a linked list.)
map.put(K key, V value)
- Saves the specified key and value to the map. If the map previously had this key, the corresponding old value is replaced.
- Concrete implementation:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// TAB: hash array p:bin first node
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Initialization, lazy loading mode, when the first put operation initialization, capacity expansion
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//bin is null, initializes the first node, and puts the newly inserted k and v into the bin
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// bin already has a key, which means a hash collision has occurred. Here are some ways to handle hash collisions
Node<K,V> e; K k;
//1. The hash value of the inserted key is equal to the hash value of the current node, and the key is also equal to the key of the current node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// Specify that the value of key already exists, then record the original value
e = p;
//2. If the hash value is not equal to the first node, check whether p belongs to the node of the red-black tree
else if (p instanceof TreeNode)
// Add nodes in red-black tree mode
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//3. The hash value is not equal to the hash value of the first node or the node of the red-black tree, so it is the node of the linked list
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// When the threshold is reached, the tree becomes red-black
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// If there are duplicate keys in the list, e is the current duplicate node, ending the loop
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// If there is a duplicate key, the old value is overwritten by the value to be inserted.
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
// Empty implementation, reserved for LinkedHashMap
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//4. Number of changes +1
if (++size > threshold)
resize();
// Empty implementation, reserved for LinkedHashMap
afterNodeInsertion(evict);
return null;
}
Copy the codeIf table is null, resize;
If bin is null, initialize the first node, key and value that we’re going to put in k, v;
Otherwise, a hash conflict occurs in the following cases:
1. The hash value of the inserted key is equal to the hash value of the current node, and the key is also equal to the key of the current node. If the specified key value already exists, record the original value.
If the node under bin is TreeNode, it means that the data structure under bin is a red-black tree. Then, the node to be inserted will be inserted in the same way that nodes are inserted in red-black trees.
If the hash value is not equal to the hash value of the first node, nor is it a node of the red-black tree, it is a node of the linked list. Iterate through the linked list to find the end of the list. If the key to be added does not duplicate, insert the node using the tail insertion method. If the size under bin is greater than TREEIFY_THRESHOLD, all nodes of bin will be converted to TreeNode nodes, that is, the linked list will be converted to a red-black tree.
map.resize()
- Capacity expansion: The capacity after expansion must be a power of 2
- The specific implementation
final Node<K,V>[] resize() {
// Record the uninserted hash array as oldTab
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//oldCap>0, that is, not the first initialization, because hashMap uses lazy loading
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}// In other cases, double the 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 { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr does not assign a value above, so start the assignment here and use the default value
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// The critical value of the above case is actually changed here, i.e., the capacity and the critical value are changed.
threshold = newThr;
@SuppressWarnings({"rawtypes"."unchecked"})
// Start initialization
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// Iterate over the elements in old into new
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e; // Temporary node
// The current hash bin position is not null, save the bin header
if((e = oldTab[j]) ! =null) {
oldTab[j] = null; // The index value is null for easy collection
// If the node at the subscript has no next element
if (e.next == null)
// Temporary nodes are stored in newTab
newTab[e.hash & (newCap - 1)] = e;
// Red black tree structure
else if (e instanceof TreeNode)
// Go to newTab directly
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // Move old to new by iterating through the list
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;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the codeThe main steps of resize are also fairly clear:
1. Since HashMap is lazily loaded, the map is initialized only when the first PUT is performed, i.e. the resize process begins. If it is not initialized the first time, some properties of newTab are copied in another case, as described above.
2. After the new TAB array is created, we need to move the elements from old to new, and we need to go through the same process as the put operation. If you move tree directly to newTab — > the rest of the bin structure is a linked list, then directly iterate over old list elements into newTab.
map.remove(Object key)
- Remove keys and corresponding values from the map by key
- Concrete implementation:
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;
// 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) {
Node<K,V> node = null, e; K k; V v;
// If the subscript node of the array (the first node of bin) happens to be the key to be removed, use the node node first to save the node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
// If the node to be deleted is in a linked list or a red-black tree
else if((e = p.next) ! =null) {
// is the node of the red-black tree
if (p instanceof TreeNode)
// Walk through the red-black tree, find the node, return
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// List structure, traverse the list to find the node
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while((e = e.next) ! =null); }}// After finding the node to delete, judge! MatchValue, in general,! MatchValue to true
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
// Delete nodes from the red black tree
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// List structure, and delete the list header, let the next element be the header
else if (node == p)
tab[index] = node.next;
elseIn the linked list, set the next node to be deleted as the next node of the previous node
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the codeThe detailed steps are described above