Overall structure (Node array + linked list + red-black tree)
Construction method
- The initial capacity cannot be less than the concurrency level
- Segment in 1.7 is created and loaded, and HashEntry with 0 subscript is initialized. It is improved to lazy loading in 1.8, and only the length of the Node array is calculated during initialization.
- The length is calculated as (1.0 + (long)initialCapacity / loadFactor) which is greater than or equal to the 2nd power of the number.
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {<!-- -->
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
Get method
- Node is used instead of Segment in the construction of 1.8. There is no need to use UNSAFE.getObjectVolatile to ensure visibility when obtaining data.
- Normally all hash values will be set to positive numbers
- The node being expanded will be assigned a value of -1, and the tree node will be -2. Therefore, when it is determined that the hash value of the node is a negative number, it means that it is not a normal linked list structure, and you need to use find to query it.
- If it is a linked list structure, traverse directly to obtain it.
public V get(Object key) {<!-- -->
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// The spread method ensures that the returned result is a positive number
int h = spread(key.hashCode());
if ((tab = table) != null & amp; & amp; (n = tab.length) > 0 & amp; & amp;
(e = tabAt(tab, (n - 1) & amp; h)) != null) {<!-- -->
// If the head node is already the key to be found
if ((eh = e.hash) == h) {<!-- -->
if ((ek = e.key) == key || (ek != null & amp; & amp; key.equals(ek)))
return e.val;
}
// A negative hash indicates that the bin is being expanded or is a treebin. In this case, call the find method to find it.
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//Traverse the linked list normally and use equals to compare
while ((e = e.next) != null) {<!-- -->
if (e.hash == h & amp; & amp;
((ek = e.key) == key || (ek != null & amp; & amp; key.equals(ek))))
return e.val;
}
}
return null;
}
Put
- Before the element is actually put successfully, it will continue to loop endlessly. First, the hash subscript corresponding to the key will be calculated.
- First, the array bucket will be created through spin + CAS. Only the first one who changes sizectl to -1 through CAS operation will indicate that the lock has been obtained. -1 means that initialization or expansion operation is in progress, and -N means that there is N threads are operating, and other threads that have not acquired the lock will call the yield() method to give up the time slice, so that other threads can operate with higher efficiency. After the bucket is successfully created, the elements are added to it through CAS. barrel
- If the element in the bucket is empty, just CAS it directly. No locking operation is required. Exit the put method.
- If it is determined that the hash value of the node is -1 at this time, it means that the old array bucket is being expanded and the subscript of the old array bucket has been expanded. At this time, the thread will help with the expansion process.
- When the array bucket is created and is not in the expansion state, and a Hash conflict occurs at this time, the Synchronized locking operation will be performed. At this time, only the Node node will be locked.
- If the bucket corresponds to a linked list, it will be traversed directly. If there are the same nodes, the overwriting operation will be performed. If not, tail insertion will be used to insert to the end of the linked list.
- Otherwise, it indicates that it is a red-black tree, and the corresponding red-black tree adding node process will be executed.
- After adding the node, if it is a linked list node, the length of the linked list will be recorded. If the length of the linked list reaches 8, the linked list will be converted into a red-black tree. The conversion operation of the red-black tree will perform a Synchronized locking operation and lock the head node.
- When all processes are completed, the values of all nodes recorded in the map will be added, similar to the atomic class
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) {<!-- -->
// key and value cannot be empty
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {<!-- -->
// f = target position element
Node<K,V> f; int n, i, fh; // The hash value of the element at the target location is stored after fh
if (tab == null || (n = tab.length) == 0)
//The array bucket is empty, initialize the array bucket (spin + CAS)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & amp; hash)) == null) {<!-- -->
// The bucket is empty, CAS is put in without locking, and if successful, it will just break out.
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)
tab = helpTransfer(tab, f);
else {<!-- -->
V oldVal = null;
// Use synchronized lock to join the node
synchronized (f) {<!-- -->
if (tabAt(tab, i) == f) {<!-- -->
// Description is a linked list
if (fh >= 0) {<!-- -->
binCount = 1;
// Loop to add new or overwrite nodes
for (Node<K,V> e = f;; + + binCount) {<!-- -->
K ek;
if (e.hash == hash & amp; & amp;
((ek = e.key) == key ||
(ek != null & amp; & amp; key.equals(ek)))) {<!-- -->
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
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) {<!-- -->
// red-black tree
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 (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
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();
// Try setting sizeCtl to -1 (indicating initializing the table)
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {<!-- -->
// Obtain the lock and create the table. At this time, other threads will yield in the while() loop until the table is created.
try {<!-- -->
if ((tab = table) == null || tab.length == 0) {<!-- -->
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {<!-- -->
sizeCtl = sc;
}
break;
}
}
return tab;
}
size count
- The calculation of size will be done during the put and remove processes.
- If there is no competition, a count is made to basecount
- If competition occurs, it will be recorded in countersCells
Expansion process
- By calculating the number of CPU cores, we calculate how many buckets each thread needs to migrate. The number of buckets that each thread needs to migrate is average.
- Calculate the expanded array size, which is twice the original array size
- Each thread handles the expansion of at least 16 buckets, and assigns tasks to each node through CAS operations, that is, initial value and length.
- The processed node will set the node ID to forward, that is, the flag bit -1
private final void addCount(long x, int check) {<!-- -->
CounterCell[] cs; long b, s;
if ((cs = counterCells) != null ||
!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {<!-- -->
CounterCell c; long v; int m;
boolean uncontended = true;
if (cs == null || (m = cs.length - 1) < 0 ||
(c = cs[ThreadLocalRandom.getProbe() & amp; m]) == null ||
!(uncontended =
U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {<!-- -->
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {<!-- -->
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) & amp; & amp; (tab = table) != null & amp; & amp;
(n = tab.length) < MAXIMUM_CAPACITY) {<!-- -->
int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
if (sc < 0) {<!-- -->
if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
(nt = nextTable) == null || transferIndex <= 0)
break;
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
transfer(tab,nt);
}
else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
transfer(tab, null);
s = sumCount();
}
}
}
/**
* 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 & amp; & amp; (f instanceof ForwardingNode) & amp; & amp;
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {<!-- -->
int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
while (nextTab == nextTable & amp; & amp; table == tab & amp; & amp;
(sc = sizeCtl) < 0) {<!-- -->
if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
transferIndex <= 0)
break;
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {<!-- -->
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
Why use Synchronized instead of ReentrantLock
Lock granularity
- In JDK7, the combination of
**Segment + Entry**is used. Segment is inherited from**ReentrantLock**. When performing a Put operation, you need to**Obtain the Segment lock**before you can perform the operation, that is, lock the entire Segment - And the Segment in JDK7 is fixed after
** initialization**. When the amount of data is large, the Segment will contain many Entry nodes. When these Entry nodes need to be put, , both need to acquire Segment locks. At this time, frequent waiting for locks is required. - Optimized to Node in JDK8, when performing a Put operation, you need to obtain the Synchronized lock of the
**linked list head node Node**, that is,**lock the linked list where the Node node is located** - In JDK8,
** reduces the granularity of locks**, which reduces lock competition. Therefore, the concurrency efficiency of JDK8 will be stronger than that of JDK7.
Lock efficiency
- Because the lock granularity in JDK8 lies in the head node of the linked list, which is much smaller than the Segment in JDK7, there are actually fewer lock competitions in JDK8.
- After Synchronized has been optimized with
**bias locks, spin locks, etc.**, the performance has been much better than before. At this time, the situation in JDK8 is a situation where lock competition is small, and there is a greater possibility By spinning,**after dozens of retries**can obtain the lock without upgrading to a heavyweight lock. - After ReentrantLock fails to acquire the lock for the first time, it will only try to acquire the lock once after adding a new node. If
** fails to acquire the lock twice, it will be suspended by LockSupport.park()**, the suspension operation is the same as Synchronized acquisition of heavyweight locks. It needs to switch to the kernel state, which is very time-consuming. - Therefore, based on the low concurrency situation based on Node in JDK8, it is more appropriate to use Synchronized
Why ConcurrentHashMap does not allow null
- In the put method of
**ConcurrentHashMap**, it will be judged whether the key and value are null. If they are**null, a null pointer exception will be thrown**
final V putVal(K key, V value, boolean onlyIfAbsent) {<!-- -->
// key and value cannot be empty
if (key == null || value == null) throw new NullPointerException();
- In HashMap,
** is allowed to store**with null value,** one key**is allowed to be null, and** multiple values are allowed. **is null - The reason why ConcurrentHashMap does not allow to store null values is that
**ambiguity is not allowed**. After the get method returns null, it is impossible to determine whether the value is null or the key does not exist. - HashMap is thread-unsafe and is executed in
**single-threaded environment**by default. After the get method returns null, HashMap can be returned by**containsKey**The value determines whether the null value exists or does not exist. HashMap default key is null hash value is 0 - However, ConcurrentHashMap is a thread-safe collection. After the get method returns null, and then uses containsKey to determine whether it exists, other threads may modify the key in the interim, and the returned result may not be the real result at that time, so it will Create ambiguity.
- To avoid this ambiguity, ConcurrentHashMap does not allow null values to be stored.