Structure of HashMap
Array + linked list or red black tree
When the number of nodes in the linked list is greater than 8, it will be turned into a red black tree, and when it is less than 6, it will be returned to the linked list
Inheritance relationship of HashMap
HashMap overall inheritance relationship
As can be seen from the above figure, HashMap inherits the abstractmap < K, V > class and implements the map < K, V > class, Cloneable class and Serializable class
Inheritance relationship between node < key, value > storing key value and treenode < K, V >
- Node < key, value > node structure
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //Hash value
final K key; //key value
V value; // Value value
Node<K,V> next; // Address value of the next node
}
- Node < key, value > in red black tree
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // Precursor node
boolean red;
}
- The specific inheritance relationship of nodes is as follows:
As shown in the figure above, the tree node treenode < K, V > inherits the entry < K, V > in LinkedHashMap, that is, linkedhashmap.entry < K, V >, while linkedhashmap.entry < K, V > inherits hashmap.node < K, V >, and hashmap.node < K, V > implements the map.entry < K, V > node
Learn a line of code that HashMap must understand
hash & tab.length-1
This line of code has appeared many times in HashMap. On the surface, it is used to determine the array subscript of table in HashMap. In fact, it's just a quick residual operation. Let's take a closer look at this line of code.
We know that the HashMap specifies that the length of the table must be a power of 2, and its binary representation is 100000000 ········; While tab.length-1 is 2^n-1, and its binary representation is 01111111 ·····& Is the and operator; Hash & tab.length-1 represents the bitwise sum of hash value and tab.length-1. In this way, the final combination will not be greater than tab.length, that is, array out of bounds will not occur.
Some core parameters of HashMap
Some parameters in HashMap
- Node < K, V > [] Table: an array of nodes
- int size: indicates the number of key value pairs contained in the current HashMap
- int modCount: used to record
- int threshold: indicates the maximum number of key value pairs that the current HashMap can withstand. Once this number is exceeded, the HashMap will be expanded
- final float loadFactor: load factor of hash table, used for capacity expansion
Static variables in HashMap
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
Default initial capacity - must be a power of 2. - static final int MAXIMUM_CAPACITY = 1 << 30
Maximum capacity, used when two constructors with parameters implicitly specify a higher value. Must be a power of 2 < = 1 < < 30. - static final float DEFAULT_LOAD_FACTOR = 0.75f
The load factor to use when not specified in the constructor. - static final int TREEIFY_THRESHOLD = 8
The threshold value for judging whether the linked list is converted into a red black tree is 8 - static final int UNTREEIFY_THRESHOLD = 6
The threshold value for judging whether the linked list should be returned by the red black tree is 6
Initialization and construction method of HashMap
- Construct an empty HashMap with default initial capacity (16) and default load factor (0.75)
public HashMap() {
// All properties are default values
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
- Construct an empty HashMap with the specified initial capacity and default load factor (0.75)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- Construct an empty HashMap with a specified initial 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);
}
- Construct a new HashMap using the same mapping as the specified Map. HashMap is created using the default load factor (0.75), and the initial capacity is sufficient to save the Map in the specified Map.
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
public V put(K key, V value) method of HasMap
The parameters passed in by the method are:
- < key, value > key value pair to be put into HasMap
Specific process analysis:
- The array is empty and has not been initialized yet: call resize() to initialize the array and put it directly into the corresponding position of table. (resize expansion method is very important)
- There is no Hash conflict at this position in the table: the construction node is placed in the table
- In case of Hash conflict, first judge whether the node element key s in the table are equal, and replace the value if they are equal
- Hash conflict occurs. The node is a TreeNode: insert the node in the way of red black tree
- A Hash conflict occurs. The Node is a Node: the construction Node is inserted in a linked list, and it is checked whether it reaches the threshold 8 of turning to red black tree after insertion
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// The array is empty. For the first time, put calls resize() to initialize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Query whether the corresponding position in the array generates hash conflict
if ((p = tab[i = (n - 1) & hash]) == null)
// Construct the Node and put it into the table
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// Judge whether the hash value of the key of the element in the table is equal to the hash value of the element ke to be put
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// Use e to save the node reference of p and replace the node reference later
e = p;
// Judge whether the p node in the table is a tree node
else if (p instanceof TreeNode)
// p is a tree node, which is inserted using the insertion method of red black tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// p is a linked list node, which is inserted in the way of linked list insertion
// for loop traversal linked list
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// Insert node
p.next = newNode(hash, key, value, null);
// Judge whether the number of current linked list nodes is greater than the equal threshold 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// If the number of current nodes is greater than or equal to 8, insert the current node into and tree the linked list
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// This is not the case where a new node needs to be inserted
// Find the node with the same key and replace value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// Determine whether capacity expansion is required
// That is, when the number of existing nodes is size > threshold (capacity * load factor), capacity expansion is required
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Treeifybin in put() method (node K, v [] tab, int hash)
The parameters passed in by the method are:
- Node < K, V > [] tab: an array of node < K, V > nodes
- int hash: the hash value of the key of the current put
Specific process analysis:
- Judge whether the tab array is empty or the length is less than the minimum tree size MIN_TREEIFY_CAPACITY(64)
a. If the judgment condition is true, the linked list will not be trealized, but the resize() method will be called to expand the capacity. After capacity expansion, the length of the linked list will be reduced to improve query efficiency.
b. If the judgment condition is not true, the linked list will be treelized. - Tree linked list:
a. Traverse the linked list and assign the attributes of the linked list node to the newly constructed TreeNode node
b. After the traversal, assign the value of hd to table[index] and judge whether it is not empty. If it is not empty, call the treeify() method to complete the tree.
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// Judge whether the array is empty or the array length is < 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// If the situation holds, the linked list will not be trealized, but the resize() method will be called for capacity expansion
// After capacity expansion, the length of the linked list will be reduced to improve the query efficiency
resize();
// Judge whether the corresponding position of the input hash value in the table is not empty
else if ((e = tab[index = (n - 1) & hash]) != null) {
// Not empty, tree
TreeNode<K,V> hd = null, tl = null;
do {
// Traverse the linked list and assign the attributes of the linked list node to the newly constructed TreeNode node
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);
// Assign the value of hd to table[index] and judge whether it is not empty
if ((tab[index] = hd) != null)
// It is not empty. The tree is finished
hd.treeify(tab);
}
}
public V get(Object key) method of HasMap
The parameters passed in by the method are:
- Object key is used to obtain the key of the key value pair value
Specific process analysis:
- Determine whether the element is in the array
- null if not
- In, judge whether the elements in the array are equal to the parameter key
- If equal, the elements in the array are returned
- If it is not equal, judge whether the element has a next element. If it does, it indicates that there is a linked list or tree. Then determine whether the element is a tree node
- If it is a tree node, find the target node by traversing the tree
- If not, the node is found by traversing the linked list
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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 array is not empty, whether the array length is greater than 0, and whether the position corresponding to the hash value corresponding to the Key is not empty
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// Determine whether it is a tree node
if (first instanceof TreeNode)
// Red black tree, call getTreeNode() method (similar to binary lookup tree logic)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// Linked list
do {
// Traverse to determine whether the hash values are equal. If they are equal, the node is returned
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
public V remove(Object key) method of HasMap
The parameters passed in by the method are:
- Object key is used to remove the key of the key value pair corresponding to the HashMap
Specific process analysis:
- Judge whether the array is not empty and whether there is no element at the position determined by the hash value of the key
a. If the judgment conditions are true.
1. Judge whether the node is on the array. If it is on the array, assign the node determined by the current hash value to node; The node is not on the array. Judge whether it is on the red black tree. If it is, call the getTreeNode method to obtain the node and assign it to node. If the node is not on the linked list, traverse the linked list to obtain the node assignment and end the traversal.
2. Judge whether the node is a tree node. If it is a tree node, call the remove method of the tree node; If it is not a tree node (i.e. a linked list node), the node successor is assigned to the elements in the array, and the node successor is assigned to the successor of the node precursor.
b. If one of them does not hold. That is, if the key is not in hashmap, null will be returned directly
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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;
// Judge whether the array is not empty and whether there are elements at the position determined by the hash value of the key. If one of them is not true, that is, the key is not in the hashmap, and null is returned directly
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;
// Judge whether the nodes are equal, that is, whether the nodes are on the array
if (p.hash == hash && ((k = p.key) == key ||
(key != null && key.equals(k))))
node = p;
// Node not on array
else if ((e = p.next) != null) {
// Judge whether the node is on the red black tree
if (p instanceof TreeNode)
// If the node is on the red black tree, call the getTreeNode method
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// The node is on the linked list
else {
// Traverse the linked list to find a node equal to the node's hash value or node key
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || (value != null &&
value.equals(v)))) {
// Judge whether the node is a tree node
if (node instanceof TreeNode)
// Call the remove method of the tree node
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// Assign subsequent nodes to elements in the array
tab[index] = node.next;
else
// Assign the node successor to the successor of the node precursor
p.next = node.next;
++modCount;
--size;
// Reserved method, which can be overridden after the class inherits HashMap
// Enables the specified operation to be completed after the node is removed
afterNodeRemoval(node);
return node;
}
}
return null;
}
final Node K,V [] resize() method of HasMap
What use calls the resize() method:
- Called at the first initialization
- The number of stored key value pairs > HashMap capacity * load factor requires capacity expansion
Specific process analysis:
Directly analyze relevant codes of capacity expansion - If the current array is not empty, the capacity and threshold are doubled, and the threshold property is updated
- Create an array twice the size of the current array, and update the table property
- Migrate the previous node to the corresponding location
a. Traverse each element of the current array and judge whether the element is not empty. If it is not empty, assign the current element to e and empty the current element.
b. Judge whether e.next is empty. If it is empty, the new capacity will be quickly taken out again, and e will be saved to the corresponding position of the new array; If it is not empty, judge whether it is a tree node. If it is a tree node, call split to expand the red black tree; If it is not a tree node, it is a linked list node.
c. Linked list. Traverse the linked list elements and split a linked list into two linked lists. The splitting basis is: whether the node needs to be moved before and after capacity expansion, that is, whether the remainder changes after fast remainder fetching
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// Judge whether the current array size oldCap is greater than 0
if (oldCap > 0) {
// Judge whether oldCap is greater than or equal to the maximum capacity of the current array
if (oldCap >= MAXIMUM_CAPACITY) {
//
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// Shift left by 1 bit, i.e. oldThr*2
newThr = oldThr << 1;
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// Initialize table
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 a new array that is twice the size of the current array
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//Update properties
table = newTab;
//Migrate the previous node to the corresponding location
if (oldTab != null) {
// Traverse each element of the old array
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// Judge whether each element is not null, and assign the element value and attribute to e
if ((e = oldTab[j]) != null) {
// Leave the element empty
oldTab[j] = null;
// p judge whether e.next is empty
if (e.next == null)
// If it is empty, the new capacity will be quickly redundant again, and e will be saved to the corresponding position of the new array
newTab[e.hash & (newCap - 1)] = e;
// If it is not empty, judge whether it is a tree node
else if (e instanceof TreeNode)
// Expand the red black tree and split the red black tree
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// Linked list
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// ergodic
do {
next = e.next;
// e. Nodes with hash & oldcap result equal to 0 are stored in the loTail linked list
//The remainder after capacity expansion is the same as before, and the node does not need to be moved.
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// e. Nodes with hash & oldcap results not equal to 0 are stored in the hiTail linked list
//The remainder after capacity expansion is inconsistent with that before, and the node needs to be moved.
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null)
//The remainder after capacity expansion is inconsistent with that before, and the node needs to be moved.
if (loTail != null) {
loTail.next = null;
//The head node of the loTail linked list is assigned to the current position of the new array
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// The head node of the hiTail linked list is assigned to the position where the new array is separated from the current position and the size of the array before capacity expansion
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
final void split(HashMap K,V map, Node K,V [] tab, int index, int bit) in resize() method
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// Traverse the red black tree and split the red black tree into two linked lists
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// If the number of loTail nodes is less than 6
if (lc <= UNTREEIFY_THRESHOLD)
// The red black tree is transformed into a linked list, and the loHead is assigned to the index position of the array
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
// bit original array size
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}