jdk1.7 -: it is composed of array + linked list. The array is the main body. The linked list mainly exists to solve hash conflicts (i.e. the array index values calculated through the key are the same) (the "zipper method" solves conflicts). jdk1.8 +: it is composed of array + linked list + red black tree. There are great changes in resolving hash conflicts. When the length of the linked list is greater than the threshold (the boundary value of the red black tree is 8 by default) and the current array length is greater than 64, the data storage structure at this index position will be transformed into a red black tree. Add: before the linked list is converted into a red black tree, even if the threshold is greater than 8, but the array length is less than 64, the linked list will not be changed into a red black tree, but the capacity of the array will be expanded. The purpose is: when the array is small, try to avoid the red black tree structure. In the case of red trees, the efficiency of these operations will be reduced because the red trees will become black. At the same time, when the array length is less than 64, the search time is relatively faster. Therefore, as mentioned above, in order to improve performance, the linked list is converted into a red black tree only when the underlying threshold is greater than 8 and the array length is greater than 64. For details, please refer to the treeifyBin() method. Of course, although the red black tree is added as the underlying data structure, the structure becomes complex, but when the threshold is greater than 8 and the array length is greater than 64, the efficiency becomes more efficient when the linked list is converted to red black tree.
1. The access of HashMap is out of order
2. NULL is allowed in all cases
3. In the case of multithreading, this class is safe, and HashTable can be considered.
4. The bottom layer of JDk8 is array + linked list + red black tree, and the bottom layer of JDK7 is array + linked list.
5. Initial capacity and load factor are the key points that determine the performance of the whole class. Don't move easily.
6. HashMap is created lazily. It will be built only when you put data
7. When converting a one-way linked list into a red black tree, it will first change into a two-way linked list and finally into a red black tree. The two-way linked list and the red black tree coexist. Remember.
8. For the two key s passed in, it will be forced to judge the height. The main purpose of judging the height is to decide whether to turn left or right.
9. After the linked list is transferred to the red black tree, efforts will be made to integrate the root node of the red black tree, the head node of the linked list and the table[i] node into one.
10. When deleting, first judge whether the number of red and black trees of deleted nodes needs to be transferred to the linked list. If not, it is similar to RBT. Find an appropriate node to fill in the deleted nodes.
11. The root node of the red black tree is not necessarily the same as the table[i], that is, the head node of the linked list. The synchronization of the three is realized by MoveRootToFront. And hashiterator Remove() will call removeNode with movable=false.
Static variable
/** Serialization version number */
private static final long serialVersionUID = 362498820763181265L;
/** The set initialization capacity must be the n-th power of 2. The default initial capacity is 16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/** The maximum capacity of the set, which is the 30th power of 2 by default */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** Default load factor, default 0.75 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** When the number of elements in the linked list exceeds this value, it will turn into a red black tree (new in jdk1.8) */
static final int TREEIFY_THRESHOLD = 8;
/** When the value of the linked list is less than 6, it will be transferred back from the red black tree to the linked list */
static final int UNTREEIFY_THRESHOLD = 6;
/** When the number of stored elements exceeds this value, the bucket in the table can be converted into a red black tree. Otherwise, when the elements in the bucket exceed the specified conditions, it will only be expanded */
static final int MIN_TREEIFY_CAPACITY = 64;
/** Array structure */
transient Node<K,V>[] table;
/**Store cached data */
transient Set<Map.Entry<K,V>> entrySet;
/**Number of stored elements */
transient int size;
/** It is used to record the modification times of HashMap, that is, the counter for each expansion and change of map structure */
transient int modCount;
/** Capacity expansion critical value: when the number of stored elements exceeds the critical value (capacity * load factor), capacity expansion will be carried out */
int threshold;
/** Hash table load factor */
final float loadFactor;Data structure for storing elements
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}Constructor
1. Custom capacity and load factors
2. Custom capacity, default load factor 0.75
3. Default capacity 16, default load factor 0.75
4. Pass in a map
/**
* Constructor specifying capacity size and load factor
* @param initialCapacity capacity
* @param loadFactor Load factor
*/
public HashMap(int initialCapacity, float loadFactor) {
// Judge whether the initialization capacity initialCapacity is less than 0. If it is less than 0, an illegal parameter exception IllegalArgumentException will be thrown
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// Judge whether the initialization capacity is greater than the maximum capacity of the set_ Capability, if yes, the maximum value is used
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// Judge whether the load factor loadFactor is less than or equal to 0 or whether it is a non numeric value
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Assign the specified load factor to the load factor loadFactor of the HashMap member variable
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Formulate the constructor of capacity size. The default load factor of 0.75 is used
* @param initialCapacity Capacity
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructor using default capacity 16 and default load factor 0.75
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
Construct a new HashMap whose mapping is the same as the specified map.
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}The above 1, 2 and 3 construction methods will call the following methods
/**
* Returns the n-th power of the smallest 2 larger than the specified initialization capacity,
* For example, if the specified capacity is 11, return 16
*/
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;
}If the customized capacity is greater than the 30th power of 2, the capacity defaults to the 30th power of 2; If the customized capacity is not the n-th power of 2, the capacity is changed to the n-th power of the closest customized 2 that is greater than the customized capacity, for example,
/** The actual capacity is 16 */ Map<String, String> map = new HashMap<>(11);
put operation
Steps:
1. First, hash the key to get the subscript of the bucket to be stored
2. Judge whether there is value on the bucket. If not, store it directly; If yes, a hash conflict was encountered:
a. judge whether the key to be inserted is consistent with the conflicting key value. If so, update the value;
b. judge whether the conflicting node of the bucket is a TreeNode (red black tree structure). If so, call the insertion method putTreeNode() of the red black tree
c. the last case is that the conflict node uses the linked list structure to cycle through the linked list. If there is the same key, update the value. If not, insert the node at the end; Judge whether the length of the linked list is greater than or equal to 8. If so, call the method treeifyBin converted into red black tree. In this method, the length of the array will be checked. If it is less than MIN_TREEIFY_CAPACITY=64 will expand the capacity of the array, so it does not necessarily turn into a red black tree.
3. If the size is greater than the threshold (capacity * load factor), expand the capacity;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Judge whether the collection is newly created, that is, the tab is null
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Calculate whether an element already exists at the node location. If it exists, it indicates that there is a collision conflict. If not, insert the element directly into the location
// Save the existing bucket data to the variable p
if ((p = tab[i = (n - 1) & hash]) == null)
// Create a new node and store it in the bucket
tab[i] = newNode(hash, key, value, null);
// Execute else to explain that tab[i] is not equal to null, indicating that this location already has a value
else {
Node<K,V> e; K k;
// 1. The element hash values are equal, but it cannot be determined that they are the same value
// 2. Whether the key is the same instance or whether the values are equal
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// Note: the hash values of the two elements are equal, and the value of the key is also equal. Assign the whole object of the old element to e and record it with E
e = p;
// If the hash values are not equal or the key s are not equal; Judge whether p is a red black tree node
else if (p instanceof TreeNode)
// Put it in the tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// Description is a linked list node
// 1) If it is a linked list, you need to traverse to the last node and insert it
// 2) Loop traversal is used to judge whether there are duplicate key s in the linked list
else {
for (int binCount = 0; ; ++binCount) {
// Determine whether p.next reaches the tail of the linked list
// Take out p.next and assign it to e
if ((e = p.next) == null) {
// Insert the node into the tail of the linked list
p.next = newNode(hash, key, value, null);
// Judge whether the critical condition for converting to red black tree is met. If so, call treeifyBin to convert to red black tree
// Note: the treeifyBin method will check the array length if it is less than min_ TREEIFY_ Capability will expand the capacity of the array
if (binCount >= TREEIFY_THRESHOLD - 1)
// Although the judgment here is 7 > = 7, because binCount starts from 0, it has been inserted at the eighth node
// Convert to red black tree
treeifyBin(tab, hash);
// Jump out of loop
break;
}
// If the end of the linked list is not reached, judge whether the key value is the same
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// If the key s are equal, the loop jumps out
break;
// It indicates that the newly added element is not equal to the current node. Continue to find the next node.
// Used to traverse the linked list in the bucket. Combined with the previous e = p.next, you can traverse the linked list
p = e;
}
}
// Indicates that a node whose key value and hash value are equal to the inserted element is found in the bucket
// That is to say, a duplicate key is found through the above operation, so here is to change the value of the key into a new value and return the old value
// The modification function of put method is completed here
if (e != null) { // existing mapping for key
// Record the value of e
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// Update value
e.value = value;
// Post access callback
afterNodeAccess(e);
// Return old value
return oldValue;
}
}
// Record modification times
++modCount;
// Judge whether the actual size is greater than the threshold. If it exceeds the threshold, expand the capacity
if (++size > threshold)
// Capacity expansion
resize();
// Post insert callback
afterNodeInsertion(evict);
return null;
}Operation of hash value
/**
* Returns the hash value of the key
*/
static final int hash(Object key) {
int h;
/*
1)If key equals null: the returned value is 0
2)If the key is not equal to null: first calculate the hashCode of the key, assign it to h, and then move it 16 bits to the right without sign with H
Perform bitwise XOR on binary to get the final hash value
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}putTreeNode()
Find the root node first, and then judge whether to find the key from the left or the right.
If found, the found node will be returned directly.
If it is not found, create a new node, put the new node in the appropriate position, and consider the node insertion of red black tree and two-way linked list.
/**
* Node insertion of red black tree
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null; // class object defining k
boolean searched = false; // Indicates whether the tree has been traversed once, not necessarily from the root node
TreeNode<K,V> root = (parent != null) ? root() : this; // If the parent node is not empty, find the root node. If it is empty, it is the root node itself
// The traversal starts from the root node and has no termination conditions. You can only exit from the inside
for (TreeNode<K,V> p = root;;) {
// Declare the search direction, the hash value of the current node, and the current node
int dir, ph; K pk;
if ((ph = p.hash) > h) // If the hash value of the current node is greater than the hash value of the specified key
dir = -1; // The node to be inserted should be to the left of the current node
else if (ph < h) // If the hash value of the current node is less than the hash value of the specified key
dir = 1; // The node to be inserted should be to the right of the current node
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // If the hash value and key of the current node are the same as the specified key
return p; // Return to this node
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}flow chart
get operation
Steps:
1. Calculate the hash value of the key to be queried. If the bucket corresponding to the hash is empty, null is returned;
2. If the bucket is not empty, judge whether the key to be queried is equal to the bucket key. If equal, return the elements in the bucket;
If not, judge whether the bucket has the next node. If not, return null;
3. If there is a next node, judge whether the bucket node is a red black tree node. If so, call the method getTreeNode() of the red black tree to get the node and return the node to be queried; If it is not a red black tree node, it is a linked list node. Traverse the linked list and return the node to be queried.
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// If the hash table is not empty and the bucket corresponding to the key is not empty
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// Determine whether the array elements are equal
// Check the position of the first element according to the index
// Note: always check the first element
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// If the array is not the element to be found, judge whether there is the next node at that position
if ((e = first.next) != null) {
// The next node is the red black tree node
if (first instanceof TreeNode)
// Judge whether it is a red black tree. If yes, call the getTreeNode method in the red black tree to obtain the node
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// Linked list node, loop through the linked list
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}getTreeNode()
Get the root node, left node and right node first.
Search the data step by step according to the left node < root node < right node.
If the Comparable method is implemented, it is directly compared.
Otherwise, if the root node does not match, the find lookup function will be called recursively
final TreeNode<K,V> getTreeNode(int h, Object k) {
// Call the root() method to get the root node, and then search the red black tree
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* Get the root node of red black tree
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
// Root node
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
// Check left or right according to the hash value
if ((ph = p.hash) > h)
p = pl;
else if (ph < h) // Check left or right according to the hash value
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // If the key and hash values of this node are the same as those to be checked
return p; // Return to this node
else if (pl == null) // If the left is empty, traverse the right
p = pr;
else if (pr == null) // The right side is empty, and the left side is traversed
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}remove operation
Steps:
1. Calculate the hash value of the key to be deleted, which is similar to the get operation to obtain the node to be deleted
2. After obtaining the node to be deleted, judge the type of the node:
If it is a bucket element, the deletion method is to assign the next node of the bucket to the bucket
If it is a red black tree node, call the red black tree removeTreeNode method to delete the node
If it is a linked list node, delete the node according to the non head node deletion method of the linked list
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;
// Find the location according to the hash
// If the bucket mapped to the current key is not empty
// Assign the element corresponding to the bucket to traversal p
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 node on the bucket is the key to be found, point the node to the node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// Indicates that the node has a next node
else if ((e = p.next) != null) {
// Note: if the conflict is handled by the red black tree, obtain the node to be deleted by the red black tree
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// Judge whether to handle hash conflicts in the way of linked list. If yes, traverse the linked list to find the node to be deleted
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// Compare whether the value of the found key matches the one to be deleted
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// Delete the node by calling the method of red black tree
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// Array deletion
tab[index] = node.next;
else
// Linked list deletion
p.next = node.next;
// Record modification times
++modCount;
// Number of changes
--size;
// Callback
afterNodeRemoval(node);
return node;
}
}
return null;
}resize() capacity expansion
Each capacity expansion is doubled. Compared with the original (n - 1) - hash result, there is only one bit more, so the node is either in the original position or assigned to the position of "original position + old capacity".
Therefore, during HashMap capacity expansion, you do not need to recalculate the hash. You only need to see whether the new bit of the original hash value is 1 or 0. If it is 0, the index remains unchanged, and if it is 1, the index becomes "original location + old capacity"
Steps:
1. Get the old table data. If the old table is large enough, it will not be expanded, and only the threshold will be adjusted.
2. The expanded range of the old table also meets the requirements, and the container size and threshold are directly expanded.
3. If it is a constructor with parameters, you need to copy the threshold to the container capacity.
4. Otherwise, it is considered that the container has not passed parameters during initialization and needs to be initialized.
5. If the old table has data, the new one changes size and is set, but the threshold is not set successfully. At this point, set a new threshold.
6. Create a new container.
7. The successful expansion of the old table to the new one involves data transfer.
If the data is not empty and is a separate node, the new location will be directly re hash ed.
If the data is not empty, followed by a linked list, you should distinguish the linked list data to see which are assigned to the old place and which are assigned to the new place.
If the node type is a red black tree, call split
/**
* Each capacity expansion is doubled. Compared with the original (n - 1) - hash result, there is only one bit more, so the node is either in the original position or assigned to the position of "original position + old capacity".
* Therefore, during HashMap capacity expansion, you do not need to recalculate the hash. You only need to see whether the new bit of the original hash value is 1 or 0. If it is 0, the index remains unchanged, and if it is 1, the index becomes "original location + old capacity"
* @return the table
*/
final Node<K,V>[] resize() {
// Get the current array
Node<K,V>[] oldTab = table;
// Returns 0 if the current array is equal to null length, otherwise returns the length of the current array
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// The current threshold value is 12 (16 * 0.75) by default
int oldThr = threshold;
int newCap, newThr = 0;
// If the length of the old array is greater than 0, start to calculate the size after capacity expansion
// Less than or equal to 0, there is no need to expand the capacity
if (oldCap > 0) {
// If you exceed the maximum value, you won't expand any more, so you have to collide with you
if (oldCap >= MAXIMUM_CAPACITY) {
// Modify the threshold to the maximum value of int
threshold = Integer.MAX_VALUE;
return oldTab;
}
// The capacity is expanded by 2 times
// The new capacity cannot exceed the size of 2 ^ 30
// The original capacity is greater than or equal to initialization DEFAULT_INITIAL_CAPACITY=16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// Double the threshold
newThr = oldThr << 1; // double threshold
}
// If the original capacity is less than or equal to 0 and the original threshold point is greater than 0
else if (oldThr > 0) // initial capacity was placed in threshold
// The original threshold is assigned to the new array length
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// If it is not satisfied, the default value is used directly
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// If the original capacity is less than or equal to 0 and the original threshold point is greater than 0, then newThr is 0
// Calculate the new resize maximum upper limit
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// The default value of the new threshold is 12 times 2 and then becomes 24
threshold = newThr;
// Create a new hash table
@SuppressWarnings({"rawtypes","unchecked"})
//newCap is the new array length
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// The original array is not empty
if (oldTab != null) {
// Move each bucket into a new bucket
// Traverse each bucket of the original hash table and recalculate the new position of the elements in the bucket
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// The original data is assigned null to facilitate GC recycling
oldTab[j] = null;
// Determine whether the array has the next reference
if (e.next == null)
// There is no next reference, indicating that it is not a linked list. There is only one key value pair on the current bucket, which can be inserted directly
newTab[e.hash & (newCap - 1)] = e;
// Judge whether it is a red black tree
else if (e instanceof TreeNode)
// If the description is a red black tree to handle the conflict, call relevant methods to separate the tree
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// Using linked list to deal with conflicts
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// Calculate the new position of the node through the principle explained above
do {
next = e.next;
// Here we judge that if it is equal to true e, the node does not need to move its position after resizing
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}
Turn linked list into red black tree treeifyBin()
Before the linked list is converted into a red black tree, even if the threshold is greater than 8, but the array length is less than 64, the linked list will not be changed into a red black tree, but the capacity of the array will be expanded.
The purpose is: when the array is small, try to avoid the red black tree structure. In the case of red trees, the efficiency of these operations will be reduced because the red trees will become black. At the same time, when the array length is less than 64, the search time is relatively faster. Therefore, as mentioned above, in order to improve performance, the linked list is converted into a red black tree only when the underlying threshold is greater than 8 and the array length is greater than 64
/**
* Convert the linked list into a red black tree
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// If the current array is empty or the length of the array is less than the threshold for tree formation (min_tree_capability = 64), expand the capacity.
// Instead of turning the node into a red black tree.
// Objective: if the array is very small, it is less efficient to convert the red black tree and traverse it.
// At this time, if the capacity is expanded, the hash value will be recalculated, the length of the linked list may be shortened, and the data will be put into the array, which is relatively more efficient.
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// Capacity expansion
resize();
// Get the bucket element of the key hash value and judge whether it is empty
else if ((e = tab[index = (n - 1) & hash]) != null) {
// Perform steps
// 1. First convert the element into a red black tree node
// 2. Then set it as a linked list structure
// 3. Finally, the linked list structure is transformed into a red black tree
// hd: head node of red black tree tl: tail node of red black tree
TreeNode<K,V> hd = null, tl = null;
do {
// Replace the current bucket node with a red black tree node
TreeNode<K,V> p = replacementTreeNode(e, null);
// For the first operation, the red black tree tail node is empty
if (tl == null)
// Assign the p node of the newly created key to the head node of the red black tree
hd = p;
else {
p.prev = tl; // Assign the previous node p to the previous node of the current P
tl.next = p; // Take the current node p as the next node of the tail node of the tree
}
tl = p;
// Until the loop reaches the end of the linked list, and the linked list elements are replaced with red black tree nodes
} while ((e = e.next) != null);
// Let the first element in the bucket, that is, the element in the array, point to the node of the new red black tree,
// In the future, the elements in this bucket are red and black trees instead of linked list data structures
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
/**
* Turn the linked list into a red black tree
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// Traverse each TreeNode in the linked list. The current node is x
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//For the first tree node, the root of the current red black tree = = null, so the first node is the root of the tree and is set to black
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//Traverse from the root node to find the insertion position of the current node x
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) //If the hash value of the current node is less than the hash value of the root node, the direction dir = -1;
dir = -1;
else if (ph < h) //If the hash value of the current node is greater than the hash value of the root node, the direction dir = 1;
dir = 1;
//If the key of node X does not implement the comparable interface, or its key is equal to the key of the root node (k.compareTo(x) == 0), the arbitration insertion rule
//Only when the type K of K directly implements the comparable < k > interface, can it return the class of K. otherwise, null will be returned, and indirect implementation will not work.
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//Arbitration insertion rules
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { //If the left and right nodes of p are not null, continue the for loop, otherwise execute the insertion
x.parent = xp;
if (dir <= 0) //Dir < = 0, insert to left node
xp.left = x;
else //Otherwise, it is inserted into the right node
xp.right = x;
//Adjust the tree after insertion to make it conform to the nature of red black tree
root = balanceInsertion(root, x);
break;
}
}
}
}
// Point the bucket element node to the root node of the red black tree
moveRootToFront(tab, root);
}Red black tree into linked list untreeify
/**
* Turn the red black tree into a linked list, and the number of nodes < = 6 will trigger
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null; // hd points to the head node and tl points to the tail node
for (Node<K,V> q = this; q != null; q = q.next) {// The structure of red black tree and two-way linked list coexist. Here, the chain header node starts to traverse
Node<K,V> p = map.replacementNode(q, null); // Convert each node into a linked list node
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
// Returns the head node of the converted linked list
return hd;
}problem
1. Under what circumstances may the capacity be expanded
When put, putAll, and parameter passing are map s
2. Under what circumstances does the linked list turn into a red black tree
When the number of nodes > = 8 and the array length is greater than 64
3. When will the red and black tree turn into a linked list
When deleting a tree node or expanding capacity, it may
4. Finding the point to be inserted in JDK8 is through = = tail interpolation = = (similar to queuing at the back), while in JDK7 is = = front interpolation = = (similar to plugging at the front. The reason for this is that HashMap inventors believe that the rear insertion section has a higher probability of being accessed)