This is the 30th day of my participation in the Wenwen Challenge
In the above
The core code of ConcurrentHashMap for JDK1.7 was explained in the previous article. ☕ [Java principle exploration] “ConcurrentHashMap” simple source analysis (JDK1.7 version), next we will look at the current very important JDK1.8 version of ConcurrentHashMap, this is currently we should learn one of the most technical source code.
If the profile
ConcurrentHashMap is a class in the Concurrent family that is used to implement the underlying data structures of the classic open source framework Spring due to its high efficiency in supporting concurrent operations and its widespread use.
It’s already a step up from its thread-safe big brother, HashTable, and as a result its locks are more detailed than the synchronized locks that HashTable adds to almost every method, which can undoubtedly affect performance.
Introduction of the principle
This analysis of the source code is JDK8 version, and JDK7 version has a big difference. The idea of implementing thread-safe has also changed completely, abandoning the concept of Segment in favor of a completely new way of implementing it, using the CAS algorithm.
It follows the HashMap concept of its contemporary (JDK1.8). The bottom layer is still “array” + linked list + red-black tree, but in order to achieve concurrency, a lot of auxiliary classes are added, such as TreeBin, Traverser and other internal object classes.
Important attributes
Let’s start with a couple of important attributes that we won’t cover with HashMap, but let’s focus on sizeCtl. It is a highly visible attribute in ConcurrentHashMap because it is a control identifier that has different uses in different places and has different values that represent different meanings.
sizeCtl
- ** A negative value indicates that an initialization or expansion operation is in progress **
- -1 indicates initialization
- -n Indicates that N-1 threads are performing capacity expansion
- A positive value or 0 indicates that the hash table has not been initialized. This value indicates the size of the initialization or next expansion, which is similar to the concept of expansion threshold.
As you will see later, its value is always 0.75 times the capacity of the current ConcurrentHashMap, which corresponds to loadFactor.
** * Size is always a power of two. Directly by iterators. */
transient volatile Node<K,V>[] table;
/** * Table initialization and resizing control. When negative, the * table is being initialized or resized: -1 for initialization, * else -(1 + the number of active resizing threads). Otherwise, * when table is null, holds the initial table size to use upon * creation, or 0 for default. After initialization, Holds the * next element count value upon which to resize the table. Holds the * next element count value upon which to resize the table. A negative value indicates that the hash table is being initialized or expanded. -1 indicates that the hash table is being initialized or expanded. -N Indicates that N-1 threads are expanding the hash table
private transient volatile int sizeCtl;
// The following two variables are used to control single thread entry during expansion
/**
* The number of bits used for generation stamp in sizeCtl.
* Must be at least 6 for 32bit arrays.
*/
private static int RESIZE_STAMP_BITS = 16;
/**
* The bit shift for recording size stamp in sizeCtl.
*/
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
/*
* Encodings for Node hash fields. See above for explanation.
*/
static final int MOVED = -1; // The hash value is -1, indicating a forwardNode
static final int TREEBIN = -2; // A hash value of -2 indicates a TreeBin node
Copy the codeImportant inner classes
Node (Linked list)
Node is the core inner class that wraps key-value pairs in which all data inserted into ConcurrentHashMap is wrapped.
As follows:
static class Node<K.V> implements Map.Entry<K.V> {
final int hash; / / hash value
final K key; / / key value is the key
volatile V val;// Value with sync lock
volatile Node<K,V> next;// Next pointer with sync lock
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash; // hash
this.key = key; // key
this.val = val; // value
this.next = next; // Reference to the next node
}
public final K getKey(a) { return key; }
public final V getValue(a) { return val; }
public final int hashCode(a) { return key.hashCode() ^ val.hashCode(); }
public final String toString(a){ return key + "=" + val; }
// Directly changing the value of value is not allowed
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
// Compare whether two nodes are equal
public final boolean equals(Object o) { Object k, v, u; Map.Entry<? ,? > e;return ((o instanceofMap.Entry) && (k = (e = (Map.Entry<? ,? >)o).getKey()) ! =null&& (v = e.getValue()) ! =null && // Compare the type first
(k == key || k.equals(key)) && / / than the key again
(v == (u = val) || v.equals(u))); // compare value with value
}
/** * Virtualized support for map.get(); overridden in subclasses. */
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if(k ! =null) {
do {
K ek;
if(e.hash == h && ((ek = e.key) == k || (ek ! =null && k.equals(ek))))
return e;
} while((e = e.next) ! =null);
}
return null; }}Copy the codeThis Node inner class is very similar to the Node class defined in HashMap
-
But there are some differences: It sets the sync lock for volatile on the value and next attributes
-
It does not allow calls to the setValue method to directly change the value field of a Node
-
It adds the find method to assist the map.get() method
TreeNode
-
Tree node class, another core data structure.
-
When the list becomes too long, it is converted to a TreeNode.
Unlike HashMap, however, it does not convert the nodes directly into red-black trees. Instead, it wraps the nodes as Treenodes in TreeBin objects, and the TreeBin wraps the red-black tree.
In ConcurrentHashMap, TreeNode is integrated from the Node class, not from the linkedhashMap. Entry
,v>
class in HashMap, that is, TreeNode has a next pointer. This is done to facilitate Treebin-based access.
TreeBin
This class is not responsible for wrapping the user’s key and value information, but rather many TreeNode nodes. It replaces the root node of the TreeNode, which means that the actual ConcurrentHashMap “array” stores TreeBin objects instead of TreeNode objects, which is different from the HashMap. This class also has read/write locks.
You can see that when the TreeBin node is constructed, only its hash value is specified as the TreeBin constant, which is an identifier for. We also see the familiar red-black tree construction method
/** * Creates bin with initial set of nodes headed by b. */
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null.null.null);
this.first = b; // wrap it as the first node
TreeNode<K,V> r = null;
// Initialize the root node
for(TreeNode<K,V> x = b, next; x ! =null; x = next) {
next = (TreeNode<K,V>)x.next; // Next of the incoming node is assigned to the next node of the current Treebin node for data synchronization
x.left = x.right = null; // Make both the left and right subtrees null
if (r == null) {
x.parent = null;// The parent node is empty
x.red = false; // Does not belong to the red subtree node
r = x; // Temporarily store the red node for the next cycle
}
else {
K k = x.key; // If it is not the root node, it is the next subtree node (belonging to the next value).
int h = x.hash; // Fetch the hash value if it is not the root nodeClass<? > kc =null;
for (TreeNode<K,V> p = r;;) {
int dir, ph; //
K pk = p.key;// Get the key of the root node
if ((ph = p.hash) > h) // Get the hash value to determine whether the hash value is less than the root node
dir = -1; // Belongs to the left subtree,
else if (ph < h) // Otherwise belongs to the right subtree
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// Compare class and key values when hash values are equal
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
// Check whether the comparison result is less than zero and both the left and right subtrees are null
x.parent = xp;// Assign the parent node
if (dir <= 0)
xp.left = x; // Check whether it belongs to the left subtree (<=0)
else
xp.right = x;// Check whether it belongs to the right subtree (>0)
// Create a balance insertion mechanism
r = balanceInsertion(r, x);
break; }}}}this.root = r; / / the root node
assert checkInvariants(root);
}
Copy the codeForwardingNode
A node class used to join two tables. It contains a pointer to the nextTable, nextTable. The key value next pointer to this node is null and its hash value is -1. The find method defined here queries nodes from nextTable rather than itself as the head node
/** * A node inserted at head of bins during transfer operations. */
static final class ForwardingNode<K.V> extends Node<K.V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null.null.null);
this.nextTable = tab;
}
// Loop over to find the corresponding hash and key values
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
// Return if null or unable to locate
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (;;) {
int eh; K ek;
// Iterate over the hash and key values to see if they are equal.
if((eh = e.hash) == h && ((ek = e.key) == k || (ek ! =null && k.equals(ek))))
// Return the same value
return e;
// If the hash value is -1 or -2
if (eh < 0) {
// forwardingNode represents -1
if (e instanceof ForwardingNode) {
// Get directly to the next table.
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
// Return until null
if ((e = e.next) == null)
return null; }}}}Copy the codeThe Unsafe and CAS
Appearing everywhere in ConcurrentHashMap, Unsafe makes extensive use of the Unsafe.compareAndSwapXXX method, which uses a CAS algorithm to implement lock-free value modification operations that significantly reduce the performance cost of lock agents.
The basic idea of this algorithm is to constantly compare the value of a variable in memory to whether the value of a variable you specify is equal, if so, accept the value you specify, otherwise reject your operation.
Because the value in the current thread is not the latest value, your changes may overwrite the results of changes made by other threads. This is similar to the idea of optimistic locking and SVN.
The unsafe static block
The unsafe code block controls the modification of attributes, such as the most commonly used SIZECTL. In this version of concurrentHashMap, a large number of CAS methods are used to modify variables and attributes. Using CAS for lock-free operation can greatly improve performance.
// The offset of each field attribute can be obtained by the offset + the first address of the corresponding data object
private static final sun.misc.Unsafe U;
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;
private static final long CELLSBUSY;
private static final long CELLVALUE;
private static final long ABASE;
private static final int ASHIFT;
static {
try{ U = sun.misc.Unsafe.getUnsafe(); Class<? > k = ConcurrentHashMap.class; SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(k.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(k.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(k.getDeclaredField("cellsBusy")); Class<? > ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class<? > ak = Node[].class; ABASE = U.arrayBaseOffset(ak);int scale = U.arrayIndexScale(ak);
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
throw newError(e); }}Copy the codeThree core methods
ConcurrentHashMap defines three atomic operations that operate on nodes at a specified location. It is these atomic operations that make ConcurrentHashMap thread-safe.
@SuppressWarnings("unchecked")
// Get the Node at position I
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
Copy the code-
CAS algorithm is used to set the Node Node at position I. Concurrency is possible because he specifies what the value of the original node was
-
In the CAS algorithm, the value in memory will be compared to whether the value you specify is equal or not. If the value is equal, your changes will be accepted. Otherwise, your changes will be rejected
-
Therefore, the value in the current thread is not the latest value, and this modification may overwrite changes in other threads similar to SVN
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
// Use volatile to set the node location
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
Copy the codeInitialize method initTable
-
For ConcurrentHashMap, calling its constructor simply sets some parameters.
-
The initialization of the entire table occurs when an element is inserted into ConcurrentHashMap.
- For example, when the put, computeIfAbsent, compute, and merge methods are called, the call time is to check the table== NULL.
-
The initialization method applies the key attribute sizeCtl. If this value is less than 0, another thread is initializing and the operation is abandoned.
-
It can also be seen that the initialization of ConcurrentHashMap can only be done by one thread.
-
If the initialization permission is granted, the CAS method sets sizeCtl to -1 to prevent other threads from entering.
SizeCtl = 0.75 * n;
/** * Initializes table, using the size recorded in sizeCtl. */
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
//sizeCtl indicates that other threads are conducting initialization operations, suspending the thread. Only one thread can initialize a table.
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {// Use CAS to set sizectL to -1 to indicate that the thread is being initialized
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt; sc = n - (n >>>2);// Equivalent to 0.75 x N Set a capacity expansion threshold}}finally {
sizeCtl = sc;
}
break; }}return tab;
}
Copy the codeExpansion method Transfer
-
When the capacity of ConcurrentHashMap is insufficient, expand the table.
-
The basic idea of this method is similar to HashMap, but it is much more complicated because it supports concurrent scaling.
-
The reason is that it supports multiple threads for expansion operations, and does not lock.
-
I would like to do this not just to satisfy concurrent requirements, but to take advantage of concurrent processing to reduce the time impact of capacity expansion. Since capacity expansion always involves copying from one array to another, it would be nice if this could be done concurrently.
The expansion operation is divided into two parts
-
The first part is to build a nextTable, which is twice as big. This is done single-threaded. This single-threaded guarantee is guaranteed by a single operation of the constant RESIZE_STAMP_SHIFT, which will be mentioned later;
-
The second part is copying elements from the original table into nextTable, which allows multithreading.
Let’s take a look at how the single thread works:
-
The general idea is the process of traversal and replication. Firstly, the number of times to be traversed is obtained according to the operation, and then the element at the position of I is obtained by using tabAt method:
-
If this position is empty, the forwardNode node is placed in the I position of the original table, which is also the key to trigger concurrent expansion.
-
If the location is Node (fH >=0) and if it is the head of a linked list, construct an antilist and place them at I and I +n in nextTable
-
If it is a TreeBin node (fH <0), do a reverse process and determine whether untreefi is required. Place the process at I and I +n in nextTable respectively
-
After all nodes have been replicated, make nextTable the new table and update sizeCtl to 0.75 times the new size.
Look again at how multithreading works:
-
If the node traversed to is a forward node, continue traversing backwards, coupled with the mechanism to lock the node, the completion of multi-threaded control.
-
Multithreading traverses nodes, processing a node, sets the value of the corresponding point to forward, and another thread sees the forward, traverses backwards.
-
So the crossover completes the replication. But also a good solution to the thread safety problem. The design of this method really makes me worship.
/** * a transition table, */ is used only for capacity expansion
private transient volatile Node<K,V>[] nextTable;
/** * Moves and/or copies the nodes in each bin to new table. See * above for explanation. */
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n <<1];// Construct a nextTable object that has twice the capacity
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);// Construct a link node pointer to mark the bit
boolean advance = true;// If the key attribute of concurrent expansion equals true, the node has been processed
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// The body of the while loop controls I, which iterates through the nodes of the original hash table
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false; }}if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// Assign nextTable to table if all nodes have copied to clear the temporary nextTable
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);// Set the capacity expansion threshold to 1.5 times the original capacity, which is still 0.75 times the current capacity
return;
}
// The CAS method is used to update the capacity expansion threshold, in which the sizectl value is reduced by one, indicating that a new thread is added to the capacity expansion operation
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit}}// If the node traversed is empty, place the ForwardingNode pointer
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// If traversing through the ForwardingNode node, this point has already been processed
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// The node is locked
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// If fh>=0, this is a Node
if (fh >= 0) {
int runBit = fh & n;
// Construct two lists: one is the original list and the other is the reverse order of the original list
Node<K,V> lastRun = f;
for(Node<K,V> p = f.next; p ! =null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for(Node<K,V> p = f; p ! = lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// Insert a linked list in place I of nextTable
setTabAt(nextTab, i, ln);
// Insert another linked list in place I +n of nextTable
setTabAt(nextTab, i + n, hn);
// Insert the forwardNode node in position I of the table to indicate that the node has been processed
setTabAt(tab, i, fwd);
// Set advance to true to return to the above while loop to perform the I -- operation
advance = true;
}
// Processing the TreeBin object is similar to the above procedure
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
// Create a positive and negative list
for(Node<K,V> e = t.first; e ! =null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null.null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
elsehiTail.next = p; hiTail = p; ++hc; }}// If the tree structure is no longer needed after the expansion, switch back to the linked list structureln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc ! =0)?newTreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! =0)?new TreeBin<K,V>(hi) : t;
// Insert a linked list in place I of nextTable
setTabAt(nextTab, i, ln);
// Insert another linked list in place I +n of nextTable
setTabAt(nextTab, i + n, hn);
// Insert the forwardNode node in position I of the table to indicate that the node has been processed
setTabAt(tab, i, fwd);
// Set advance to true to return to the above while loop to perform the I -- operation
advance = true;
}
}
}
}
}
}
Copy the codePut method
The most commonly used ConcurrentHashMap methods are put and GET
-
Calculate the position I of the newly inserted point in the table according to the hash value. If the position I is empty, insert it directly, otherwise judge. If the position I is a tree node, insert the new node in the tree way, otherwise insert I to the end of the linked list.
-
ConcurrentHashMap still uses this idea. One of the most important differences is that ConcurrentHashMap does not allow null keys or values.
- The put method is a little more complicated because it involves multiple threads. There are two possible situations in multithreading
-
If one or more threads are expanding ConcurrentHashMap, the current thread must also expand ConcurrentHashMap.
-
The reason why this expansion operation can be detected is that forward nodes are inserted into empty nodes in the Transfer method. If the position to be inserted is detected to be occupied by forward nodes, expansion will be assisted.
-
If it detects that the node to be inserted is non-empty and not a forward node, the node is locked, thus ensuring thread-safety. Although this has some impact on efficiency, it is still much better than Synchronized in hashTable.
-
The overall process is to first define that no key or value is allowed to be put into the table when it is null. For each value put into the table, the spread method is first used to hash the key’s hashcode to determine the position of the value in the table.
-
If the location is empty, it is placed directly, and no lock operation is required.
If there is a node at this location, it indicates that a hash collision has occurred, and the type of the node is determined first.
If it is a linked list node (fH >0), the resulting node is the head of the list of nodes with the same hash value.
You need to iterate backwards to determine where this new value is added.
If the hash and key values are the same as those of the newly added node, you only need to update the value. Otherwise, iterate backwards until the end of the list inserts the node. If the list length is greater than 8 after adding this node, the list is converted to a red-black tree. If the node type is already a tree node, the tree node insertion method is called to insert the new value.
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
// The key or value cannot be null
if (key == null || value == null) throw new NullPointerException();
// Computes the hash value
int hash = spread(key.hashCode());
int binCount = 0;
// An infinite loop is inserted successfully and exited
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// Initialize the table if the table is empty
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// Calculate the position in the table according to the hash value
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// If this position has no value, just put it in, no need to lock
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// When a table join point is encountered, an operation to consolidate the table is required
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
The node can be understood as the head of a linked list with the same hash value
synchronized (f) {
if (tabAt(tab, i) == f) {
//fh > 0 indicates that the node is a list node, not a tree node
if (fh >= 0) {
binCount = 1;
// Walk through all the nodes of the list here
for (Node<K,V> e = f;; ++binCount) {
K ek;
// If the hash value and key value are the same, change the value of the corresponding node
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
Node<K,V> pred = e;
// If the loop reaches the last node, then the new node needs to be inserted at the end of the list
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}// If the node is a tree, insert values like a tree
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! =0) {
// If the length of the list has reached the critical value 8, the list needs to be converted to a tree structure
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break; }}}// Increase the number of elements in the current ConcurrentHashMap by 1
addCount(1L, binCount);
return null;
}
Copy the codeHelpTransfer method
This is a way to help with capacity expansion. When this method is called, ConcurrentHashMap must already have a nextTable. Looking back at the transfer method above, it can be seen that when the thread enters the capacity expansion method, it will directly enter the replication stage.
/** * Helps transfer if a resize is in progress. */
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if(tab ! =null && (f instanceofForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! =null) {
int rs = resizeStamp(tab.length);// Calculate an operation check code
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break; }}return nextTab;
}
return table;
}
Copy the codeTreeifyBin method
This method is used to convert excessively long linked lists into TreeBin objects. However, it is not a direct conversion, but a capacity judgment, if the capacity does not meet the conversion requirements, directly expand the operation and return; If the criteria are met, the structure of the list is changed to TreeBin. Unlike HashMap, it does not put Treenodes directly into the red-black tree. Instead, it uses a small container called TreeBin to encapsulate all Treenodes.
private final void treeifyBin(Node<K,V>[] tab, int index) { Node<K,V> b; int n, sc; if (tab ! = null) {if ((n = tab.length) < MIN_TREEIFY_CAPACITY)// If table.length<64 then tryPresize(n << 1); else if ((b = tabAt(tab, index)) ! = null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode<K,V> hd = null, tl = null; For (Node<K,V> e = b; e ! = null; e = e.next) { TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null); If ((p.rev = tl) == null) hd = p; if ((p.rev = tl) == null) hd = p; else tl.next = p; tl = p; } // Replace Node setTabAt(TAB, index, new TreeBin<K,V>(hd)) with TreeBin (new TreeBin<K,V>(hd)); } } } } }Copy the codeThe get method
The get method is relatively simple. When a key is given to determine a value, two conditions must be met: the keys are the same and the hash value is the same. For nodes that may be in a linked list or tree, search for them separately.
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// Computes the hash value
int h = spread(key.hashCode());
// Determine node positions based on the hash value
if((tab = table) ! =null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) ! =null) {
// If the node key is the same as the passed key and not null, the node is returned directly
if ((eh = e.hash) == h) {
if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
return e.val;
}
// If eh<0, the node is found in the tree
else if (eh < 0)
return(p = e.find(h, key)) ! =null ? p.val : null;
// Otherwise, traverse the list to find the corresponding value and return
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
Copy the codeSize related methods
For ConcurrentHashMap, the exact number of items in the table is an indeterminate number, because it is impossible to call size() and cause other threads to stop counting, like GC’s “stop the world” method, so the number is an estimate. ConcurrentHashMap also worked out this estimate with great effort.
Auxiliary definition
To count elements, ConcurrentHashMap defines variables and an inner class
/** * A padded cell for distributing counts. Adapted from LongAdder * and Striped64. See their internal docs for explanation. */
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(longx) { value = x; }} * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //** * actually holds the number of elements in the hashMap updated using the CAS lock, but it does not return the number of elements in the current hashmap */
private transient volatile long baseCount;
/** * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. */
private transient volatile int cellsBusy;
/** * Table of counter cells. When non-null, size is a power of 2. */
private transient volatile CounterCell[] counterCells;
Copy the codeMappingCount and Size methods
Both methods do not return basecount directly, but count the value once, which is actually an approximate number. Therefore, it is possible that another thread is performing an insert or delete operation at the time of the count.
public int size(a) {
long n = sumCount();
return ((n < 0L)?0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
/**
* Returns the number of mappings. This method should be used
* instead of {@link #size} because a ConcurrentHashMap may
* contain more mappings than can be represented as an int. The
* value returned is an estimate; the actual count may differ if
* there are concurrent insertions or removals.
*
* @return the number of mappings
* @since1.8 * /
public long mappingCount(a) {
long n = sumCount();
return (n < 0L)?0L : n; // ignore transient negative values
}
final long sumCount(a) {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if(as ! =null) {
for (int i = 0; i < as.length; ++i) {
if((a = as[i]) ! =null)
sum += a.value;// Summation of all counter values}}return sum;
}
Copy the codeAddCount method
The addCount method is called at the end of the put method, and the number of elements in the current ConcurrentHashMap +1. This method does two things: updates the baseCount value and checks for expansion.
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// Update baseCount with CAS method
if((as = counterCells) ! =null| |! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null| |! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended);return;
}
if (check <= 1)
return;
s = sumCount();
}
// If the value of check is greater than or equal to 0, you need to check whether capacity expansion is required
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) ! =null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
//
if (sc < 0) {
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// If another thread is performing capacity expansion
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// If the current thread is the only one or the first thread to initiate expansion, nextTable=null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); s = sumCount(); }}}Copy the code