Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
Introduction to the
HashMap uses key/value storage structure, and each key corresponds to a unique value. The speed of query and modification is fast, reaching O(1) average time complexity. It is non-thread-safe and does not guarantee the order in which elements are stored;
Inheritance system
HashMap implements Cloneable and can be cloned.
HashMap implements Serializable, which can be serialized.
AbstractMap HashMap inherits AbstractMap, implements the Map interface, and has all the functions of Map.
Storage structure
In Java, the implementation of HashMap uses a complex structure (array + linked list + red-black tree), with one element of the array also known as a bucket.
When an element is added, its position in the array is calculated based on the hash value. If there is no element at that location, the element is placed directly there. If there is an element at that location, the element is placed at the end of the list.
When the number of elements in a linked list reaches a certain number (and the length of the array reaches a certain length), the linked list is transformed into a red-black tree to improve efficiency.
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.
The source code parsing
attribute
/** * 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(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.
(2) Loading factor
The load factor is used to calculate the capacity to be expanded. The default load factor is 0.75.
(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.
The Node inner class
Node is a typical 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 codeTreeNode inner class
This is a magic class that descends from the Entry class in LinkedHashMap, which we’ll talk about later.
A TreeNode is a typical TreeNode, where a prev is a node in a linked list that can be used to quickly find its predecessor 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 links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
// Located in LinkedHashMap, a typical 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 codeHashMap() constructor
Empty parameter constructor, all with default values.
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the codeHashMap(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 codeHashMap(int initialCapacity) 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 codePut (K key, V value) method
Entry to add elements.
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);
}
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 code(1) Compute the hash value of the key.
(2) If the number of buckets (array) is 0, initialize the bucket;
(3) If there is no element in the bucket where key resides, insert it directly.
(4) If the key of the first element in the bucket where the key resides is the same as that of the key to be inserted, the element is found, and proceed to the subsequent process (9).
(5) If the first element is a tree node, putTreeVal() is called to find the element or insert the tree node;
(6) If it is not in the above three cases, the linked list corresponding to the bucket is traversed to find whether the key exists in the linked list;
(7) If the element corresponding to the key is found, proceed to the subsequent process (9);
(8) If no element corresponding to the key is found, insert a new node at the end of the list and judge whether tree is needed;
(9) If the element corresponding to the key is found, it determines whether the old value needs to be replaced and directly returns the old value;
(10) If an element is inserted, the number is increased by 1 and the need for expansion is determined;
The resize () method
Capacity expansion 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;
TreeNode.putTreeVal(…) methods
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 code(1) Find the root node;
(2) Start the search from the root node;
(3) Compare hash and key values. If they are the same, return the hash value directly, and decide whether to replace value in putVal().
(4) Determine whether to search in the left or right subtree of the tree according to the hash value and key value, and return directly if the search is found;
(5) If no element is found in the end, insert the element in the corresponding position of the tree and balance it;
TreeifyBin () method
If the length of the linked list is greater than or equal to 8 after inserting elements, determine whether to tree.
final void treeifyBin(Node<K, V>[] tab, int hash) {
int n, index;
Node<K, V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// If the number of buckets is smaller than 64, expand the buckets directly
// After expansion, the linked list will split into two linked lists to reduce the number of elements
// For example, if the volume is 4, all the elements divided by 4 have a remainder of 3
// This does not reduce the length of the list
resize();
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
TreeNode<K, V> hd = null, tl = null;
// Replace all nodes with tree nodes
do {
TreeNode<K, V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while((e = e.next) ! =null);
// If you enter the loop above, tree from the beginning node
if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the codeTreeNode. Treeify () method
A real tree approach.
final void treeify(Node<K, V>[] tab) {
TreeNode<K, V> root = null;
for (TreeNode<K, V> x = this, next; x ! =null; x = next) {
next = (TreeNode<K, V>) x.next;
x.left = x.right = null;
// The first element is the root node and is black. The other elements are inserted into the tree in order to balance
if (root == null) {
x.parent = null;
x.red = false;
root = x;
} else {
K k = x.key;
inth = x.hash; Class<? > kc =null;
// Find the insertion position from the root node
for(TreeNode<K, V> p = root; ;) {int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// If no element is found, insert
TreeNode<K, V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// Insertion insertion, default is red nodes, in balanceInsertion() method
root = balanceInsertion(root, x);
break; }}}}// Move the root node to the head node of the list, since the original first element is not necessarily the root node after balancing
moveRootToFront(tab, root);
}
Copy the code(1) Start traversal from the first element of the list;
(2) take the first element as the root node;
(3) Other elements are successively inserted into the red-black tree and then balanced;
(4) Move the root node to the position of the first element in the list (because the root node will change when balancing);
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;
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.
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.;
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;
conclusion
(1) HashMap is a hash table, which adopts the storage structure of array + linked list + red-black tree;
(2) The default initial capacity of HashMap is 16 (1<<4), the default load factor is 0.75 F, and the capacity is always 2 to the power of n;
(3) When HashMap is expanded, its capacity is doubled each time;
(4) When the number of buckets is less than 64, the tree is not implemented, but the capacity is expanded.
(5) When the number of buckets is greater than 64 and the number of elements in a single bucket is greater than 8, tree is performed;
(6) When the number of elements in a single bucket is less than 6, anti-tree is carried out;
(7) HashMap is a non-thread-safe container;
(8) The time complexity of HashMap searching for added elements is O(1);
Source address with detailed comments
Source address with detailed comments
eggs
What do we know about red-black trees?
Red-black trees have the following five properties:
(1) The node is red or black.
(2) The root node is black.
(3) Each leaf node (NIL node, empty node) is black.
(4) The two children of each red node are black. (No two consecutive red nodes on all paths from each leaf to the root)
(5) All paths from any node to each of its leaves contain the same number of black nodes.
The time complexity of red-black trees is order log n, proportional to the height of the tree.
Every insertion and deletion operation of red-black tree needs to be balanced, which may change the position of root node, color conversion, left rotation, right rotation and so on.
Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
