Environment to prepare
- Java8_221 version
- The Idea of the Debug configuration
Introduction to HashMap
- A HashMap stores data in key-value pairs;
- The key cannot be repeated, but the value can be repeated, allowing null keys and null values.
- If the same key is added, the original key-value is overwritten, which is equivalent to modification (the key is not replaced, but the value is replaced).
- As with a HashSet, the order of the mapping is not guaranteed because the underlying store is hash;
- HashMap does not implement synchronization and is therefore thread-unsafe;
Underlying structure of HashMap
Expansion mechanism
- The underlying HashMap maintains an array table of type Node, which is null by default.
- When creating an object, initialize the loading factor loadfactor to 0.75;
- When a key-value is added, the hash value of the key is added to the index of the table. Then determine if the index has an element, if no element is added directly. If there is an element at the index, proceed to determine whether the element’s key is equal to the intended key. If so, replace val. If it’s not equal and you need to decide whether it’s a tree or a linked list, do different things. If the capacity is insufficient, expand the capacity.
- If the table is added for the first time, the table capacity needs to be expanded to 16 and the threshold is 12.
- In the future expansion, the table capacity needs to be expanded by 2 times, and the critical value is 2 times, that is, 24, and so on.
- In Java8, if the number of elements in a linked list exceeds TREEIFY_THRESHOLD(default: 8) and the table size >= MIN_TREEIFY_CAPACITY (default: 64), tree evolution (red-black tree) occurs.
Source code analysis
@SuppressWarnings("all")
public class HashMapSource {
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("java".10);
map.put("php".10);
map.put("java".20); }}Copy the code
1. Execute constructor new HashMap();
Initialize the loading factor this.loadFactor = DEFAULT_LOAD_FACTOR 0.75
Node<K,V>[] table = null
2. Execute put and invoke hash(key) first.
public V put(K key, V value) {
return putVal(// hash(key), key, value, false, true);
}
// Compute the hash value of Kay
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code
3. Perform putVal
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 underlying table array is null, or length == 0, expand to 16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Select a Node from the hash table index. If null, add k-v to newNode
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// If the hash of the key at the index position of the table is the same as that of the newly added hash, and the object is the same or equals() is the same
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// Already treed
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Compare in an infinite loop until the list is inserted and the loop stops
for (int binCount = 0; ; ++binCount) {
// If the whole list is not the same as it, it is added to the end of the list
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// After the list is added, check whether the number of current lists has reached 8. When the list reaches 8, the treeifyBin will determine whether to expand or tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Check if there is the same, if so break to update
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// Update operation
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value; / / replace
afterNodeAccess(e);
returnoldValue; }}// Every time newNode is added ++
++modCount;
// When the threshold is reached, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the code
treeifyBin
It turns into a red black tree
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// If table == null, or the size does not reach 64, do not tree, expand array first!
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
/ / tree
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while((e = e.next) ! =null);
if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code
Test capacity
1. Put the first element to perform the first expansion, size=16;
2. Put the 9th element to perform the second expansion, size=32, the linked list already has 9 elements;
3. When the 10th element is put, the third expansion is performed, size=64, and the tree condition is satisfied.
4. Put the 11th element to tree, HashMap$Node => HashMap$TreeNode
import java.util.HashMap;
/ * *@author Strive */
@SuppressWarnings("all")
public class HashMapSource2 {
public static void main(String[] args) {
HashMap map = new HashMap();
for (int i = 1; i <= 12; i++) {
map.put(new A(i), "hello");
}
System.out.println("hashMap="+ map); }}class A {
private int num;
public A(int num) {
this.num = num;
}
@Override
public int hashCode(a) {
return 100;
}
@Override
public String toString(a) {
return "\nA{" + "num=" + num + '} '; }}Copy the code