Basic instructions in this article:
- This article is used to record hashmap source code related reading (relatively simple)
- This article is based on a certain understanding of map (for example, the basic data structure of hashmap is array + linked list + red-black tree)
- For the detailed operation of the red-black tree, there is no relevant explanation in this article
1. Basic use of HashMap
//1. create object
HashMap<String, String> map = new HashMap<>();
//2. Add value
map. put("name", "dingkewen");
//3. Get the value
String name = map. get("name");
//4. Delete the value
map. remove("name");
2. Basic important constants and related instructions
// 1. The initial length of the array can only be a power of 2, and the default is 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 2. The maximum length of the array, the length of the array is int type and is the nth power of 2, so the closest value to Integer.MAX_VALUE is 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// load factor, array use length >= DEFAULT_LOAD_FACTOR* array length expansion
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// The linked list is converted to one of the red-black tree conditions (the length of the linked list is greater than 8, and the length of the array is greater than 64)
static final int TREEIFY_THRESHOLD = 8;
// Conditions for converting a red-black tree into a single table (to prevent repeated addition and deletion of 8 edges, resulting in jumping back and forth between the linked list and the red-black tree)
static final int UNTREEIFY_THRESHOLD = 6;
// Refer to TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
3.HashMap key method
3.1. Constructor
3.1.1 java.util.HashMap#HashMap()
// just set the loading factor (do not set the creation of arrays or anything)
public HashMap() {<!-- -->
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
3.1.2 java.util.HashMap#HashMap(int)
// specify the load factor
public HashMap(int initialCapacity) {<!-- -->
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3.1.3 java.util.HashMap#HashMap(int, float)
// Specify load factor and array length
// If the specified capacity is greater than the maximum capacity specified in the map, the maximum capacity will be directly assigned to the specified capacity ()
```java
public HashMap(int initialCapacity, float loadFactor) {<!-- -->
//1 create object
//2 The specified capacity cannot be negative, nothing to say
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//3 If the specified capacity is greater than the maximum capacity specified in the map, the maximum capacity will be directly assigned to the specified capacity
// Refer to the description of basic constants:
// The maximum length of the array, the length of the array is int type and is the nth power of 2, so the closest value to Integer.MAX_VALUE is 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//4 The specified load factor check
if (loadFactor <= 0 || Float. isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//5 specify load factor
this. loadFactor = loadFactor;
//6 Threshold value specification, the specified capacity is searched up to the nearest nth power of 2
// n |= n>>>* What you get after the operation is 1111*1, so there is a + 1 behind it
/*
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;
}
*/
this.threshold = tableSizeFor(initialCapacity);
}
3.2. Add value java.util.HashMap#put
//Continue to call the method
public V put(K key, V value) {<!-- -->
return putVal(hash(key), key, value, false, true);
}
// actually call the method
/*
Flow Description:
Node<K,V> e variable description, if the key with an element found in the entire map is the same as the key to be added, assign the found element to this e, and then assign the value below
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {<!-- -->
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. If the array is empty or the length of the array is 0, expand it
if ((tab = table) == null || (n = tab. length) == 0)
n = (tab = resize()). length;
// 2. Find the position of the element in the array according to the hash. If there is no value in this position, directly create a Node and put it in this position
if ((p = tab[i = (n - 1) & amp; hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {<!-- -->// Indicates that there is a value in this position in the array
Node<K,V> e; K k;
// 3. The key of the stored element in the array is the same as the key to be put in. In theory, the value in the parameter is directly overwritten with the value of the node at this position. Until then, the element at this position is only temporarily used Save the variable and overwrite it below
if (p.hash == hash & amp; & amp;
((k = p.key) == key || (key != null & amp; & amp; key.equals(k))))
e = p;
// 4. Determine whether the node in the array is a TreeNode type. If the value setting method in the tree is called, if the key does not exist in the tree, add it directly to the red-black tree and fanhuinull, otherwise find the same key The node, and returns, assigned to the temporary variable e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {<!-- -->// 5. It can only be a linked list, enter the loop
for (int binCount = 0; ; + + binCount) {<!-- -->
// 5.1. Determine whether it is a tail node. If it is, it means that the loop has reached the end of the linked list, but it has not been found. Create a new node directly as a new tail node
if ((e = p. next) == null) {<!-- -->
p.next = newNode(hash, key, value, null);
// 5.2. Determine whether to convert the linked list into a red-black tree. If so, slowly convert the linked list into a red-black tree (the length of the linked list is greater than or equal to 8 and the length of the array is greater than or equal to 64)
//"8" is judged here, note that binCount starts from 0, so the boundary is 8 not 7
//"64" is judged in treeifyBin
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//5.3. If an element is found in the linked list, and the key of this element is the same as the key passed in, assign this node to the temporary variable e and exit the loop
if (e.hash == hash & amp; & amp;
((k = e.key) == key || (key != null & amp; & amp; key.equals(k))))
break;
p = e;
}
}
// 6. If e exists, it will be overwritten and the value in the original node will be returned
if (e != null) {<!-- --> // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e. value = value;
afterNodeAccess(e);
return oldValue;
}
}
+ + modCount;
// 7. Determine whether to expand the capacity, if necessary, expand the capacity
if ( + + size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// Several important methods
// Perturbation function java.util.HashMap#hash
/*
hashCode() If not rewritten, the object address is mapped to int type
h>>>16 is to get the high four bits of hashCode()
The lower four digits of the obtained number after h^(h>>>16) combine the characteristics of the lower four digits and upper four digits of the original hashcode
Get the array subscript (the array subscript is the nth power of 2, length-1=>111...111)
(table.lengtn-1) & amp;hash() Even if the length of the array is not that long, the obtained subscript is also combined with the upper four digits and lower four digits of the original data, so that both the upper four digits and the fourth digits participate The operation is reduced, and the contingency of the hash collision is reduced.
*/
static final int hash(Object key) {<!-- -->
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//Expansion function java.util.HashMap#resize
// Focus on variables
// Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// int newCap
final HashMap.Node<K,V>[] resize() {<!-- -->
HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab. length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {<!-- -->
// 1. The capacity is already large enough, so it cannot be expanded
if (oldCap >= MAXIMUM_CAPACITY) {<!-- -->
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 2. Expansion, length * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY & amp; & amp;
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 signs using defaults
// 3. Initialization when creating an array
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"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {<!-- -->
// 4. Data migration
for (int j = 0; j < oldCap; + + j) {<!-- -->
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {<!-- -->
oldTab[j] = null;
if (e.next == null)// There are only elements in the array, there is no linked list or red-black tree below, directly assign
newTab[e.hash & amp; (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)// Red-black tree data migration, although I can't understand it, it should also traverse the red-black tree, re-hash, and add to the new table
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {<!-- --> // preserve order
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
do {<!-- -->
// Re-hash, or the original position
next = e. next;
if ((e.hash & amp; oldCap) == 0) {<!-- -->
if (loTail == null)
loHead = e;
else
loTail. next = e;
loTail = e;
}
else {<!-- -->// After re-hash, the position is no longer the original position, it is the original position + the old array length
if (hiTail == null)
hiHead = e;
else
hiTail. next = e;
hiTail = e;
}
} while ((e = next) != null);
// Still in the original position, assign
if (loTail != null) {<!-- -->
loTail. next = null;
newTab[j] = loHead;
}
// new location for assignment
if (hiTail != null) {<!-- -->
hiTail. next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
3.3. Get value java.util.HashMap#get
public V get(Object key) {<!-- -->
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/*
Actually, there is nothing to say,
Now determine the position in the array
See if the elements in the array are, if yes, directly return the node in the array
If not, judge whether the node in the array is a TreeNode, if so, search in the tree
If not, go to the linked list to find
*/
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 & amp; & amp; (n = tab. length) > 0 & amp; & amp;
(first = tab[(n - 1) & amp; hash]) != null) {<!-- -->
if (first. hash == hash & amp; & amp; // always check first node
((k = first.key) == key || (key != null & amp; & amp; key.equals(k))))
return first;
if ((e = first. next) != null) {<!-- -->
if (first instance of TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {<!-- -->
if (e.hash == hash & amp; & amp;
((k = e.key) == key || (key != null & amp; & amp; key.equals(k))))
return e;
} while ((e = e. next) != null);
}
}
return null;
}
3.4. Delete value java.util.HashMap#remove(java.lang.Object)
public V remove(Object key) {<!-- -->
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e. value;
}
/*
// split into two parts
// Find the node first
// delete the node again
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {<!-- -->
//1 Find the node node
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null & amp; & amp; (n = tab. length) > 0 & amp; & amp;
(p = tab[index = (n - 1) & amp; hash]) != null) {<!-- -->
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash & amp; & amp;
((k = p.key) == key || (key != null & amp; & amp; key.equals(k))))
node = p;
else if ((e = p.next) != null) {<!-- -->
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {<!-- -->
do {<!-- -->
if (e.hash == hash & amp; & amp;
((k = e.key) == key ||
(key != null & amp; & amp; key.equals(k)))) {<!-- -->
node = e;
break;
}
p = e;
} while ((e = e. next) != null);
}
}
// 2. Delete the node node
if (node != null & amp; & amp; (!matchValue || (v = node.value) == value ||
(value != null & amp; & amp; value. equals(v)))) {<!-- -->
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node. next;
else
p.next = node.next;
+ + modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}