This article is based on JDK1.8
A HashMap uses a key/value storage structure, where each key corresponds to a unique value.
Prior to jdk1.7, the internal storage structure of a HashMap was array + linked list.
In jdk1.8, the storage structure of HashMap is array + linked list + red-black tree, which improves efficiency.
Red black tree
Before reading the HashMap source code, it’s worth knowing a little about red-black trees.
1. Properties of red-black trees
Red-black tree is a self-balanced binary search tree.
Red-black trees have the following characteristics:
- 1. Each node has a color, black or red
- 2. The root node is black
- 3. Two consecutive red nodes cannot appear between parent and child nodes
- 4. The number of black nodes passed by any node traversing down to the leaf nodes of its descendants must be equal
- Empty nodes are considered black
2. Red-black tree balancing operation
A red-black tree is a balanced tree, and there are two main ways to keep a red-black tree in balance: rotation (left, right) and color change.
The diagram of left and right rotation is as follows:
Discoloration means changing the color of the node to maintain balance, as shown below:
Red black tree in HashMap
HashMap uses a hybrid storage structure — array + linked list + red-black tree.
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.
2. Hash
1. Hash Table
A HashMap is a Map based on a Hash Table, a general-purpose data structure that is natively supported by most programming languages.
Hash table: After a key is hashed to a bucket or slots index, which stores the value to be fetched.
The diagram below:
2. Hash functions
The index is computed by the hash function, so different keys may be computed by the hash function to get the same index, resulting in hash collisions
Therefore, a good hash function must be designed to reduce the probability of hash collisions.
Hash collisions have to be handled properly.
Take a quick look at the hash methods in a HashMap:
static final int hash(Object key) {
int h;
// key.hashcode () is a hash algorithm that returns the initial hash value
// Do the 16-bit right shift xor mix again
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeString hashCode is a value of type int, which can be used as an array subscript without collisions. But this hashCode is in the range of [-2147483648, 2147483647], which is nearly 4 billion in length, so it certainly cannot be used as an array subscript, nor will it fit in memory.
DEFAULT_INITIAL_CAPACITY = 1 << 4. Therefore, the Hash value obtained cannot be used as a subscript. You need to obtain a subscript value by modulo operation with the array length.
(h = key.hashCode()) ^ (h >>> 16). By moving the hash 16 bits to the right, which is exactly half its length, and then xor with the original hash, you mix the high and low values of the original hash, increasing the randomness.
HashMap source code
1. HashMap inheritance
The class diagram of HashMap is as follows:
- Implementation of Cloneable, can be cloned
- Serializable is implemented and can be serialized
- AbstractMap inherits from AbstractMap, implements the Map interface, with all the functions of Map
2. The HashMap attribute
/** * Default capacity, must be a power of 2 **/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //aka16
/** * The maximum capacity is 2 ^ 30 **/
static final int MAXIMUM_CAPACITY = 1 << 30;
/** * The default load factor is 0.75 and can be expanded when the capacity exceeds 3/4 **/
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
/** * Tree threshold: Tree when the number of elements in the bucket is greater than 8 **/
static final int TREEIFY_THRESHOLD = 8;
/** * De-threshold: 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;
/** * Minimum tree threshold: 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
- 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 will be tree.
- The load factor
The load factor is used to calculate the capacity to be expanded. The default load factor is 0.75. When the capacity exceeds 3/4, expand the capacity.
- The tree,
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.
3. 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 code
4. Red-black tree correlation
Now that you’ve seen some of the properties and operations of red-black trees, let’s look at the implementation.
4.1 TreeNode inner class
Node is the Node class of a red-black tree. It inherits from the Entry class in LinkedHashMap.
static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
TreeNode<K,V> parent; / / the parent node
TreeNode<K,V> left; / / the left child
TreeNode<K,V> right; / / right child
TreeNode<K,V> prev; // The front node
boolean red; // The color of the red-black tree
/** * constructor */
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/** * returns the root node */
final TreeNode<K,V> root(a) {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
returnr; r = p; }}/ /...
}
Copy the code
4.2, left-handed
/** * red black tree left rotation **/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode
root, TreeNode
p)
,v>
,v> {
TreeNode<K,V> r, pp, rl;
//p is not null and the right subtree of p is not null
if(p ! =null&& (r = p.right) ! =null) {
// Program the left subtree of r(the right subtree of P) into the right subtree of P
if((rl = p.right = r.left) ! =null)
Rl is the left subtree of r(the right subtree of p)
rl.parent = p;
// Turn the parent of r(the right subtree of P) into the parent of P (the left rotation process turns the right subtree into its parent)
if ((pp = r.parent = p.parent) == null)
// If the parent of p is null, p is the root of the subtree.
// Change r to the root node (the root node of the subtree) and turn it black (balanced)
(root = r).red = false;
// If there is a parent node and p is the left subtree of the node
else if (pp.left == p)
// Change r(the right subtree of p) to the left subtree of the node
pp.left = r;
// If there is a parent node and the p node is the right subtree of that node
else
// Change r(the right subtree of p) to the right subtree of the node
pp.right = r;
// Change r(left subtree of p) to p (left subtree of p)
r.left = p;
//r becomes the parent of p
p.parent = r;
}
return root;
}
Copy the codeTake a look at the diagram.
- P has no parent
- P has a parent
4.3, right
/** * red black tree right **/
static <K,V> TreeNode<K,V> rotateRight(TreeNode
root, TreeNode
p)
,v>
,v> {
TreeNode<K,V> l, pp, lr;
//p is not null and the left subtree of p is not null
if(p ! =null&& (l = p.left) ! =null) {
// Change the right subtree of L (left subtree of P) to the left subtree of P
if((lr = p.left = l.right) ! =null)
lr.parent = p;
// Turn the parent of L (the right subtree of P) into the parent of P (dextral process, turn the left subtree into its parent)
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
// If there is a parent node and p is the right subtree of that node
else if (pp.right == p)
pp.right = l;
// If there is a parent node and p is the left subtree of the node
else
pp.left = l;
// Change l(right subtree of p) to p (right subtree of p)
l.right = p;
p.parent = l;
}
return root;
}
Copy the codeThe illustration is as follows:
- P has no parent node.
- P has a parent
4.3, the tree
Treeify means to treeify.
As mentioned earlier, lists are treified when the length of the list in the hash bucket exceeds a threshold (8 by default).
/** * red-black tree *@returnThe root of the tree */
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// loop collation
for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
// Fetch the next list node
next = (TreeNode<K,V>)x.next;
// Set the left and right nodes of node X to null
x.left = x.right = null;
// Check whether the current red-black tree has a root node
if (root == null) {
// If there is no root node
// The parent of the current node is set to null
x.parent = null;
// Set the color to black (root node is black)
x.red = false;
// Set x node to the root node
root = x;
}
// The current red-black tree has a root node
else {
// Get the key of node X
K k = x.key;
// Get the hash of the x node
int h = x.hash;
/ / the class keyClass<? > kc =null;
// Traverse from the root node and insert the x node into the red-black tree
for (TreeNode<K,V> p = root;;) {
// define dir(direction),ph(node hash)
int dir, ph;
// Retrieve the key of node P
K pk = p.key;
// When the hash of p node is greater than that of x node
if ((ph = p.hash) > h)
/ / on the left side of the
dir = -1;
else if (ph < h)
/ / on the right side
dir = 1;
// If the if branch above does not go, then the hash value of the keys of the two nodes is equal
If the key Class of the current node (x) implements the Comparable interface and the current loop node (p) is an instance of the same Class
// Compare with Comparable
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// If it is still equal, use tieBreakOrder to compare
dir = tieBreakOrder(k, pk);
// Cache the p node first
TreeNode<K,V> xp = p;
// Insert to the left or right according to the dir direction
// Check whether it is null
if ((p = (dir <= 0)? p.left : p.right) ==null) {
// The selected left/right subtree is null
// Set the original p node (now XP) to the parent node of X
x.parent = xp;
// If dir is less than or equal to 0
// Place the X node to the left of the original P (now XP) node
if (dir <= 0)
xp.left = x;
// If dir is greater than 0
// Place the X node to the right of the original P (now XP) node
xp.right = x;
// Call balanceInsertion to perform insertion balancing
root = balanceInsertion(root, x);
break; }}}}// Make sure that the node stored at the specified location of the hash bucket is the root node of the red-black tree
moveRootToFront(tab, root);
}
/** * Ensure that the node stored at the specified location of the hash bucket is the root node of the red-black tree */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if(root ! =null&& tab ! =null && (n = tab.length) > 0) {
// Index position
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// If it is not the root of a red-black tree
if(root ! = first) { Node<K,V> rn;// Points to the root of the red-black tree
tab[index] = root;
TreeNode<K,V> rp = root.prev;
// Sort the node order
if((rn = root.next) ! =null)
((TreeNode<K,V>)rn).prev = rp;
if(rp ! =null)
rp.next = rn;
if(first ! =null)
first.prev = root;
root.next = first;
root.prev = null;
}
// Do a constant check recursively
assert checkInvariants(root); }}Copy the codeThe legend is as follows:
4.4 Insertion balance
A red-black tree needs to be balanced after nodes are inserted.
BalanceInsertion is a method of balancing nodes inserted into red-black trees.
The way to maintain balance is to rotate and change color.
/** * insert balance */
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode
root, TreeNode
x)
,v>
,v> {
// Set the x node to red (the newly inserted node starts out red)
x.red = true;
// a loop with no boundaries (needs to be jumped out inside)
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// Fetch the parent node of x and check whether it is null
if ((xp = x.parent) == null) {
//x has no parent node
x.red = false;// Change color (black)
return x;// when x is the root node
}
// If x has a parent and the parent of x is black or the parent of X does not exist
else if(! xp.red || (xpp = xp.parent) ==null)
/ / return a root
return root;
// If the parent of x is the left child of the parent
if (xp == (xppl = xpp.left)) {
// The right child of the parent node is not null and is red
if((xppr = xpp.right) ! =null && xppr.red) {
xppr.red = false;// Change color (black)
xp.red = false;// Change color (black)
xpp.red = true;// Change color (red)
x = xpp;
}
else {
//x is the right child of the parent node
if (x == xp.right) {
/ / left
root = rotateLeft(root, x = xp);
// Process the parent node of x
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// The parent node of x exists
if(xp ! =null) {
xp.red = false;/ / discoloration
// The parent node of x exists
if(xpp ! =null) {
xpp.red = true;/ / discoloration
/ / rightroot = rotateRight(root, xpp); }}}}// If the parent of x is the right child of the parent
else {
// The left child of the parent node of x exists and is red
if(xppl ! =null && xppl.red) {
xppl.red = false;// Change color (black)
xp.red = false;// Change color (black)
xpp.red = true;// Change color (red)
x = xpp;
}
else {
If x is the left child of the parent node
if (x == xp.left) {
/ / right
root = rotateRight(root, x = xp);
// Process the parent node of x
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// If the parent of x exists
if(xp ! =null) {
xp.red = false;// Change color (black)
// If the parent node of x exists
if(xpp ! =null) {
xpp.red = true;// Change color (red)
/ / left
root = rotateLeft(root, xpp);
}
}
}
}
}
}
Copy the codeThe legend is as follows:
- Let’s say we have a linked list where the numbers represent hash values (regardless of the hash distribution)
- Nodes are then removed in linked list order for red-black tree insertion and post-insertion balancing (left-right rotation/discoloration)
4.5. Anti-treification
When the length of the list is less than 6, the red-black tree degenerates into a linked list.
/** * red black tree linked list */
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// Loop to turn the red-black tree into a linked list
for (Node<K,V> q = this; q ! =null; q = q.next) {
// Construct a normal list node
Node<K,V> p = map.replacementNode(q, null);
// Maintain the sequence
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Copy the code
4.6, find
The node search of the corresponding linked list, after the tree of the linked list, the node search is realized by the red-black tree. The search logic is relatively clear, because a red-black tree is a self-balanced binary search tree, the left subtree of the node is smaller than itself, and the right subtree is larger than itself. Therefore, according to the given hash, we can determine whether to search from the left subtree or the right subtree, and then loop.
/** * red black tree node lookup entry method */
final TreeNode<K,V> getTreeNode(int h, Object k) {
return((parent ! =null)? root() :this).find(h, k, null);
}
/** * Searches from the root of the red-black tree based on the given hash and key */
final TreeNode<K,V> find(inth, Object k, Class<? > kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
// Retrieve the left and right subtrees and search by hash and key
TreeNode<K,V> pl = p.left, pr = p.right, q;
// Determine the left or right subtree based on the hash size
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
// Returns if the nodes are equal
else if((pk = p.key) == k || (k ! =null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
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;
}
Copy the code
4.7. Delete a Node
Deleting the node is still a bit of a hassle because it requires balancing the red-black tree.
* This is more complicated than a typical red-black tree node deletion because you cannot exchange the contents of the internal node where the leaf node exists. * The successor node to which the "next" pointer points during traversal is accessible. * If there are too few nodes in the current tree, the binary tree is replaced with a simple form * (2-6 node test trigger, depending on the structure of the tree) */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
// Determine the hash bucket
if (tab == null || (n = tab.length) == 0)
return;
/ / the subscript
int index = (n - 1) & hash;
// Retrieve the root node of the specified subscript
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// The successor node and the preceding node
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
If the front node does not exist, the node to be removed is the root node
if (pred == null)
// Move the successor node forward
tab[index] = first = succ;
else
// If the front node exists, connect the successor node to the front node.
pred.next = succ;
// Determine whether the successor node exists
if(succ ! =null)
// Modify the prereference if it exists
succ.prev = pred;
// If first is null, there may be only one node at the specified position
if (first == null)
/ / return
return;
// Get the root node
if(root.parent ! =null)
root = root.root();
// The root node does not exist or the left/right subtree of the root node does not exist or the left/left subtree does not exist
// This judgment is used as a threshold for listization
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
// The red black tree is too small
tab[index] = first.untreeify(map); // too small
return;
}
// Get the node to remove, left and right subtrees
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// Both left and right subtrees exist
if(pl ! =null&& pr ! =null) {
TreeNode<K,V> s = pr, sl;
// Loop to find the successor node
while((sl = s.left) ! =null) // find successor
s = sl;
// Switch p and s colors
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 p is equal, then p is the immediate parent of s.
if (s == pr) { // p was s's direct parent
// Switch places
p.parent = s;
s.right = p;
}
// If there are multiple levels
else {
// Retrieve the parent node of s
TreeNode<K,V> sp = s.parent;
// Switch the position of p and s
if((p.parent = sp) ! =null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if((s.right = pr) ! =null)
pr.parent = s;
}
// Clear the right subtree reference of p
p.left = null;
// Adjust related references
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;
// Determine the replacement node
if(sr ! =null)
replacement = sr;
else
replacement = p;
}
// Only the left subtree exists
else if(pl ! =null)
replacement = pl;
// Only the right subtree exists
else if(pr ! =null)
replacement = pr;
// The left and right subtrees do not exist
else
replacement = p;
// Determine if the replaced node is itself
if(replacement ! = p) {// If it is not itself, the relevant replacement operation is performed
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;
}
// determine the color of p
// If p is a red node, assign the root node to r
// If p is black, delete balance (similar to insert balance)
// where r stores the root of the red-black tree
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// If the replacement node is itself
if (replacement == p) { // detach
// Perform the separation operation
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)
// Make sure that the hash bucket is storing red and black root nodes at the specified location
moveRootToFront(tab, r);
}
Copy the code
5. HashMap constructor
- No-parameter construction method:
/** * Use the default values */ for all parameters
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the code- HashMap(int initialCapacity) : Specifies the default load factor
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the code- HashMap(int initialCapacity, float loadFactor) : determines whether the incoming initialCapacity and loadFactor are valid and calculates the threshold for expansion. The threshold is the nearest 2 to the n power of the incoming initialCapacity
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 code
6, insert,
The flow chart for the HashMap insert is as follows:
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);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Initialize the bucket array table, which is deferred until new data is inserted
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;
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();
afterNodeInsertion(evict);
return null;
}
Copy the codeInsert:
- 1. First, the hash value is disturbed to obtain a new hash value.
- 2. Check whether the TAB bit is empty or its length is 0. If yes, expand the capacity
- 3. Calculate the subscript according to the hash value. If the corresponding subscript does not store data, insert it directly; otherwise, it needs to be overwritten.
- 4, check whether TAB [I] is a tree node, otherwise insert data into the linked list, if yes, insert node into the tree.
- 5. If the length of the linked list is greater than or equal to 8 when nodes are inserted into the list, the list needs to be converted to a red-black tree.
- 6. After all elements are processed, judge whether the threshold value is exceeded; Threshold: If the threshold is exceeded, the system will expand the capacity.
- 7, treeifyBin, is a method to convert a list to a tree, but not all lists with a length of 8 will be converted to a tree, we also need to determine whether the length of the array bucket that stores the key value is less than 64 (MIN_TREEIFY_CAPACITY). If the value is smaller than that of the bucket node, the linked list needs to be expanded. After the expansion, the data on the linked list will be separated to the corresponding bucket node of the column, shortening the length of the linked list.
7,
A HashMap is implemented based on an array + linked list and a red-black tree, but the length of an array bucket used to hold a key value is fixed and determined by initialization.
Then, as the number of data inserts increases and the load factor takes effect, the capacity needs to be expanded to accommodate more data.
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 codeCapacity:
-
(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
8, find
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 codeLooking for:
-
(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;
8, delete,
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;
// Locate the index position in the bucket array, index = (n-1) & hash
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 value of the key is equal to that of the first node in the list, node points to that node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
else if((e = p.next) ! =null) {
// Tree node, call the red-black tree lookup method, locate the node.
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// Walk through the 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); }}// Delete nodes, and red-black trees need to be fixed because deletion breaks balance. Deletion of linked lists is much easier.
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the code
Four,
- A HashMap is a hash table with a storage structure (array + linked list + red-black tree)
- The default initial capacity of a HashMap is 16 (1<<4), the default load factor is 0.75 F, and the capacity is always 2 to the power of n
- The capacity of HashMap is doubled each time it is expanded
- When the number of buckets is less than 64, the system does not tree buckets but expands buckets
- If the number of buckets is greater than 64 and the number of elements in a bucket is greater than 8, tree the bucket
- When the number of elements in a bucket is less than 6, invert the tree
- HashMap is not thread-safe
- HashMap finds added elements in O(1) time
This article is for study notes, references below!
Reference:
[1] : HashMap source code analysis [2] : HashMap source code reading [3] : Face by manual, chapter 3 “HashMap core knowledge, disturbance function, load factor, expansion linked list resolution, deep learning” [4] : Chapter 4 “HashMap data insertion, search, delete, traverse, source analysis” [5] : chapter 5 “Look at the picture, explain 2-3 balance tree” red-black tree predecessor “[6] : [7] : red black tree in the HashMap application – JDK1.8 [8] : Java HashMap source code analysis [9] : Relearning data structures (six, tree and binary tree) [10] : red-black tree in-depth analysis and Java implementation [11] : hash collision and birthday attack