One, foreword
With an initial impression of the basic concepts of ConcurrentHashMap, the real exploration comes next.
Expansion is the main play, read the people say difficult. Indeed, compared to the java7 version, the difficulty is really not of the same order. Some of the details were so confusing that it took me days to think about them.
Delve into the details is time-consuming and painful, happy is, how also can’t understand the logic, found this is the wrong source! The official JDK! Java8 is now widely used in the market, how can there be bugs?
Consider a few questions first:
ConcurrentHashMapHow is the capacity expansion mechanism implemented?- Multi-threaded capacity expansion? How do I allocate capacity expansion migration tasks?
- What are the differences and optimizations relative to java7?
- What if there is a GET operation during capacity expansion?
Put adds elements
As usual, start with put. The process of adding elements may trigger the initialization of the array, trigger the linked list and red-black tree conversion, trigger the expansion mechanism, etc. Interestingly, a simple element count, the author has taken great efforts.
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 1. Hash high and low perturbations
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
// 2. TAB is null initialized
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 3. If TAB is not null, use (n-1) &hash to compute the index subscript corresponding to TAB to find node
// If node is null, no hash conflict has occurred. Cas sets the new node to the corresponding position of TAB
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
// 4. When the hash value is MOVED,
This node can only be a ForwardingNode
tab = helpTransfer(tab, f);
else {
// 5. A hash conflict occurs normally
V oldVal = null;
synchronized (f) {
// Check if the node at position I is still f
// Re-loop if there are changes
if (tabAt(tab, i) == f) {
if (fh >= 0) {
Fh >=0 is a linked list
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
// Hash is already equal and (key address is equal or key value is equal)
// Determine whether a replacement is required
// put onlyIfAbsent=false. Replace the old value with the new one
// putIfAbsent onlyIfAbsent=true. The new value does not replace the old value
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
// How to resolve hash conflicts
// The new node is placed at the end of the list, which is different from JDk1.7
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}else if (f instanceof TreeBin) {
// 7. Red black tree
Node<K,V> p;
binCount = 2;
if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
// putTreeVal returns an existing node
// p ! = null Indicates that the key already exists. Check whether value needs to be replaced
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! =0) {
// 8. BinCount, if the length of the list is greater than or equal to 8, it may become a red-black tree
// If the array length is less than 64, it is an expanded array
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
// If the old value is not null, it is a replacement and does not need addCount
return oldVal;
break; }}}// 9. Number of elements +1
addCount(1L, binCount);
return null;
}
Copy the code(1) First calculate the hash value of key, and do the high-low perturbation spread.
(2) Initialize table () if array table is empty. The amount of initialization is minimal, just instantiating an array, but how do you do it safely in a multithreaded environment? SizeCtl changes are involved here:
- Before initialization,
sizeCtlThis is the initial capacity. - At initialization,
sizeCtlEquivalent to a spin lock, one and only one thread can lock itcasIf the value is -1, the lock is obtained. The other threads execute the while loop, where the spin frees up CPU time until the array is not null, which exits the entire function when initialization ends. - Initialization is complete,
sizeCtlThe value is set to the capacity expansion threshold, which is 3/4 of the current capacity and also represents lock release.
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spi
// SIZECTL is set to -1, equivalent to a lightweight spin lock
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// If a thread successfully sets sizeCtl to -1, it has the right to initialize
// After the initialization is complete, set the sizeCtl to 3/4 of the current capacity, which is the capacity expansion threshold
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;/ / 3/4
sc = n - (n >>> 2); }}finally {
// Set the sizeCtl size to 3/4 of the current capacity, which is the capacity expansion threshold
// Release the lock.
sizeCtl = sc;
}
break; }}return tab;
}
Copy the code(3) If the array is not empty, then the hash mapping array subscript (f = tabAt(TAB, I = (n-1) & hash)) will fetch the latest node from the main memory. If the array is empty, then there is no hash conflict, cas sets the new node to the corresponding position, and the setting failure may be because other threads compete for setting. Then recirculate the judgment. (long) I << ASHIFT) + ABASE represents the offset of the I position node in main memory.
// Get the latest node at that location from main memory
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);
}
// cas sets the new node to the corresponding location
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);
}
Copy the codeIf the value of the node is equal to ‘MOVED’, the array is being expanded, and the current thread will help expand helpTransfer (more details later).
(5) If the hash of the node is not equal to ‘MOVED’, it is a normal hash conflict. At this time synchronized node, again judge whether the current position of the node is changed, if it is changed, it means that other threads have modified, and repeat the loop.
(6) the hash value of the node fh > = 0, judging its is common nodes, the linked list, traverse the list and have the same node is the key judgment is replaced or directly to the end, if it is a new node, the interpolation method added to the list the tail to tail, binCount in the process of traversing the list from, record the length of the list, behind to see if need to the red-black tree. Java7 uses header interpolation for new nodes, and java7HashMap uses header interpolation as well. In concurrent cases, it is easy to create an endless loop for the linked list, and later java8 uses tail interpolation.
Fh < 0 && f instanceof TreeBin checks whether it is a red-black tree. PutTreeVal returns a new node if it is null. If it is not null, the returned node is an existing node in the tree.
If a new node is added to the list, the length of the list will be accumulated. If a new node is added to the red-black tree, the value of binCount will be 2. If binCount>= TREEIFY_THRESHOLD indicates that the number of nodes in the list has reached the treeifyBin threshold, run the treeifyBin command.
If the length of the array is smaller than MIN_TREEIFY_CAPACITY=64, tryPresize must be expanded (n << 1). (tryPresize involves capacity expansion, which will be explained later). If the length of the array is greater than =MIN_TREEIFY_CAPACITY=64, the current placeholder node is locked and the tree starts.
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)
// The TAB capacity is less than 64, why << 1
tryPresize(n << 1);
else if((b = tabAt(tab, index)) ! =null && b.hash >= 0) {
// The list becomes a red-black tree.
// A node is locked
synchronized (b) {
// Check whether the TAB index has changed
if (tabAt(tab, index) == b) {
// hd head, TL tail
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.prev = tl) == null)
// Set the header for the first time
hd = p;
else
tl.next = p;
// The tail pointer points to the last node
tl = p;
}
// Red-black TreeBin
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
Copy the codeAddCount (1L, binCount), the number of elements +1.
AddCount Counts elements
AddCount is a little bit more complicated and I’m going to separate it out. How about a simple addition or subtraction of elements, a volatile variable, and then cas? In competitive situations, CAS spin can become a performance bottleneck, with some threads spinning for a long time due to cas count failures.
What did Doug Lea do? The base variable (baseCount) + array (CounterCell[]) assists in counting.
The author’s idea is to avoid competition as far as possible. If CAS succeeds in modifying baseCount, it will not modify CounterCell[], and if modification fails, it will not spin. Cas count of the lattice corresponding to CounterCell[] will be found by hash mapping. CounterCell[] will be expanded if it fails to compete with other threads after expansion, and then spin repeat hash mapping will be entered until the modification is successful. Although it may eventually fall into the situation of continuous spin retry, the performance of multiple threads competing for multiple resources will be significantly better than that of multiple threads competing for one resource. See code for details:
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// counterCells! =null, add the number of elements directly to counterCells,
// counterCells=null, then try to modify baseCount, then modify counterCells.
if((as = counterCells) ! =null| |! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
// Initializing optimistic that true means no competition
boolean uncontended = true;
/ / ThreadLocalRandom getProbe () is equivalent to the hash value of the current thread
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null| |! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {Cas = value+x; cas = value+x
Uncontended =false
// Enter fullAddCount. This method will be added successfully.
fullAddCount(x, uncontended);
return;
}
// From put to addCount, check must be >=2,
// From computeIfAbsent to addCount, check =1
After all, capacity expansion is a time-consuming operation
if (check <= 1)
return;
// Count the total number of elements.
s = sumCount();
}
// When replacing nodes and clearing arrays, check=-1, only the number of elements is decreased, and the capacity expansion check is not triggered, nor the capacity reduction is not triggered.
if (check >= 0) {
// It is not necessary to trigger the expansion.
// Trigger code omission for capacity expansion judgment}}Copy the codeIf the fullAddCount() method succeeds in modifying the number of elements, it will immediately exit the whole addCount method. Personal guess:
- Suppose to
fullAddCountbecauseCounterCell[] asIs empty, then the peripheralifIs cas modificationbaseCountIf it fails, it indicates that another thread has successfully modified it to check whether to expand the capacity. - Suppose to
fullAddCountBecause cas is modifiedcounterCellIf no, other threads are successfully modified and check capacity expansion. - Now that it’s done
fullAddCountThis method is complicated and may be time-consuming. The author’s intention is not to let the client call too long, since there are other threads to check the expansion, the current thread should end, do not let the caller wait too long.
1, fullAddCount tries to change the number of elements
This method is a bit complicated, but the purpose is simple: the modification must be successful. Spin can be divided into three major branches:
counterCellsIf the array is not empty, the hash map corresponds to the grid. If the conflict escalation triggers expansion after multiple failures, the hash map spins again.counterCellsIf the array is empty, it is initialized.- If the CAS server does not have the initialization right, the CAS server is modified
baseCount.
Two variables need to be explained:
collide, meaning whether there is a collision, that is, a competition, CAS failed to modify the grid at the corresponding positioncollideIt is set to true, meaning upgrade, and if the hash loop fails again, it may trigger expansion (2x).CounterCell[]The length of the array depends on the number of CPU coresn>=NCPUConflict no longer escalates (collide=false), will not trigger expansion, but constantly hash spin retry;cellsBusyIs equivalent to a spin lock,cellsBusy=1Acquiring a lock,cellsBusy=0Releases the lock. Expand capacity in branchesCounterCell, add a grid orCounterCellIt’s used in the initialization of the arraycellsBusy.
private final void fullAddCount(long x, boolean wasUncontended) {
int h; // h is similar to hash
if ((h = ThreadLocalRandom.getProbe()) == 0) {
// h = 0 initializes the rehash, and wasUncontended=true means no contention
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
// false: no collision occurred
// True means to upgrade to severe competition level, which may trigger expansion
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
if((as = counterCells) ! =null && (n = as.length) > 0) {
// 1. As is not equal to null and has CounterCell
if ((a = as[(n - 1) & h]) == null) {
If CounterCell=null, create a new one
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
// cellsBusy is equivalent to an optimistic lock, indicating that no other threads are competing
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if((rs = counterCells) ! =null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
// if j is still empty, r is assigned to j
rs[j] = r;
// The Settings were successfully created
created = true; }}finally {
/ / releases the lock
cellsBusy = 0;
}
if (created)
// End the loop
break;
continue; // Slot is now non-empty
}
}
collide = false;
}
// (2) The mapping position of CounterCell is not empty, hash conflict occurs
else if(! wasUncontended)// CAS already known to fail
// (2.1) wasUncontended=false
WasUncontended =true
wasUncontended = true; // Continue after rehash
WasUncontended =true; if there is no contest, try cas to add value+x to the CounterCell
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
// Exit after successful modification
break;
// (2.3) The modification failed
else if(counterCells ! = as || n >= NCPU)// (2.3.1) The ADDRESS of the AS is changed (other threads have expanded) or n indicates that the length of the AS array is greater than or equal to the number of CPU cores
// (no more cores for other threads), no conflict escalation, go (5) hash again, loop again try
collide = false; // At max size or stale
// （2.3.2）counterCells = as && n < NCPU
else if(! collide)Collide = "keep me oncollide", keep me oncollide = "keep me oncollide", keep me oncollide
collide = true;
Keep me in mind: Keep me in mind: keep me in mind: keep me in mind: keep me in mind: keep me in mind: keep me in mind
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
try {
if (counterCells == as) {// Expand table unless stale
// counterCells is expanded twice
// The trigger mechanism of this capacity expansion is that the counterCell mapped to is not null, and the cas operation +x failed several times.
// If the current counterCells address is not changed and the array length is smaller than NCPU (number of CPU cores), double expansion is triggered
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i) rs[i] = as[i]; counterCells = rs; }}finally {
cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
// (5) Generate a pseudo-random number and assign it to h for the next loop judgment
/ / to hash
h = ThreadLocalRandom.advanceProbe(h);
}
// 2. As is null or as is null
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
boolean init = false;
try { // Initialize table
// Check counterCells == AS multiple times, not preventing AS change
if (counterCells == as) {
// Initializes the CounterCell array with an initial capacity of 2
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true; }}finally {
cellsBusy = 0;
}
if (init)
break;
}
BaseCount + x: baseCount + x: baseCount + x: baseCount + x: baseCount + x: baseCount + x: baseCount + x
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base}}Copy the code2, sumCount
How do you count all the elements? The sum of cardinality baseCount+CounterCell[].
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 codeMethods like size(), which provides the user with the number of elements, and isEmpty(), which evaluates to empty, call sumCount().
public int size(a) {
long n = sumCount();
return ((n < 0L)?0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
public boolean isEmpty(a) {
return sumCount() <= 0L;
}
Copy the codeFour,
Expansion is at the heart of ConcurrentHashMap, so it’s easy to see what the author is trying to do. The capacity expansion mechanism is triggered in three ways:
- When updating elements (
put or replace or remove…). , the hash value of the node found by the hash mapping array is equal toMOVED=-1, indicating that the array is being expandedhelpTransfer. - When an element is added, the chain is expressed to the threshold for turning a red-black tree if the array length is less than
MIN_TREEIFY_CAPACITY=64, the capacity expansion is triggeredtryPresize. - When the element is successfully added,
addCountWhen the number of elements is updated, expansion is triggered when the number of elements reaches the capacity expansion threshold.
1. AddCount triggers capacity expansion
AddCount is the most orthodox source of expansion except the expansion that may be triggered by the transformation of linked list to red-black tree, so the mysterious footprint of expansion is explored from addCount first.
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// Update the number of elements.
if((as = counterCells) ! =null| |! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
/ / ThreadLocalRandom getProbe () is equivalent to the hash value of the current thread
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null| |! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {Cas = value+x; cas = value+x
Uncontended =false
// Enter fullAddCount. This method will definitely succeed, but because this process may be time-consuming, it will immediately exit the whole method.
fullAddCount(x, uncontended);
return;
}
// From put to addCount, check must be >=2,
// From computeIfAbsent to addCount, check =1, meaning that no hash conflicts have occurred for the added element.
After all, capacity expansion is a time-consuming operation
if (check <= 1)
return;
// Count the total number of elements.
s = sumCount();
}
// See here
// When replacing nodes and clearing arrays, check=-1, only the number of elements is decreased, and the capacity expansion check is not triggered, nor the capacity reduction is not triggered.
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) ! =null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// Number of elements in S >= Threshold for sc expansion. The address of TAB does not change, and the array length does not reach the maximum value
// The capacity is expanded
// For example, n=64
// rs=32793 1000000000011001
int rs = resizeStamp(n);
if (sc < 0) {
// 1. Check capacity expansion. If you need help, expand capacity
// ①(SC >>> RESIZE_STAMP_SHIFT)! = RS To determine whether the capacity is expanded.
// ②sc=rs+1
// ③ SC == RS +MAX_RESIZERS
Rs +1 and RS + MAX_RESIZERS can be negative.
// So this is a bug, discussing with friends, this is indeed a bug.
// transferIndex Indicates the index of the migration element. If the expansion is performed in reverse order, transferIndex<=0 indicates that the migration task has been assigned.
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
// If the capacity expansion is completed and the capacity expansion has been completed, or the number of expanded threads has reached the maximum, no help is needed for capacity expansion
break;
// Help thread +1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 2. The first thread to trigger capacity expansion
Rs << RESIZE_STAMP_SHIFT) + 2, why add 2
// 1000000000011001 00000000 00000000 + 2
// sc = 1000000000011001 0000 0000 0000 0010
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
// 3. If the first expansion thread fails to trigger, the total number of elements is counted again and the loop is repeated.s = sumCount(); }}}Copy the codeIf the calculated total number of elements s is greater than or equal to the threshold for sc capacity expansion, the address of TAB does not change, and the array length does not reach the maximum value, the capacity expansion is triggered.
(1) Calculation process of resizeStamp
What does RS mean and what does it do? I stumbled on a rock at the beginning. Let’s first look at the calculation process of resizeStamp(n) :
/** * return the value as a flag for the size of the tablespace being expanded, that is, n. Rs can reverse deduce that n * Returns the stamp bits for resizing a table of size N. * Must be negative when shifting left by RESIZE_STAMP_SHIFT. * */
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
Copy the codeLook at the source comment, return the value as a flag bit is expanding the array length N? And get a negative number when moving RESIZE_STAMP_SHIFT=16 bits to the left?
Integer. NumberOfLeadingZeros (n) is to obtain the effect of n of a number of consecutive 0 binary from left to right, such as:
2The binary10From left to right30A continuous0
4The binary100From left to right29A continuous0
8The binary1000From left to right28A continuous0
16The binary10000From left to right27A continuous0
（intThere are32Bit, a complement to the left0)Copy the code(1 << (resize_stamp_bits-1)) is what?
RESIZE_STAMP_BITS = 16,1 moves 15 bits to the right, which is equal to 1*2^15=32768, which is a number of 2 to the integer power.
Interestingly, a number and a bigger than it | operations, the number of integer power of 2 do is equal to the number of the two to do addition. Is easy to understand, the integer of 2 times the number of the left side of the binary 1 is 0, and a smaller number of | operation is to the smaller number to fill the lows of large integer power of 2.
Therefore, the calculation process of resizeStamp is as follows:
n=2, resizeStamp=30+32768=32798, binary:1000 0000 0001 1110
n=4, resizeStamp=29+32768=32797, binary:1000 0000 0001 1101
n=8, resizeStamp=28+32768=32796, binary:1000 0000 0001 1100
n=16, resizeStamp=27+32768=32795, binary:1000 0000 0001 1011
Copy the codeVerify two points of the source code comment:
- Return value as a flag bit for the length n of the expanding array? Yes, for example, 32798 is the expansion flag of n=4,
32 - (32797-32768),We can inversely derive n=4. - The return value moves to the right
RESIZE_STAMP_SHIFT=16Digit, and you do get a negative number (the first digit on the left is 1), and a negative number with a very large absolute value.
(2) Expand the number of threads
Knowing the calculation of resizeStamp, let’s see where it is used:
sc >0If capacity expansion is not started, the first capacity expansion thread is triggered, and the CAS is changed to sc(rs << RESIZE_STAMP_SHIFT) + 2)Rs moves 16 to the left, so it’s a negative number plus 2. Why plus 2? Don’t get the author’s intention.sc<0The system may be expanding capacity. Check whether the system is expanding capacity. Is capacity expansion complete? Does the number of expansion threads reach the upper limit? The current array is in the expansion state, the expansion is not completed, and the number of threads for expansion has not reached the maximum value. If the number of threads for expansion has not reached the maximum value, the number of threads +1 (sc+1).- Read the following code, a thread after the expansion task is complete will
sc-1, that is, the number of threads -1.
This idea is quite clear, but there is always a problem when judging the end of capacity expansion and the maximum number of threads for capacity expansion:
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;
// Help thread +1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
Copy the codeSc < 0, that’s a negative number, rs is a big positive number:
(sc >>> RESIZE_STAMP_SHIFT) ! = rsThe first expansion thread changes sc to RS 16 bits left and then +2.sc=(rs << RESIZE_STAMP_SHIFT) + 2)), then sc is a very small negative number, and sc moves 16 bits to the right (erasing the low value) to derive rs back. So this is to determine whether the current array size is expanded.sc == rs + 1Baidu said the expansion marked the end. Sc is a negative number, RS is an integer plus 1 is still an integer, and a negative number can never equal a negative number.sc == rs + MAX_RESIZERSBaidu said that the number of threads has reached the maximum mark. The same is obviously not true.
Is the source code wrong? The official JDK, and many commercial projects in the market are using java8, can not have a bug? Baidu a lot of domestic blog also no one think here is a bug ah, I wondered, thought a few nights, finally decided to appeal to a big guy friend.
Big guy friend is very cool force, search a foreign special collection of JDK bug forum (domestic open foreign website super slow + English is not good, directly persuade a group of people), international fellow people also have similar doubts:
Since this is considered a bug in java8, why is it not affected in practice? (SC >>> RESIZE_STAMP_SHIFT)! = rs to judge whether the current array in the expanded state, and it can be judged whether expansion, the end of the expansion really ended, sc will change for the expansion of the new array threshold, nature is not in a state of expansion, just make some threads involved in the expansion of the found over (although not rigorous logic, but has less effect on the performance of project operation).
Java11 has not been fixed yet. Java12 has been fixed.
(3) Transfer element migration
Either the first expansion thread or the helper thread calls transfer, which is the process of moving from the old array to the new one. This process involves the allocation of tasks for expansion threads and the replication and migration of elements. (Ridicule the official source code, a function code is long enough, if-else is also a lot of, in actual development, pay attention to an else, can return in time to return in time, make so many else branches, but also nested with each other, the readability is very poor.)
The notes are very clear, although long, the situation is many, repeatedly pondering several times, understand the author’s intention, feel ok, is the thinking of people.
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// Single-core is not split
// Calculate the step size, split task n >>> 3 = n / 2^3
// Divide n into 8 parts and divide it equally among each CPU. If the final step size is smaller than the minimum step size 16, set it to 16
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
// Double the size
@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 Records the migration progress
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// From the following migration logic, we can see that migrating replicated elements is a reverse migration
// advance= true indicates that the replicated elements can be migrated to the previous location
boolean advance = true;
NextTab can be assigned to table if all threads are migrated
boolean finishing = false; // to ensure sweep before committing nextTab
// I represents the location of the array that the current thread is migrating, and bound represents the lower limit of the range that it can migrate at this time
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
// (1) There are two cases that do not need to migrate the copied element to the previous position (reverse order) :
// I >=bound indicates that the migration is incomplete and no further progress is required.
The finishing flag is true to indicate that all threads assigned migration tasks have been completed and there is no need to move forward.
// If -- I < bound, the migration task in the current batch is complete and the new scope can be assigned
// A thread can be assigned multiple tasks.
if (--i >= bound || finishing)
// Migrate replicated elements to the previous location
advance = false;
//(2) Each time transferIndex is executed, the latest value of transferIndex is synchronized to nextIndex
else if ((nextIndex = transferIndex) <= 0) {
// If transferIndex is less than or equal to 0, the transfer task has been assigned to all positions in the original array.
// Break out of the while loop and set I to -1,
// Jump to (4) to determine whether the thread being processed has completed the migration of its scope.
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
// (3) Cas set TRANSFERINDEX, assign task [nextBound,nextIndex], and the task length is the stride
// For example, assume that n=64, i.e. the initial transferIndex=64, stride=16
/ / nextIndex = transferIndex = 64, nextBound = nextIndex - stride = 48
// bound=48
// i=63
// Copy from back to front
bound = nextBound;
i = nextIndex - 1;
advance = false; // The task assignment is complete}}// (4) I has crossed the boundary, the entire array migration task has been allocated
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// Capacity expansion completed
// nextTable is empty
nextTable = null;
// Assign the new array to the old array
table = nextTab;
// sizeCtl set to 3/4 of the size of the new array
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// All migration tasks have been assigned
// The current thread has also completed its migration task (regardless of the number of migrations involved),
// Then sc-1 indicates that the number of threads participating in capacity expansion is reduced by 1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// When the migration begins, sc=(RS << RESIZE_STAMP_SHIFT) + 2 is set
// Every time a thread participates in the migration, sc increments by 1.
// Check if sc is equal to the initial value.
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
// If no, the capacity expansion task of the current thread is complete.
return;
// If the thread is equal, another thread is still migrating (not necessarily the first thread triggering the expansion).
// The current thread will check the node from the back to the front and help to copy the node.
// Finishing can be set to true in advance if all migration is completed.
finishing = advance = true;
i = n; // recheck before commit}}else if ((f = tabAt(tab, i)) == null)
// (5) If the position element of I is empty, set the placeholder node to FWD flag.
// Advance is set to true to advance the replication
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
// (6) If the head node of the current position is ForwardingNode, then all nodes of this position have been migrated.
// You can move forward to replicate nodes in other locations
advance = true; // already processed
else {
// (7) migrate TAB [I]
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
/ / list
int runBit = fh & n;
Node<K,V> lastRun = f;
// lastRun is not the last of a list. The nodes of a list can be divided into two categories.
// Find lastRun in the loop if the last node in the list is not runBit equal to the previous node.
// lastRun may have nodes behind it, but runbits are all equal to lastRun.
// lastRun = java7
for(Node<K,V> p = f.next; p ! =null; p = p.next) {
// Calculate p position
int b = p.hash & n;
if(b ! = runBit) {// Not in the same position as runBitrunBit = b; lastRun = p; }}// hash &n =0 is the low value node, hash &n! =0 is the high-order node.
// Determine whether lastRun found is a low or high node
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
// all nodes before lastRun need to be rehash because fh&n is uncertain.
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);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
// Is a red black tree,
// The principle is similar to the process of linked list migration, which also divides nodes into high and low level nodes
TreeBin<K,V> t = (TreeBin<K,V>)f;
// loTail Indicates the loTail node
// hi high tree head node, hiTail high tree tail node
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
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;
/ / stern interpolation
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
elsehiTail.next = p; hiTail = p; ++hc; }}// If the number of low level nodes <= UNTREEIFY_THRESHOLD=6, the tree is reduced to a linked list
// If there is no high level node, then the original tree t is a low level tree, and the value is directly assigned to ln
// If there is a high level node, the low level node is re-tree-like.
// The judgment of the high level node is the sameln = (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;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Copy the codeSo how do you assign tasks between multiple threads? How do you migrate elements from an old array to a new one? Let me stroke you again:
(3.1) How to assign tasks among multiple threads
First, take a look at the concept of stride at the beginning, task allocation unit, which is the element transfer task assigned to the thread stride one position at a time. In the case of multi-core only, the stride calculation method is to divide the length of the original array into 8 parts, and then divide them equally to each CPU, but the minimum step size is MIN_TRANSFER_STRIDE=16.
TransferIndex records the progress of the migration. The initial value is the length of the original array, n, and the migration is performed in reverse order. ForwardingNode ForwardingNode. A location is occupied by a ForwardingNode when the element is migrated but the entire migration task is not completed. The writer thread will help expand the capacity when it encounters a ForwardingNode, and the reader thread will encounter a ForwardingNode forwarding request.
The task interval assigned by each thread is [transferIndex-stride, transferIndex), and the transferIndex decreases the stride each time. In the source code, the latest transferIndex is first assigned to nextIndex, and then Nextindex-Stride is assigned to nextBound. Meanwhile, CAS updates the transferIndex to nextBound, i.e., a task with a stride unit is assigned. The interval of a unit task is [nextBound,nextIndex). However, instead of a thread only allocating a single stride unit task, the thread will continue to allocate the task after its migration task is completed and the whole large task has not been allocated (transferIndex>0).
When migrating a [nextBound,nextIndex] task, proceed from I = nextindex-1 in descending order until I — < bound=nextIndex indicates that the task is complete and can be assigned to a new task. While (advance){}, I –, while (advance){}, I –, while (advance){}, I —
When transferIndex<=0, it indicates that all tasks are allocated and all migration tasks assigned to the current thread are completed. In this case, I is set to -1. If the current thread does not need to help expand capacity, the number of threads to be expanded is -1 (SC-1). However, there is a point here that the author has thought carefully. When there is still another thread whose migration task is not completed ((SC-2) = resizeStamp(n) << RESIZE_STAMP_SHIFT), the penultimate thread will not stop immediately after its own task is completed. But from forward after traversal check again, whether all nodes position migration, hasn’t begun to migrate the location of the migration, so the last but one thread may help the last thread to do the task, scan down a ring, and can ensure that each position of the element migration, at this point it can be new arrays nextTab to replace the old table, Also set the new capacity expansion threshold to sizeCtl.
(3.2) Migrate elements from the old array to the new array
The process of migrating elements is also interesting. Compared to java7, which only has linked lists, when copying and migrating elements, lastRun is first found and a linked list is divided into two types of nodes: lastRun before and lastRun after. The concept of lastRun is the last node whose hash map is different from that of its predecessor. In this way, we can tell whether the nodes behind lastRun and lastRun are of the same kind and migrate to the new array or the same linked list, so we can follow lastRun to migrate all the time. The nodes before lastRun need to be copied into the new array one by one.
Java8 still uses the concept of lastRun, as well as the concept of high and low nodes, dividing a linked list or red-black tree into two types of nodes, namely, two lists, a list of high and low nodes. How do you tell the difference?
Hash &n =0 is the low value node, hash &n! =0 is the high-order node. The position of the low-order node does not change when it is moved to the new array. The original position of the low-order node is I in the old array, but it is still I in the new array. And the higher-order node, which was at position I in the array, goes to position I in the new array plus the length n of the old array. Why does this rule exist?
Because n is the length of the old array and the value is an integer power of 2, that is, n=2^(m-1) (m is a positive integer not less than 2), only the MTH bit of the corresponding binary is 1, the rest are 0, such as 16(10000), 32(100000). So there are only two outcomes for pH & n, 0 or n, which means that the MTH bit of pH is 0, or the MTH bit of pH is 1 if it’s n.
Mask of n =n-1 mask of 16 1111 mask of 32 11111,2 the mask of n has one more 1 than the mask of n in decimal notation. Mask&ph acts as a modular operation to map array subscripts:
ph & n=0When,phThe MTH bit of is 0, which is an invalid bit, soph&(n-1)Must be equal toph&(2n-1).ph & n=nWhen,phThe MTH bit of phi is 1, which is the significant bit,ph&(2n-1)The MTH bit of is 1, and the rest bits sumph&(n-1)Same thing, soph&(n-1)+n=ph&(2n-1).
Because of this rule, a linked list is divided into two lists, and only two lists are needed to migrate elements from the old array to the new one.
If the number of nodes in the tree is less than or equal to UNTREEIFY_THRESHOLD=6, the tree degenerates into a linked list; otherwise, the tree regenerates into a red-black tree. Similarly, you only need to migrate two linked lists (ln and HN).
2. HelpTransfer to expand capacity
When the element is updated and the location is ForwardingNode, the array is expanding, but the elements in the current location have been migrated, so determine whether to expand with help. (Because java8 code has a problem, the following is copied from Java12)
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// Determine whether the current node F is ForwardingNode and whether its forward nextTable is empty
if(tab ! =null && (f instanceofForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! =null) {
int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
// The addresses of new arrays nextTable and old arrays table remain unchanged and sc<0,
Sc == RS + MAX_RESIZERS sc == RS + MAX_RESIZERS
Sc == RS + 1 Is not ready to commit (table=nextTable)
// Whether the task is assigned transferIndex <=0
if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
transferIndex <= 0)
break;
// The number of threads to be expanded is +1
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break; }}return nextTab;
}
return table;
}
Copy the code3, tryPresize list to red black tree trigger capacity expansion
If the number of nodes in the linked list reaches the threshold to become a red-black tree, but the length of the array is less than 64, expansion is triggered instead of tree.
TryPresize may be called by putAll. The size argument is the size of the added map. Initialization is triggered when the array table is not initialized. Estimated capacity c calculated based on size and capacity expansion factor (tableSizeFor details and initial capacity optimization in the previous article) compared with the original initial capacity of the table (sc), the larger one becomes the new initial capacity.
If there is no empty element in array table, the estimated capacity c of the added element may be greater than the capacity expansion threshold SC in putAll. In this case, the capacity expansion is triggered first and then the elements are added in batches.
TryPresize (n << 1) is called by treeifyBin, tryPresize(n << 1). To ensure that capacity expansion must be triggered if the size of the array is less than 64, the parameter passed to tryPresize is twice the length of the array, so that the calculated C must be greater than the capacity expansion threshold. However, only passing n is certainly greater than the capacity expansion threshold, it is not likely to get the author why to pass n<<1.
private final void tryPresize(int size) {
// c Calculate an appropriate capacity. If size >= MAXIMUM_CAPACITY/2, the appropriate capacity is MAXIMUM_CAPACITY
// Otherwise find a value greater than =size and nearest to size to the power of 2
int c = (size >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>>1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
// When tryPresize is called in putAll, the array is initialized if it has not already been initialized
// In putAll mode, size is the size of the map to be added. C is an estimated capacity value calculated based on size to avoid unnecessary expansion
// Estimate the initial capacity of c and the original array, which is the new initial capacity
n = (sc > c) ? sc : c;
if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = nt; sc = n - (n >>>2); }}finally{ sizeCtl = sc; }}}// Table is not empty and has data
// If c calculated by putAll may be greater than sc capacity expansion threshold, capacity expansion will be triggered first, and elements will be added in batches.
// The input parameter of treeifyBin is n<<1, which must be greater than the capacity expansion threshold sc. Therefore, capacity expansion must be triggered
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
// Java12 is different from Java8
// Java8 will also determine whether to trigger expansion first or help expansion
// Java12 considers that the first thread triggers capacity expansion. If CAS fails, another thread triggers capacity expansion.
int rs = resizeStamp(n);
if (U.compareAndSetInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); }}}Copy the code5. The GET operation is being expanded
What if the location node of the hash map is migrated to the new array due to expansion when the GET operation is performed? During capacity expansion, a FWD (Forward Node) is placed in the location that has been migrated. When the GET operation meets FWD, the retrieval request is forwarded from the old array to the new array, which ensures the real-time consistency of capacity expansion. Another function of FWD is that when the update operation encounters the FWD of a placeholder node at a certain position, it will help expand the capacity. Otherwise, the operation will be normal.
FWD is also a big difference between Java7 and Java8. In Java7, the HashEntry array in a segment is completely migrated, and then the new array is replaced by the old array. This ensures consistency. So there is no concept of helping to expand.
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 1. Hash hash
int h = spread(key.hashCode());
// 2. Hash mapping to find slots in the corresponding array
if((tab = table) ! =null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) ! =null) {
if ((eh = e.hash) == h) {
// 3. If the placeholder node in the slot is the desired key, return
if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
return e.val;
}
// 4. Eh < 0 May encounter red black tree or ForwardingNode
else if (eh < 0)
return(p = e.find(h, key)) ! =null ? p.val : null;
// 5. Otherwise, it is normal list traversal
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
Copy the codeMove on to the previous article for a detailed explanation of ForwardingNode and other node concepts.
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;
}
// Forward to nextTable for further retrieval
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;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
// Return null if the slot of the new array map is empty
return null;
for (;;) {
int eh; K ek;
if((eh = e.hash) == h && ((ek = e.key) == k || (ek ! =null && k.equals(ek))))
return e;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
// Another forward node is encountered, a loop is skipped, and the new TAB is retrieved,
// Will not be added to the new array during the expansion phase? Subject to subsequent verification
continue outer;
}
else
// Here is the red black tree
return e.find(h, k);
}
if ((e = e.next) == null)
// Return null if not found
return null; }}}}Copy the codeReplaceNode Updates a node
Remove and replace both call the replaceNode method. When the remove call is made, both value and CV are null. If the node is traversed and the node with the same key is found, the node will be deleted.
/**
* Implementation for the four public remove/replace methods:
* Replaces node value with v, conditional upon match of cv if
* non-null. If resulting value is null, delete.
* @paramKey Indicates the key * to be replaced@paramValue Indicates the new value *@paramCV old value *@return* /
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
// 1. If the hash mapping node is null, there is no need to replace it
break;
else if ((fh = f.hash) == MOVED)
// 2. Fh =MOVED
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// Common list replacement
validated = true;
for (Node<K,V> e = f, pred = null;;) {
K ek;
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
// Key is equal to hash
// CV is not null, we need to check whether CV and ev are equal, equal to replace or delete
V ev = e.val;
if (cv == null|| cv == ev || (ev ! =null && cv.equals(ev))) {
oldVal = ev;
if(value ! =null)
// Incoming value! =null, the old value is replaced with the new value
e.val = value;
else if(pred ! =null)
// If the value passed in is null and the pred is not null, delete this object
pred.next = e.next;
else
// If the precursor is null, the head node is deleted
setTabAt(tab, i, e.next);
}
// The node is found and processed, ending the loop
break;
}
// Continue traversing
pred = e;
if ((e = e.next) == null)
// If the next node is null, the end of the loop is reached. The node to be replaced does not exist
break; }}else if (f instanceof TreeBin) {
// Red-black tree replacement
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if((r = t.root) ! =null &&
(p = r.findTreeNode(hash, key, null)) != null) {
// r.pintreenode finds the node from the red-black tree
V pv = p.val;
if (cv == null|| cv == pv || (pv ! =null && cv.equals(pv))) {
// Pass in the old CV value
oldVal = pv;
if(value ! =null)
// If the value passed is not null, replace it
p.val = value;
// If the value passed is null, the node is removed from the tree
else if (t.removeTreeNode(p))
// When deleting a node, it does not determine whether the number of nodes in the tree has been reduced to UNTREEIFY_THRESHOLD
// t.emovetreenode (p) returns a result that does not indicate whether the deletion was successful,
// True instead means that the tree is too small (the root node is null or the left child or the right child is null) and needs to degenerate into a linked list
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
"// validated=true", this node is already processed in the general list or red-black tree
if(oldVal ! =null) {
if (value == null)
// value=null if the node is deleted, count-1
addCount(-1L, -1);
return oldVal;
}
break; }}}return null;
}
Copy the codeSeven,
Finally is the most core expansion of the source code liver over, but there are still some details did not get to the author’s meaning, also take out and discuss:
1. Why is the count of the first thread that triggers capacity expansion +2? If sc==rs+1, we can say that all threads have been expanded, but if sc==rs+1, we can also say that all threads have been expanded.
TryPresize = 2 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 treeifyBin = 64 In order to ensure that the call to tryPresize will trigger expansion, passing n must be greater than the current expansion threshold.
Those who like to drill and are interested can talk about their opinions and discuss them together.
(The source code for ConcurrentHashMap is much larger than that, but some functions are not commonly used or even used, so I’ll leave it at that.)
PS: If there is any misunderstanding in this article, we welcome your criticism and correction, and look forward to your comments, likes and favorites. I am Xu, willing to make progress with you!
Sky blue and so on misty rain, and I am waiting for you, wechat public number search: Xu students ah, continue to update liver goods, come to pay attention to me, and I study together ~