This article is participating in the Java Theme Month – Java Debug Notes EventActive link
preface
The body of the
JDK version: 1.8.0_181
The data structure
Array, linked list red black tree; The data structure is the same as the HashMap data structure;
A constructor
/** * Creates a new, empty map with the default initial table size (16). */
// no argument constructor
public ConcurrentHashMap(a) {}// Initializes the constructor for the specified capacity
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>>1) + 1));
this.sizeCtl = cap;
}
Copy the codeThe common construction methods are mainly the above two; The default configuration is set to 16. The default configuration is set to 16. TableSizeFor; tableSizeFor; tableSizeFor; tableSizeFor; ConcurrentHashMap initialCapacity + (initialCapacity >>> 1) + 1, which is roughly half the original value
Add methods
Provides add methods for external calls
public V put(K key, V value) {
return putVal(key, value, false);
}
public void putAll(Map<? extends K, ? extends V> m) {
tryPresize(m.size());
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putVal(e.getKey(), e.getValue(), false);
}
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}
Copy the codeThe first put method, which is the most common; The second is to add data from the Map to the ConcurrentHashMap, using the for loop Map, and then putting; The third is also added, but only if there is no key value; This is useful when setting defaults;
All three of the above methods call putVal: putVal (); putVal (); putVal (); putVal ()
final V putVal(K key, V value, boolean onlyIfAbsent) {
/ / empty
if (key == null || value == null) throw new NullPointerException();
// Computes the hash value
int hash = spread(key.hashCode());
int binCount = 0;
// loop (cas)
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// Check whether the initialization is complete
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// Check whether there is data in the corresponding (bucket) array position
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// cas adds data to the corresponding header of the (bucket) array (thread-safe)
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// Check whether the current (bucket) array is MOVED and whether the current Map is expanding
else if ((fh = f.hash) == MOVED)
// Speed up capacity expansion
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// Use synchronized to lock positions (thread-safe)
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// List processing, similar to HashMap
for (Node<K,V> e = f;; ++binCount) {
K ek;
// Check if there is the same key
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 same key is not found, add it directly at the end
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,value, null);
break; }}}// Check whether there is a red-black tree (similar to HashMap)
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) {
// Determine if tree is required
if (binCount >= TREEIFY_THRESHOLD)
// List to red black tree
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break; }}}// Change the number of elements in the container
addCount(1L, binCount);
return null;
}
Copy the codeDescription:
synchronizedLock part of code withHashMapPretty much the same; But the processing process andHashMapIt’s different;- use
caswithsynchronized(in this case, segmented locking) to keep threads safe; - Increase in the
addCountMethod, there’s a little bit of caution herebinCountNumerical,addCountIn the method; - In this code above
MOVEDState, need to combinetransferMethods to observe;
Process:
- Check whether initialization is performed
- Check whether it is the first node
- Determine whether to expand capacity.
- Add to bucket
4.1 Locking 4.1.1 Determining whether to Add or Overwrite a Linked List 4.1.1.1 Determining whether to Add or Overwrite a Linked List 4.1.2 Determining whether to Add a Red-black Tree 4.1.2.1 Adding a Red-black Tree 4.2 Determining the number of elements in a bucket 4.2.1 Determining whether to add or overwrite a Linked List 4.2.2 Determining whether to Add or Overwrite a Linked list Overwriting returns 5. Add number (addCount)
Initialization method
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// Check whether the current container array is initialized
while ((tab = table) == null || tab.length == 0) {
// Determine the sizeCtl value. If less than 0, another thread is initializing
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// Change the SIZECTL value in CAS mode
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// Determine the container
if ((tab = table) == null || tab.length == 0) {
// Determine the size of the container. If not, use DEFAULT_CAPACITY. The default length of 16 is implemented here
int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt;// sc is 3/4 of the array size
sc = n - (n >>> 2); }}finally {
/ / modify the value
sizeCtl = sc;
}
// Stop the while loop
break; }}return tab;
}
Copy the codeInitialization also uses CAS to ensure thread safety; Double check is also used to check whether the array length is null; SizeCtl is negative when the container is being expanded. When multiple threads are competing, thread.yield () is used;
Add the number of container elements
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// Notice the baseCount value here. Cas is used to add 1, which is the current number of elements in the container
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))) {// block cas method
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
// See here
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// Determine whether the container needs to be expanded
while (s >= (long)(sc = sizeCtl) && (tab = table) ! =null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) { // A thread is already performing capacity expansion to accelerate capacity expansion
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))// Add a thread to help with capacity expansion
transfer(tab, nt);
}
// Change the sizeCtl value
else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); s = sumCount(); }}}Copy the codeThis method is mainly used for two functions: first, it is used to modify the number of container elements, that is, cas changes baseCount. However, it needs to be paid attention to here, if no CAS succeeds, it means that the multi-thread competition is added, and the CAS will be divided. Second, determine whether expansion is needed, that is, call transfer expansion; If the capacity is being expanded, accelerate the capacity expansion.
To sum up: CAS, segmented CAS; Capacity expansion to accelerate capacity expansion
capacity
The expansion of ConcurrentHashMap is to create a new array with twice the size of the original array, and then add elements from the original array to the new array.
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
// Create an array twice as large as n << 1
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;
// Note that ForwardingNode inherits Node, and ForwardingNode's default hash is MOVED
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
// Loop through the old array to place elements in the new array
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;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false; }}// Check whether all elements in the original array have been moved
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// After the move is complete
if (finishing) {
nextTable = null;
// Table points to a new array
table = nextTab;
// Change the sizeCtl value to 3/4 of the size after the expansion
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) // Check if there is an element in the array corresponding to the position I
// If there are no elements, put FWD in the position of array I, which means the position of array I has been moved
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED) // Check whether the position corresponding to I in the original array has been moved
advance = true; // already processed
else {
// Lock an array into a new array, focusing on setTabAt.
synchronized (f) {
// Elements in one position in the original array are moved to two positions in the new array,
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) { // The list is moved to the new array
int runBit = fh & n;
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);
}
setTabAt(nextTab, i, ln); // Set the header of the new array
setTabAt(nextTab, i + n, hn); // Set the header of the new array
setTabAt(tab, i, fwd); // The original array sets the move identifier
advance = true;
}
else if (f instanceof TreeBin) { // The red-black tree is transferred to the new array
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;
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; } } ln = (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); // Set the header of the new array
setTabAt(nextTab, i + n, hn); // Set the header of the new array
setTabAt(tab, i, fwd); // The original array sets the move identifier
advance = true;
}
}
}
}
}
}
Copy the codeThe code for expansion is a bit too much, so I won’t describe it in detail:
- Expansion is to create a new array and put the elements of the original array into the new array
HashMapThe expansion is similar; - use
caswillForwardingNodePut into the node corresponding to the original array, the symbol has moved; Specific seefwdWhere the element is used; - about
synchronizedCode block, you can look at it firstHashMapExpansion, the two are about the same, I won’t go into detail here;
extension
Another point of this method is the while code block, which is where the expansion is accelerated; Here are the details:
while (advance) {
int nextIndex, nextBound;
// Determine whether the phase is complete
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// Calculate the next phase
else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false; }}Copy the codeThis is where I is evaluated, which is the index of an array (bucket); The original array is segmented by (transferIndex-stride); In the case of multithreading, cas is used to ensure thread safety.
Parameters involved: transferIndex: indicates the index of the transfer element. It depends on where the transfer data is moved to; Stride: The number of each transfer, this value is calculated according to the CPU, the minimum value is 16;
That is, when the array length is greater than 16, it will be piecewise accelerated;
Access method
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
/ / calculate the hash
int h = spread(key.hashCode());
// Check whether the hash is initialized and there is data in the bucket
if((tab = table) ! =null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) ! =null) {
// Check if it is the first one
if ((eh = e.hash) == h) {
if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
return e.val;
}
else if (eh < 0) // Check whether the capacity has been expanded
return(p = e.find(h, key)) ! =null ? p.val : null;
while((e = e.next) ! =null) {get directlyif(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
Copy the codeThe find method is in the ForwardingNode class. Instead of the Node class;
Other methods
The remove method
// Delete by key
public V remove(Object key) {
return replaceNode(key, null.null);
}
// Delete by key and value
public boolean remove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
returnvalue ! =null && replaceNode(key, null, value) ! =null;
}
Copy the codeBoth methods call the replaceNode method;
final V replaceNode(Object key, V value, Object cv) {
/ / calculate the hash
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) { / / loop
Node<K,V> f; int n, i, fh;
// Check whether the bucket is initialized and whether the bucket corresponding to key is empty
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// Determine whether to expand the capacity
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) { / / lock
if (tabAt(tab, i) == f) {
if (fh >= 0) { // list traversal
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)))) {
V ev = e.val;
if (cv == null|| cv == ev || (ev ! =null && cv.equals(ev))) {
oldVal = ev;
if(value ! =null)
e.val = value;
else if(pred ! =null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break; }}else if (f instanceof TreeBin) { / / the red-black tree
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) {
V pv = p.val;
if (cv == null|| cv == pv || (pv ! =null && cv.equals(pv))) {
oldVal = pv;
if(value ! =null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
// Check whether the key exists
if(oldVal ! =null) {
if (value == null)// Determine whether to change the capacity value
addCount(-1L, -1);
return oldVal;
}
break; }}}return null;
}
Copy the codeSumCount method
This method evaluates the elements in the container;
Data added by segmented CAS is stored in counterCells; This situation occurs mainly in the case of multiple threads adding conflicts
final long sumCount(a) {
// Get the counterCells value
CounterCell[] as = counterCells; CounterCell a;
// baseCount(in baseCount if uncontested)
long sum = baseCount;
if(as ! =null) {
for (int i = 0; i < as.length; ++i) { / / traverse counterCells
if((a = as[i]) ! =null)
sum += a.value; / / accumulation}}return sum;
}
Copy the codeThe last
reference
- Java magic classes: Unsafe Application parsing
- Java Advanced (6) Java multithreading core technology from the evolution of ConcurrentHashMap
- Concurrent programming – ConcurrentHashMap#helpTransfer() analysis
- ConcurrentHashMap source read summary