Hashmap principle summary 2
problem
- Do you know what the process of the put element of HashMap is like
- Do you know what the get process looks like
- What other hash algorithms do you know
- Let's talk about the implementation of String hashcode
It is recommended to read the source code for an analysis, and then check the way of listing points, review and summarize the content of the source code process, and deepen the memory!!
Conduct an analysis in annotated form
Put process source code analysis
JDK1.8 source code analysis
/**
* 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 current table is empty or has no elements, the capacity will be expanded
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Get the i corresponding to the current key and judge whether there is a node in the bucket
// Note: index is n-1 & hash
if ((p = tab[i = (n - 1) & hash]) == null)
// If not, create a new Node and put it into the bucket
tab[i] = newNode(hash, key, value, null);
else { // hash collision occurs
Node<K,V> e; K k;
// If the hash is the same, the key reference is the same or the key value is the same, record to e first
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// If the first node is of red black tree type, the node addition method of red black tree type is used
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// The first node is a linked list type
else {
// Traverse the nodes on the linked list
for (int binCount = 0; ; ++binCount) {
// Find the end of the list
if ((e = p.next) == null) {
// Put the new node at the end first
p.next = newNode(hash, key, value, null);
// If the number of nodes exceeds the threshold, it will be transformed into a red black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Judge whether the new node already exists on the linked list. If so, e the node information has been recorded
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// Record nodes at the same location and overwrite them with value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// When the number of nodes + 1 is greater than the threshold, the capacity will be expanded
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Note: jdk1 8. Use the tail insertion method of linked list, jdk1 Head insertion method was used before 8
PUT process is summarized again
Make a secondary summary by listing points
1. Calculate the hashcode value of the key
2. If the hash table is empty, call resize() to expand the capacity
3. Check for collision
3.1 if there is no collision, directly add the node into the bucket
3.2 in case of collision
- If the first node has the same key address or the same content after equals, record e
- For the red black tree type, the method of adding node to the red black tree type is adopted
- For the linked list type, traverse the linked list
- Traverse to the tail node of the linked list, perform tail interpolation, and judge whether the number of nodes exceeds the tree threshold. If it exceeds the threshold, it will turn into a red black tree
- If the key address is the same or the content after equals is the same, record e
4. e overwrite the original value
5. Judge whether the new node is greater than the threshold (capacity * load_factor). If it exceeds the threshold, expand the capacity
Get process source code analysis
// hash(key) method is used to calculate hashcode according to code
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;
// Judge whether the table is empty
// Find the index according to n-1 & hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// If the first node table[i] == key, it will be returned directly
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// If there are multiple nodes in the bucket
if ((e = first.next) != null) {
// If it is a red black tree, the traversal method of the tree is used
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// If it is a linked list, it will traverse and distinguish different nodes by judging the hash value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
The Get process is summarized again
Make a secondary summary by listing points
1. Get the hash value according to the key value
2. Get the subscript corresponding to the key according to the hash
3. Judge whether the table is empty
3.1 if it is empty, null will be returned
3.2 if not empty
- If the first node is the same, return node
- It is a red black tree type, which adopts a convenient way of tree search
- For the linked list type, loop through and return node if found, null if not found
After personal summary
Reference articles
1.https://www.bilibili.com/read/cv5517205/ 2.https://zhuanlan.zhihu.com/p/353846426 3.https://blog.csdn.net/u011277123/article/details/80467673 (put details) 4.https://blog.csdn.net/m0_37550986/article/details/115833221 (get details)