1. Basic variables
// The threshold of the list to the tree
static final int TREEIFY_THRESHOLD = 8;
// The tree turns to the threshold of the list
static final int UNTREEIFY_THRESHOLD = 6;
// The number of buckets transferred per time, which is equivalent to the number of buckets each thread can operate at once
private static final int MIN_TRANSFER_STRIDE = 16;
// Expansion transfer data is where the next transfer starts (this is the reverse from large to small)
private transient volatile int transferIndex;
Copy the code1.1 the CAS operation
The Unsafe class is used for cas operations. It is all native methods implemented in C++. The following variables represent the offset of the corresponding variable: compareAndSwapInt(Object o, long offset, int expected, int x); Set the value of the variable offset to x if the value is equal to the expected value
private static final sun.misc.Unsafe U;
// The long variable below represents the offset of the corresponding this variable of the same name
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;
Copy the code1. Initialize the table
1. Table initialization is delayed until the first put. Using loop +CAS ensures that only one thread will initialize the table at a time.
If the table is null and sizeCtl is less than 0, then some threads have already started initialization. Other threads can yield CPU slices by using thread.yield () and wait for the table to be non-null.
3. Otherwise, use CAS to change the sizeCtl value to -1. If the replacement succeeds, initialize the table.
Note that table size is set to N – (n >>> 2), i.e. 0.75n. This value is used to determine whether table size needs to be expanded.
//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) {
// Check whether a thread has been initialized, if so, release the CPU, and continue the spin test
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// The cas operation sets the sizeCtl value
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// Continue to double-check the judgment
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
// Initialize the table
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt; sc = n - (n >>>2);/ / set sizeCtl = 0.75 n}}finally {
sizeCtl = sc;
}
break; }}return tab;
}
Copy the code2. Put (putVal)
1. Calculate the hash value of the key first
Check whether the table is null. If yes, initialize the table
3. Determine the position of the bucket based on the hash value, and check whether the bucket is empty. If the bucket is empty, set it through the CAS operation
4. If the first node of the bucket is not empty and hash=MOVED, it indicates that a thread is expanding the capacity. Call helpTransfer to expand the capacity
5. Lock the bucket, determine whether the node is a linked list or a tree, and insert nodes according to different situations
6. Determine whether the switch from a linked list to a tree threshold is reached
7. Count the number of nodes
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//1. Calculate the hash value of the key first
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//2, check whether the table is empty, if yes, initialize the table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//3. Determine the position of the bucket based on the hash value and check whether the bucket is empty. If yes, the bucket is empty
// Set it in the cas operation
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//4. If the first node of the bucket is not empty and hash=MOVED, it indicates that a thread is expanding the capacity.
// Call helpTransfer to help expand
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//5. Lock the bucket, determine whether the node is a linked list or a tree, and insert nodes according to different conditions
synchronized (f) {
if (tabAt(tab, i) == f) {// To ensure security in a multi-threaded environment, check again
if (fh >= 0) {// If the hash value is greater than 0, it indicates a linked list
binCount = 1;// Record the number of elements in the list
for (Node<K,V> e = f;; ++binCount) {
K ek;
// Check whether key is already in the list. If it is, replace value directly
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
// Insert a new Key at the end of the table
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}// Call the tree insertion method
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) {
//6. Check whether the link list to the tree threshold is reached
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break; }}}//7. Count the number of nodes
addCount(1L, binCount);
return null;
}
Copy the code3, the list to the tree
1. Check whether the number of linked list nodes is smaller than 64
2. Lock the bucket
3. Turn the list node set into tree node set in turn
4. Turn the set of tree nodes into a red-black tree. This red-black tree is a combination of the linked list and tree structure, which is also seriated into a linked list by the next reference
private final void treeifyBin(Node<K,V>[] tab, int index) {// Change the TAB [index] list to a tree
Node<K,V> b; int n, sc;
if(tab ! =null) {
//1. Check whether the number of linked list nodes is smaller than 64
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// To ensure security in multi-threaded environments, check whether the bucket is empty again. Hash >0 indicates that the bucket is a linked list
else if((b = tabAt(tab, index)) ! =null && b.hash >= 0) {
synchronized (b) {//2. Lock the bucket
if (tabAt(tab, index) == b) {// After locking, judge again
TreeNode<K,V> hd = null, tl = null;
//3. Turn the list node collection into a tree node
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.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
//4. Transform the set of tree nodes into a red-black tree
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
Copy the code4, capacity
1, because the capacity expansion allows concurrent operations, first through the number of CPUS, calculate the number of buckets that can be processed by each thread stride, at least each thread processing 16
2. Apply for nextTable
3. Set nextTab to ForwardingNode, indicating that capacity expansion is being performed
4, each thread in the thread to get its own processing area, each thread through the CAS operation set the transferIndex variable, set a successful thread in the table (transferIndex, transferIndex-stride) this section of the processing permission
- For example, with stride=16, the first thread gets the bucket segment from the next
5. Loop each bucket in turn:
5.1 If the first node of the current bucket is a linked list, relocate the list nodes to two buckets, one at the original position I and the other at the position I +n
5.2 If it’s a red-black tree, here’s the interesting thing. It’s also traversed like a list by a for, divided into two parts, one will be placed at I and one at I +n.
- So the question is, if this is a tree, why does it work like a linked list?
Here is the author design is very clever place, admire Doug Lea god, tree traversal is very inconvenient, and the list traversal is very convenient. TreeNode itself inherits from Node and has a next pointer. When the list is converted to a red-black tree with more than 8 nodes, the next pointer remains unchanged and the list structure is not broken, so the tree itself is a combination of a tree and a list, which can be used as both a list and a tree (this design is similar to a LinkedHashMap, even if a hashMap is also a list).
- Here’s a structure like this, where the yellow lines represent the linked lists:
This is divided into two parts, and the two parts are converted to a linked list or organized as a red-black tree based on whether the two parts reach the treetreeify_threshold =6.
6. After processing a bucket, the bucket is set to the ForwardingNode where the new list is executed. (This is used to mark the expansion status of the table.
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// Take the number of cpus and determine the number of nodes to be migrated per thread. Make sure that the number is not less than MIN_TRANSFER_STRIDE=16
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// Apply for array nextTable
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n <<1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
// Set nextTab to ForwardingNode, indicating that capacity expansion is underway
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
/** nextIndex starts at n; /** nextIndex starts at n; If the success indicates that the thread processes the migration of the next index-stride bucket, that is, I =[nextIndex-1, nextindex-stride] bucket */
// Exit the transfer method directly
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false; }}// Check whether all buckets have been processed
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
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}}else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// Hash >0 indicates a linked list. The list nodes are reassigned to two buckets, one at position I and one at position I +n
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
// Find the tail node of the low and high linked lists
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;
}
// Loop to split the list into two lists, head insertion method
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);
}
// Set the split list to the corresponding bucket through cas operations
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
// Set the current bucket to a ForwardingNode pointing to the new table
setTabAt(tab, i, fwd);
advance = true;
}
// The bucket stores a red-black tree
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;
// The code here is interesting
// Since the red-black tree is a combination of a tree and a linked list, the TreeNode is also a Node
// So this can be traversed like a linked list. This structure is used for easy traversal
// Select nodes from the tree and divide them into the ranking and high-order lists according to the hash results of the nodes
// The list is transformed into a tree, while maintaining the structure of the 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; }}// Split the tree into low (place it at position I) and high (place it at position I +n). Here determine whether the two lists reach the threshold of becoming a treeln = (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;
// Set the split structure to the corresponding bucket
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Copy the code5. Count the number of elements
1. Simply pass the sum of the CouterCell array. This data is not accurate because other threads may be adding or deleting data.
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; }}return sum;
}
Copy the code