HashMap source code analysis
Based on the JDK1.8
Data Structure
1.1 Important Variables
-
/** * The default initial capacity is 16 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; /** * The maximum capacity is 2 ^ 30 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * Default load factor */ static final float DEFAULT_LOAD_FACTOR = 0.75 f; /** * Tree when the number of elements in a bucket is greater than or equal to 8 */ static final int TREEIFY_THRESHOLD = 8; /** * Convert the tree to a linked list */ when the number of elements in a bucket is less than or equal to 6 static final int UNTREEIFY_THRESHOLD = 6; /** * Tree only when the number of buckets reaches 64 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * array, also called bucket */ transient Node<K,V>[] table; /** * as a cache for entrySet() */ transient Set<Map.Entry<K,V>> entrySet; /** * The number of elements */ transient int size; /** * The number of modifications used to execute the fast failure policy during iteration */ transient int modCount; /** * Expand the capacity when the number of buckets in use reaches the threshold = capacity * loadFactor */ int threshold; /** * load factor */ final float loadFactor; Copy the code
Matters needing attention
(1) Capacity
The capacity is the length of the array, that is, the number of buckets. The default value is 16, and the maximum value is 2 to the power of 30. When the capacity reaches 64, it can be treed.Copy the code(2) Loading factor
The load factor is used to calculate the capacity to be expanded. The default load factor is 0.75.Copy the code(3) Treification
Tree, when the capacity reaches 64 and the length of the list reaches 8 tree, when the length of the list is less than 6 tree.Copy the codeSource code analysis
2.1 HashMap class annotation parsing
- Allowing null values, unlike HashTable, is thread-unsafe;
- The default value of load factor is 0.75, which is calculated by balancing the time and space consumption. A higher value will reduce the space overhead (reduced expansion, slower growth of array size), but increase the search cost (increased hash collisions, longer list length). The conditions for no expansion are as follows: Group size > array size required /load factor;
- If a large amount of data needs to be stored in a HashMap, it is recommended that the capacity of the HashMap be set to a sufficient size at the beginning to prevent the continuous expansion of the HashMap from affecting performance.
- HashMap is not thread-safe. We can use external locking ourselves or thread security via Collections#synchronizedMap. SynchronizedMap is implemented by adding a synchronized lock to each method;
- During iteration, if the structure of the HashMap is modified, it will quickly fail.
2.2 the inner class
2.2.1 Node
Node is a single-linked list Node where the hash is used to store the hash value computed by the key.
static class Node<K.V> implements Map.Entry<K.V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
Copy the code2.2.2 TreeNode inner Class
Inherits the Entry class from the LinkedHashMap
A TreeNode is a TreeNode, where a prev is a node in a linked list that can be used to quickly find the preceding node when an element is deleted.
// in a HashMap
static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
TreeNode<K,V> parent; // Red black tree node
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // It is used to quickly find the leading node of an element when it is deleted.
boolean red;
}
// In the LinkedHashMap, the bidirectional list node
static class Entry<K.V> extends HashMap.Node<K.V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next); }}Copy the code2.3 a HashMap () structure
2.3.1 Empty parameter constructor, all use default values.
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
Copy the code2.3.2 HashMap(int initialCapacity) constructor
Call the HashMap(int initialCapacity, float loadFactor) constructor, passing in the default loadFactor.
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the code2.3.3 HashMap(int initialCapacity, float loadFactor) constructor
Determine whether the incoming initial capacity and the loading factor are legal, and calculate the expansion threshold, which is the nearest 2 to the n power of the incoming initial capacity.
public HashMap(int initialCapacity, float loadFactor) {
// Check whether the incoming initial capacity is valid
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// Check whether the load factor is valid
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// Calculate the capacity expansion threshold
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
// The threshold for expansion is the nearest 2 to the NTH power from the incoming initial capacity
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;
}
Copy the code2.4 new
The procedure for adding a key and value is as follows:
- Whether the empty array is initialized or not
- If the hash of the key can be found directly, go to 6; otherwise, go to 3;
- If hash conflicts, there are two solutions: linked lists or red-black trees;
- If it’s a linked list, recurse, append new elements to the end of the queue;
- If it is a red-black tree, call the method added to the red-black tree.
- Perform 2, 4, and 5 to add the new element successfully, and then determine whether the new element needs to be overwritten according to onlyIfAbsent.
- Determine whether to expand the capacity. Expand the capacity.
Against 2.4.1 put method
public V put(K key, V value) {
// Call hash(key) to compute the hash value of the key
return putVal(hash(key), key, value, false.true);
}
static final int hash(Object key) {
int h;
// If the key is null, the hash value is 0, otherwise the key's hashCode() method is called
// And make the top 16 bits xor with the entire hash to make the calculated hash more diffuse
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
/ * * *@paramHash Indicates the value calculated using the hash algorithm *@paramThe key key *@paramThe value value *@paramOnlyIfAbsent False Indicates that the new value overwrites the original value even if the key already exists. The default value is false *@paramIf evict is false, the table is in create 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 number of buckets is 0, initialize
if ((tab = table) == null || (n = tab.length) == 0)
// Call resize() to initialize
n = (tab = resize()).length;
// (n-1) &hash which bucket the element is in
// If there is no element in the bucket, place the element at the first position in the bucket
if ((p = tab[i = (n - 1) & hash]) == null)
// Create a new node and place it in the bucket
tab[i] = newNode(hash, key, value, null);
else {
// If there are already elements in the bucket
Node<K, V> e;
K k;
// If the key of the first element in the bucket is the same as that of the element to be inserted, save it to e for subsequent modification of value
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
If the first element is a tree node, putTreeVal of the tree node is called to insert the element
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// Iterate over the bucket's linked list. BinCount is used to store the number of elements in the list
for (int binCount = 0; ; ++binCount) {
// Insert a new node at the end of the list if there is no element with the same key
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// If the length of the list is greater than 8 after inserting a new node, then check whether the list needs to be treed, because the first element was not added to binCount, so -1
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// If the key to insert is found in the linked list, exit the loop
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// If the element corresponding to key is found
if(e ! =null) { // existing mapping for key
// Record the old value
V oldValue = e.value;
// Determine whether the old value needs to be replaced
if(! onlyIfAbsent || oldValue ==null)
// Replace the old value with the new value
e.value = value;
// Do something after the node is accessed, as used in LinkedHashMap
afterNodeAccess(e);
// Return the old value
returnoldValue; }}// The element is not found
// The number of changes is increased by 1
++modCount;
// Increase the number of elements by 1 to determine whether expansion is required
if (++size > threshold)
/ / capacity
resize();
// What do I do after the node is inserted, used in LinkedHashMap
afterNodeInsertion(evict);
// Return null if no element is found
return null;
}
Copy the code2.4.2 the resize () method
final Node<K, V>[] resize() {
/ / the old array
Node<K, V>[] oldTab = table;
/ / the old capacity
int oldCap = (oldTab == null)?0 : oldTab.length;
// Old capacity expansion threshold
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// If the old capacity reaches the maximum capacity, the capacity will not be expanded
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// If two times of the old capacity is less than the maximum capacity and the old capacity is greater than the default initial capacity (16), the capacity is expanded by two times and the threshold for expansion is also increased by two times
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
// Map created using a non-default constructor, the first insert will go here
// If the old capacity is 0 and the old threshold is greater than 0, the new capacity is assigned to the old threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// Call the map created by the default constructor, where the first element is inserted
// If the threshold of the old capacity is 0, it indicates that the capacity has not been initialized. In this case, the initial capacity is the default capacity, and the threshold is the default capacity x default load factor
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// If the new capacity threshold is 0, the capacity x load factor is calculated, but cannot exceed the maximum capacity
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
// Set the expansion threshold to a new threshold
threshold = newThr;
// Create an array of new capacity
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
// Assign buckets to new arrays
table = newTab;
// If the old array is not empty, move the element
if(oldTab ! =null) {
// Iterate over the old array
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
// If the first element in the bucket is not empty, assign e
if((e = oldTab[j]) ! =null) {
// Empty old buckets for GC collection
oldTab[j] = null;
// If there is only one element in the bucket, calculate its position in the new bucket and move it to the new bucket
// Since it doubles each time, the first element must be moved to the new bucket when the new bucket has no element
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// If the first element is a tree node, split the tree into two trees and insert them into the new bucket
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
// If the list has more than one element and is not a tree
// Split into two linked lists and insert them into a new bucket
// for example, if the original capacity is 4,3, 7, 11, 15, all four elements are in bucket 3
// Now that we have expanded to 8, 3 and 11 will still be in bucket 3, 7 and 15 will be moved to bucket 7
// Split into two linked lists
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
next = e.next;
// (e.hash & oldCap) == 0 in the low level list
// For example, 3&4 == 0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
// (e.hash & oldCap) ! The elements that are equal to 0 are placed in the higher-order list
// For example, 7&4! = 0
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
// The traversal has split into two lists
// The position of the low list in the new bucket is the same as in the old bucket (i.e. 3 and 11 are still in bucket 3).
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
// The position of the high list in the new bucket is exactly the same as the old position plus the old capacity (that is, 7 and 15 moved to the 7 bucket)
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the code(1) If the default constructor is used, the default value is initialized when the element is inserted for the first time, the capacity is 16, and the expansion threshold is 12;
(2) If the non-default constructor is used, the initial capacity on the first insertion is equal to the expansion threshold, which in the constructor is equal to the nearest power of 2 to the n of the incoming capacity;
(3) If the old capacity is greater than 0, the new capacity is equal to twice the old capacity, but not more than the maximum capacity 2 ^ 30, and the threshold for new capacity expansion is twice the threshold of the old capacity expansion;
(4) Create a bucket with a new capacity;
(5) Move elements. The original linked list is divided into two linked lists. The low linked list is stored in the location of the original bucket, and the high linked list is moved to the location of the original bucket plus the location of the old capacity;
2.4.3 New linked list
To add a LinkedList, append the current node to the end of the list in the same way as to append LinkedList. When the length of the linked list is greater than or equal to 8, the linked list will be transformed into a red-black tree by the following method: TreeifyBin, this method has a check, when the list length is greater than or equal to 8, and the entire array size is greater than 64, will be converted to a red black tree, when the array size is smaller than 64, will only trigger expansion, will not be converted to a red black tree, why 8, linked list query time complexity is O (n), The query complexity of red-black trees is O (log (n)). When the linked list data is not large, the traversal using the linked list is also faster. Only when the linked list data is large, it will be converted into a red-black tree, but the red-black tree takes up twice the space of the linked list. Considering the conversion time and space loss, we need to define the conversion boundary value. When considering the value of design 8, we refer to the Probability function of Poisson distribution, from which we conclude that the hit probability of each length of the linked list is: When the length of the linked list is 8, the probability of occurrence is 0.00000006, which is less than one in ten million. Therefore, under normal circumstances, the length of the linked list cannot reach 8, and once it reaches 8, there must be something wrong with the hash algorithm, so in this case, In order for HashMap to still have high query performance, we convert the list to a red-black tree. When we use HashMap in normal code, we almost never encounter the list to a red-black tree, because the concept is only one in ten million.
2.4.4 Process of adding nodes to a red-black tree
First, check whether the new node already exists in the red-black tree by the following two methods:
1.1. If the node does not implement the Comparable interface, use equals to determine;
1.2. If the node implements the Comparable interface itself, use compareTo to determine.
If the newly added node is already in the red-black tree, the node is returned directly. If not, determine whether the new node is to the left or right of the current node. The left value is small and the right value is large.
Spin recursion steps 1 and 2, until the node on the left or right of the current node is empty, stop spin, the current node is the parent node of our new node;
Place the new node to an empty place on the left or right of the current node, and establish a parent-child node relationship with the current node.
Color and rotate, end.
The specific source code is as follows:
Method of inserting elements into a 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;
// Flag whether the node for this key is found
boolean searched = false;
// Find the root of the treeTreeNode<K, V> root = (parent ! =null)? root() :this;
// Start at the root of the tree
for(TreeNode<K, V> p = root; ;) {// dir=direction, the flag is left or right
// ph=p.hash, the hash value of the current node
int dir, ph;
// pk=p.key, the key value of the current node
K pk;
if ((ph = p.hash) > h) {
// The current hash is larger than the target hash, indicating that it is on the left
dir = -1;
}
else if (ph < h)
// The current hash is smaller than the target hash, indicating that it is on the right
dir = 1;
else if((pk = p.key) == k || (k ! =null && k.equals(pk)))
// If the hash and key are the same, the node is found
// Go back to putVal() to see if you need to change its value
return p;
else if ((kc == null &&
// Return the true class if k is a Comparable subclass, otherwise null
(kc = comparableClassFor(k)) == null) | |Return 0 if k and PK are not of the same type, otherwise return the result of the comparison between the two
(dir = compareComparables(kc, k, pk)) == 0) {
// This condition means that both hashes are the same but one of them is not Comparable or that they are of different types
For example, if the key is of Object type, you can pass either String or Integer, which may have the same hash value
// Store elements with the same hash value in the same subtree in a red-black tree. This is equivalent to finding the vertices of the subtree
// Traverse the left and right subtrees of the vertex to see if there are any elements that are the same as the key to be inserted
if(! searched) { TreeNode<K, V> q, ch; searched =true;
// If the left and right subtrees are found, return directly
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;
}
// If the two types are the same, the hash value is calculated based on their memory addresses for comparison
dir = tieBreakOrder(k, pk);
}
TreeNode<K, V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
// If no element corresponding to the key is found, a new node is created
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;
// Rebalance after inserting tree nodes
// Move the root node to the first node in the list
moveRootToFront(tab, balanceInsertion(root, x));
return null; }}}Copy the codeThe five principles of red-black trees:
- Nodes are red or black
- The root is black
- All the leaves are black
- All simple paths from any node to each of its leaves contain the same number of black nodes
- There cannot be two consecutive red nodes on all paths from each leaf to the root
2.5 find
The search for HashMap is divided into the following three steps:
- Based on the hash algorithm, equals determines whether the current node is the key we are looking for. If so, equals returns the key. If not, equals returns the key.
- Check whether the current node has a next node. If so, check whether it is a linked list or a red-black tree.
- Different types of lookups for linked lists and red-black trees respectively.
2.5.1 Get (Object Key) Method
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;
// If the number of buckets is greater than 0 and the first element of the bucket where the key is located is not empty
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
// Check whether the first element is the element to look up, if it is directly returned
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
// If the first element is a tree node, look it up as a tree
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
// Otherwise, the list is traversed to find the element
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the code(1) Compute the hash value of the key.
(2) Find the bucket where the key is and its first element;
(3) If the key of the first element is equal to the key to be searched, return it directly;
(4) If the first element is a tree node, search in tree mode; otherwise, search in linked list mode;
2.5.2 treenode.getTreenode (int h, Object k) method
final TreeNode<K, V> getTreeNode(int h, Object k) {
// Start at the root of the tree
return((parent ! =null)? root() :this).find(h, k, null);
}
final TreeNode<K, V> find(inth, Object k, Class<? > kc) {
TreeNode<K, V> p = this;
do {
int ph, dir;
K pk;
TreeNode<K, V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
/ / the left subtree
p = pl;
else if (ph < h)
/ / right subtree
p = pr;
else if((pk = p.key) == k || (k ! =null && k.equals(pk)))
// If found, return directly
return p;
else if (pl == null)
// The hash is the same but the key is different. Search the right subtree if the left subtree is empty
p = pr;
else if (pr == null)
// If the right subtree is empty, check the left subtree
p = pl;
else if((kc ! =null|| (kc = comparableClassFor(k)) ! =null) && (dir = compareComparables(kc, k, pk)) ! =0)
// Use the left or right subtree to compare key values
p = (dir < 0)? pl : pr;else if((q = pr.find(h, k, kc)) ! =null)
// If none of the above conditions pass, try searching in the right subtree
return q;
else
// Search the left subtree
p = pl;
} while(p ! =null);
return null;
}
Copy the codeIn the search process of the classical binary search tree, the search process is determined by comparing the hash value first and then the key value.
2.6 delete
2.6.1 Remove (Object Key) Method
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;
// If the number of buckets is greater than 0 and the first element of the bucket in which the element is to be deleted is not empty
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(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// If the first element is exactly what you are looking for, assign it to the node variable for subsequent deletion
node = p;
else if((e = p.next) ! =null) {
if (p instanceof TreeNode)
// If the first element is a tree node, the node is found as a tree
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else {
// Otherwise walk through the list looking for elements
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 the element is found, the argument needs to match the value, if it does not need to match the value is deleted, if it needs to match the value is equal to the value passed in
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
if (node instanceof TreeNode)
// If it is a tree node, the tree deletion method is called.
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
else if (node == p)
// If the element to be deleted is the first, move the second element to the first position
tab[index] = node.next;
else
// Otherwise, delete the node node
p.next = node.next;
++modCount;
--size;
// Delete the node
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the code(1) First find the node where the element is;
(2) If the node found is a tree node, it is processed as the removed node of the tree;
(3) If the node found is the first node in the bucket, move the second node to the first position;
(4) Otherwise, delete nodes according to the linked list;
(5) Modify size, invoke post-removal of node, etc.;
2.6.2 TreeNode. RemoveTreeNode (…). methods
final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,
boolean movable) {
int n;
// Return if the number of buckets is 0
if (tab == null || (n = tab.length) == 0)
return;
// The index of the node in the bucket
int index = (n - 1) & hash;
// The first node, the root node, the root left child node
TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
// Next node, front node
TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;
if (pred == null)
// If the front node is empty, the current node is the root node, and the subsequent node is assigned to the position of the first node, which is equivalent to deleting the current node
tab[index] = first = succ;
else
// Otherwise, if the next node of the front node is set to the successor node of the current node, the current node is deleted
pred.next = succ;
// If the successor node is not empty, the front node of the successor node points to the front node of the current node, which is equivalent to deleting the current node
if(succ ! =null)
succ.prev = pred;
// If the first node is empty, there are no subsequent nodes
if (first == null)
return;
// If the parent of the root node is not empty, find the parent again
if(root.parent ! =null)
root = root.root();
// If the root node is empty, you need to de-tree (turn the tree into a linked list)
// If you need to move nodes and the height of the tree is small, you need to de-tree
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode is a linked list node and a TreeNode. TreeNode is a linked list node and a TreeNode. TreeNode is a TreeNode.
// The general process of deleting a red-black tree node is to find the smallest node in the right subtree and put it at the location of the deleted node, and then balance it
TreeNode<K, V> p = this, pl = left, pr = right, replacement;
if(pl ! =null&& pr ! =null) {
TreeNode<K, V> s = pr, sl;
while((sl = s.left) ! =null) // find successor
s = sl;
boolean c = s.red;
s.red = p.red;
p.red = c; // swap colors
TreeNode<K, V> sr = s.right;
TreeNode<K, V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
} else {
TreeNode<K, V> sp = s.parent;
if((p.parent = sp) ! =null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if((s.right = pr) ! =null)
pr.parent = s;
}
p.left = null;
if((p.right = sr) ! =null)
sr.parent = p;
if((s.left = pl) ! =null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if(sr ! =null)
replacement = sr;
else
replacement = p;
} else if(pl ! =null)
replacement = pl;
else if(pr ! =null)
replacement = pr;
else
replacement = p;
if(replacement ! = p) { TreeNode<K, V> pp = replacement.parent = p.parent;if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K, V> pp = p.parent;
p.parent = null;
if(pp ! =null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null; }}if (movable)
moveRootToFront(tab, r);
}
Copy the code(1) TreeNode itself is both a linked list node and a red-black TreeNode;
(2) Delete the linked list node first;
(3) Delete the red-black tree node and balance it;
Time complexity
The query efficiency of array is O(1), the query efficiency of linked list is O(k), and the query efficiency of red-black tree is O(log K), where K is the number of elements in the bucket. Therefore, when the number of elements is very large, converting to red-black tree can greatly improve the efficiency.
Four. Thread safety
4.1 Thread safety Causes Occur
If you have two threads, A and B, and they both insert data, it just so happens that the hash code for these two different data is the same, and there’s no other data at that location. So both of these threads are going to go into the code that I marked 1 above. Assume A situation in which, thread A pass if judgment, this position does not have the hash conflict, entered the if statement, not insert data, then CPU resources to the thread B, thread A stop in the if statement, thread B judging the location without hash conflict (thread A haven’t insert), also entered the if statement, thread B after the execution, It’s thread A’s turn to do it, and now thread A inserts directly at that location without any judgment. At this point, you will notice that thread A overwrites the data inserted by thread B. A thread unsafe condition has occurred. In a HashMap, hash collisions can be resolved using linked lists or red-black trees, but in multithreading, they can be overridden.
4.2 Solutions
2 ConcurrentHashMap
- Without synchronizing the entire Map, it is still thread-safe
- The read operation is very fast, while the write operation is done by locking
- There are no locks at the object level (that is, no threads are blocked)
- The granularity of the lock is set very well. Only one key in the hash table is locked
ConcurrentHashMapDon’t throwConcurrentModificationException, even if one thread is traversing while another thread is trying to make changes.ConcurrentHashMapMultiple locks will be used- A null key is not allowed
4.2.2 SynchronizedHashMap
- The entire object is synchronized
- Every read/write operation needs to be locked
- Locking the entire object greatly degrades performance
- This is equivalent to allowing at most one thread to operate on the entire Map at a time, while the other threads must wait
- It can cause resource conflicts (some threads wait a long time)
SynchronizedHashMapReturns theIterator, will throw an exception when traversal changes- Key null is allowed
5 Recommended Reading
The network of the most core source analysis – String source analysis
The Spring Boot automatic configuration principle is fully explained with diagrams
MySQL 3 large log function
The most core source code analysis of the entire web – ArrayList source code analysis
If you feel helpful, I hope you can pay attention to it, click a “like” and then go, thank you for reading. Markdown, PDF format can be obtained from the public account