ConcurrentHashMap has been optimized in JDK1.8. This article will look at the source code for these optimizations and why they are done. First of all, the following points need to be noted:
- Why use CAS+synchronized instead of Segemnt +ReentrantLock to ensure thread safety
- ConcurrentHashMap Why not allow the key and value to be null
- How to efficiently implement capacity expansion under multiple threads
- Black technology @ sun. Misc. Contended
Storage structure
Jdk1.8 concurrentHashMap has the same storage structure as hashMap. Instead of the segments array of 1.7, each segment is a map and ReentrantLock is implemented for each segment.
Obviously, compared to current implementations, there is a waste of memory.
It takes two hashes to find the real bucket
As shown below:
Synchronized lock optimization
When it comes to synchronized, you probably have the impression that the lock is heavyweight and performs worse than reentrantLock in the context of intense thread contention. For example, this is the JDK1.5 comparison below. Synchronized is the syntactic level of Java synchronization. Java virtual machines can record lock information in thread and object metadata, and the development team put a lot of effort into optimizing synchronized.
Synchronized information can be stored in the metadata of an object. There is a “Mark Word” in the header of the object. Lightweight lock; Heavyweight lock; Bias lock several states. And there will be adaptive spin optimization.
If there is no node in the bucket, either CAS attempts to use the element as a head node without locking it. If there are other elements in it, then the head node f will be locked, locking the list. This means that each bucket is a separate lock, so the chances of different threads simultaneously fighting for the same bucket are very small, and because of the adaptive spin mechanism, even if a fight does occur, the thread will not be suspended, and the spin can wait. In fact, this is already the design idea of optimistic lock.
- ReentrantLock is essentially a pessimistic lock. Even in unfair mode, the CAS will be tried once to obtain the lock. If the LOCK cannot be obtained, it will be added to the AQS waiting queue to try again.
V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
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)
tab = initTable();
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
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 ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! = null) { oldVal = p.val;if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! = 0) {if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! = null)return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the codeEfficient expansion
Expansion is a consumption point, the performance of the hashMap before also mentioned that it is better to forecast need to deposit in the number of data, initialization is set, try to avoid frequent capacity, especially in a multithreaded environment, more need to be careful, combined with “SAO” operation to promote efficiency, can avoid the best.
private final void addCount(long x, int check) { CounterCell[] as; long b, s; // Update baseCount with CAS methodif((as = counterCells) ! = null || ! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {// 1 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)) { A thread that failed to compete will execute fullAddCount(x, uncontended) and insert the value of x into the counterCell class fullAddCount(x, uncontended); / / 2return;
}
if(check <= 1)// If this is not a tree, no need to operatereturn; s = sumCount(); } // If the value of check is greater than or equal to 0, check whether capacity expansion is requiredif(check >= 0) { Node<K,V>[] tab, nt; int n, sc; // Start expansion when conditions are metwhile(s >= (long)(sc = sizeCtl) && (tab = table) ! = null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); // If the value is smaller than 0, some threads are already performing capacity expansionif(sc < 0) {// The following situation indicates that the capacity expansion has been performed by multiple threads or other threads directlybreakDo not enter expansionif((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)break; // If the capacity expansion is performed by another thread // If the capacity expansion is performed by another thread, the capacity expansion is completedif(U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } // If the current thread is the only one or the first thread to initiate the expansion, nextTable=nullelse if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { Node<K,V>[] nextTab; int sc; // Condition: the original node is not empty, this node is a helper node and is not lastif(tab ! = null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! = null) { int rs = resizeStamp(tab.length); //sizeCtl is negative, indicating expansion; If TAB is different from table, capacity expansion is in progresswhile (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0)break; // If the current table length is not changed, other processes are not expandingif (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break; }}return nextTab;
}
return table;
}
Copy the code@sun.misc.Contended
In the source code, CounterCell is annotated by Contended, indicating the elimination of false shares. Because this value represents the number of elements in the bucket, it is often changed, that is, it is often set to invalid in the cache. If there are other variables in the same cache line with it, they will affect each other and reduce concurrency.
@sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; }}Copy the codeThe key value cannot be null
A hashMap allows null keys or values, so why not concurrentHashMap? When get(key) is null, concurrentHashMap cannot tell whether the value corresponding to the key does not exist or the value corresponding to the key itself is null.
