ConcurrentHashMap (JDK1.7 and 1.8)

preface

I wrote about HashMap earlier (blog.csdn.net/qq_27574367…) When a HashMap is put and the number of elements inserted exceeds its capacity (determined by the load factor), a rehash operation is triggered. This will rehash the contents of the original array into the new array. In a multi-threaded environment, other elements are put at the same time. If the hash value is the same, it can be represented in a linked list under the same array, resulting in a closed loop, resulting in an infinite loop during get, so a HashMap is thread unsafe.

Another set of key-value stores, HashTable, is thread-safe. It uses the synchronized keyword to lock the table as a whole, which means that all threads are competing for a lock. In a multi-threaded environment, HashTable is safe but inefficient. In fact, HashTable has a lot of optimization space, locking the whole table such a rude method can be changed to a soft point, for example, in the multi-threaded environment, when operating on different data sets, actually there is no need to compete for a lock, because they have different hash values, there is no thread unsafe due to rehash, so it does not affect each other. This is the lock separation technology, which reduces the granularity of locks and uses multiple locks to control multiple small tables. This is the core idea of ConcurrentHashMap JDK1.7, the main character of this article.

ConcurrentHashMapIn JDK1.7, the data structure of ConcurrentHashMap consists of an array of segments and multiple hashentries, as shown in the following figure:The meaning of the Segment array is to divide a large table into multiple small tables for locking, namely the lock separation technique mentioned above. Each Segment element stores a HashEntry array + linked list, which is initialized in the same way as the data storage structure of HashMap

ConcurrentHashMap initializes the size of the Segment by bit and operation, denoted by ssize, as shown below

int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
}
Copy the code

As shown above, since ssize is calculated by location operation (ssize <<=1), the size of the Segment is 2 to the power of N, regardless of the value of concurrencyLevel. Of course, concurrencyLevel can only be expressed in the maximum 16-bit binary, i.e. 65536. In other words, the size of a Segment is 65536 at most, and the concurrencyLevel element is not specified for initialization. The size of the Segment ssize is 16 by default. As shown below.

int cap = 1;
while (cap < c)
    cap <<= 1;
Copy the code

As shown above, the size of a HashEntry is also calculated as 2 to the power of N (cap <<=1). Cap starts with 1, so the minimum size of a HashEntry is 2

The put operation

For data inserts in ConcurrentHashMap, two Hash attempts are made to locate the storage location

static class Segment<K,V> extends ReentrantLock implements Serializable {
Copy the code

When performing a put operation, the first key hash is performed to locate the Segment. If the Segment has not been initialized, the CAS operation is used to assign values to the Segment. A second hash operation is then performed to find the corresponding HashEntry location. This takes advantage of the inherited lock properties and attempts to obtain the lock by inheriting the tryLock () method of ReentrantLock when inserting data into the specified HashEntry location (the end of the list). If the Segment is successfully acquired, the thread inserts the Segment directly into the corresponding location. If another thread has already acquired the Segment, the current thread spins to the tryLock () method to obtain the lock, suspends the Segment after the specified number of times, and waits to wake up

Get operation

The get operation of ConcurrentHashMap is similar to that of HashMap, except that the ConcurrentHashMap first hashes to locate the Segment and then hash to locate the specified HashEntry. Iterate over the linked list of the HashEntry for comparison, return on success, return null size on failure

Calculating the size of a ConcurrentHashMap element is an interesting problem, because it is concurrent, that is, while you calculate the size, it is also concurrent to insert data, which may cause the calculated size to differ from the actual size (when you return the size, To solve this problem, JDK1.7 uses two solutions

try {
    for (;;) {
        if (retries++ == RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation
        }
        sum = 0L;
        size = 0;
        overflow = false;
        for (int j = 0; j < segments.length; ++j) {
            Segment<K,V> seg = segmentAt(segments, j);
            if (seg != null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) < 0)
               overflow = true;
            } }
        if (sum == last) break;
        last = sum; } }
finally {
    if (retries > RETRIES_BEFORE_LOCK) {
        for (int j = 0; j < segments.length; ++j)
            segmentAt(segments, j).unlock();
    }
}
Copy the code

In the first scheme, he will try to calculate the size of ConcurrentHashMap several times in unlocked mode, at most three times, and compare the results of the previous two calculations. If the results are consistent, it will be considered that no element is added and the calculation result is accurate

If the first Segment does not fit, then lock each Segment and calculate the size of the ConcurrentHashMap

The realization of the JDK1.8

The implementation of JDK1.8 has discarded the concept of Segment and implemented Node arrays + linked lists + red-black tree data structures. Concurrency control is implemented using Synchronized and CAS, and the whole thing looks like an optimized and thread-safe HashMap. Although you can still see the data structure of segments in JDK1.8, the attributes have been simplified to make them compatible with older versionsBefore delving into the PUT and GET implementations of JDK1.8, there are some constants and data structures that form the basis of the ConcurrentHashMap implementation structure. Here’s a look at the basic properties:

// Node Array maximum capacity: 2^30=1073741824 Private static final int MAXIMUM_CAPACITY =1 << 30; Private static final int DEFAULT_CAPACITY = 16; private static final int DEFAULT_CAPACITY = 16; Static final int MAX_ARRAY_SIZE = integer.max_value - 8; static final int MAX_ARRAY_SIZE = integer.max_value - 8; Private static Final Int DEFAULT_CONCURRENCY_LEVEL = 16; private static final int DEFAULT_CONCURRENCY_LEVEL = 16; Private static final float LOAD_FACTOR = 0.75f; Static final int TREEIFY_THRESHOLD = 8; static final int TREEIFY_THRESHOLD = 8; // Tree list threshold, < or equal to 6 (tranfer, lc, HC =0) <=UNTREEIFY_THRESHOLD then untreeify(lo) static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; private static final int MIN_TRANSFER_STRIDE = 16; private static int RESIZE_STAMP_BITS = 16; // 2^15-1, help resize Private static final int MAX_RESIZERS = (1 << (32-resize_stamp_bits)) -1; Private static final int RESIZE_STAMP_SHIFT = 32-resize_stamp_bits; private static final int RESIZE_STAMP_SHIFT = 32-resize_stamp_bits; // Hash value of forwarding Nodes static final int MOVED = -1; Static final int TREEBIN = -1; static final int TREEBIN = -1; // ReservationNode hash static final int RESERVED = -3; Static final int NCPU = Runtime.getruntime ().availableprocessors (); // Transient volatile node <K,V>[] table; /* The control identifier is used to control the initialization and expansion of the table. Different values have different meanings. * If the value is negative, -1 indicates that the table is being initialized, and -n indicates that n-1 threads are expanding the table. Private TRANSIENT volatile int sizeCtl;Copy the code

The basic properties define some of the ConcurrentHashMap boundaries and some of the controls that operate them. Here are some of the internal structure components that are the core nodes of the ConcurrentHashMap data structure

Node is the basic unit of the ConcurrentHashMap storage structure, which is inherited from Entry in the HashMap and used to store data. The source code is as follows

Static class Node<K,V> implements map. Entry<K,V> {// Final int hash; final K key; // Both val and next will change during expansion, so volatile is used to maintain visibility and disallow reordering of volatile V val; volatile Node<K,V> next; Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); } public final String toString(){ return key + "=" + val; } / / not allowed to update the value of public final V setValue value (V) {throw new UnsupportedOperationException (); } public final boolean equals(Object o) { Object k, v, u; Map.Entry<? ,? > e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry<? ,? >)o).getKey()) ! = null && (v = e.getValue()) ! = null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } Node<K,V> find(int h, Object K) {Node<K,V> e = this; if (k ! = null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek ! = null && k.equals(ek)))) return e; } while ((e = e.next) ! = null); } return null; }}Copy the code

The Node data structure is a simple linked list, but only allows data to be searched, not modified

TreeNode

TreeNode inherits Node, but its data structure is changed into a binary tree structure, which is the data storage structure of a red-black tree. It is used to store data in a red-black tree. When the number of nodes in the linked list is greater than 8, it will be converted into a red-black tree structure

Static final class TreeNode<K,V> extends Node<K,V> {TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next, TreeNode<K,V> parent) {super(hash, key, val, next); this.parent = parent; } Node<K,V> find(int h, Object k) { return findTreeNode(h, k, null); } final TreeNode<K,V> findTreeNode(int h, Object K, Class<? > kc) { if (k ! = null) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> q; TreeNode<K,V> pl = p.left, pr = p.right; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (pk ! = null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc ! = null || (kc = comparableClassFor(k)) ! = null) && (dir = compareComparables(kc, k, pk)) ! = 0) p = (dir < 0) ? pl : pr; else if ((q = pr.findTreeNode(h, k, kc)) ! = null) return q; else p = pl; } while (p ! = null); } return null; }}Copy the code

TreeBin

TreeBin is a container that stores tree structures, and tree structures refer to TreeNode, so TreeBin is a container that encapsulates TreeNode. It provides some conditions and lock control for converting black mangroves. The source code structure is as follows

Static final Class TreeBin<K,V> extends Node<K,V> {// TreeNode<K,V> root; volatile TreeNode<K,V> first; volatile Thread waiter; volatile int lockState; Static final int WRITER = 1; Static final int WAITER = 2; Static final int READER = 4; TreeBin(TreeNode<K,V> b) {super(TreeBin, null, null, null); this.first = b; TreeNode<K,V> r = null; for (TreeNode<K,V> x = b, next; x ! = null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (r == null) { x.parent = null; x.red = false; r = x; } else { K k = x.key; int h = x.hash; Class<? > kc = null; for (TreeNode<K,V> p = r;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; r = balanceInsertion(r, x); break; } } } } this.root = r; assert checkInvariants(root); }... }Copy the code

This section describes the main attributes and internal data structures of ConcurrentHashMap. Now use a simple example to view the details of ConcurrentHashMap operations from the perspective of DEBUG

public class TestConcurrentHashMap{ public static void main(String[] args){ ConcurrentHashMap<String,String> map = new ConcurrentHashMap(); // Initialize ConcurrentHashMap // Add personal information map.put("id","1"); map.put("name","andy"); The map. The put (" sex ", "male"); String name = map.get("name"); Assert.assertEquals(name,"andy"); Int size = map.size(); Assert.assertEquals(size,3); }}Copy the code

We initialize it with new ConcurrentHashMap()

public ConcurrentHashMap() {
}
Copy the code

As you can see above, the initialization of ConcurrentHashMap is an empty implementation that doesn’t do anything, and as we’ll see later, it differs from other collection classes in that it’s not done in the constructor, it’s done in the PUT operation, Of course, ConcurrentHashMap also provides other constructors that specify capacity or load factors, just like HashMap. Put is not covered here

In the example above, when we add personal information, we call the PUT method. Let’s take a look

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) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); Int binCount = 0; for (Node<K,V>[] tab = table;;) {// Iterate over the table Node<K,V> f; int n, i, fh; // initialize table (); // initialize table (); Belong to the lazy mode initialization 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)// If (fh = helpTransfer(TAB, f); else { V oldVal = null; // If none of the above conditions are met, then the lock operation is performed. Synchronized (f) {if (tabAt(TAB, I) == f) {if (fh >= 0) {// Synchronized (f) {if (tabAt(TAB, I) == f) { for (Node<K,V> e = f;; ++binCount) { K ek; / / here comes to the same key to put will cover the original value of the if (e.h ash = = hash && (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) { oldVal = e.val; if (! onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; Next = new Node<K,V>(hash, key, value, null); break; }}} else if (f instanceof TreeBin) {if (f instanceof TreeBin) { binCount = 2; If ((p = ((TreeBin<K,V>)f).puttreeval (hash, key, value))! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; } } } } if (binCount ! If (binCount >= TREEIFY_THRESHOLD) treeifyBin(TAB, I); if (binCount >= TREEIFY_THRESHOLD) treeifyBin(TAB, I); if (oldVal ! = null) return oldVal; break; } } } addCount(1L, binCount); // Count size and check whether return null needs to be expanded; }Copy the code

The put process is very clear. We loop through the current table unconditionally until the put succeeds. This can be summarized in the following six steps: if there is no initialization, call initTable () first. If there is no hash conflict, insert CAS directly. If capacity expansion is still in progress, expand capacity first. One is to iterate to the end of the linked list, the other is to insert according to the red-black tree structure, and the last one is if the number of the linked list is greater than the threshold 8, the structure of the black mangrove should be converted first, break enters the loop again, and addCount () method will be called to count the size if it is added successfully. In the first step, initialization is performed if conditions are met. Let’s look at the initTable () method

/** * 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. The length = = 0) {/ / empty table can enter initialization if (= sizeCtl (sc) < 0) Thread.yield(); //sizeCtl<0; thread.yield (); // lost initialization race; Just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { Said the initialization state try {if ((TAB = table) = = null | | TAB. The length = = 0) {int n = > 0 (sc)? Sc: DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n]; Table = TAB = nt; sc = n - (n >>> 2); }} finally {sizeCtl = sc; } break; } } return tab; }Copy the code

In step 2, CAS inserts the element without hash collisions. In step 3, if the container is expanding, the helpTransfer () method is called to help expand. Now let’s look at the helpTransfer () method

/** * Help copy elements from old table to new table */ Final Node<K,V>[] helpTransfer(Node<K,V>[] TAB, Node<K,V> f) {Node<K,V>[] nextTab; int sc; if (tab ! = null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! Int rs = resizeStamp(tab.length); while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { transfer(tab, nextTab); // Call break; } } return nextTab; } return table; }Copy the code

The purpose of the helpTransfer () method is to call multiple worker threads to help with capacity expansion, so that it’s more efficient, rather than having to check for the one thread to expand capacity and wait for the other threads to complete capacity expansion since capacity expansion is involved, Transfer ()

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 if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n << 1]; NextTab = nt; // Build a nextTable with twice the capacity nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; // Join point pointer used to mark bits (FWD hash value is -1, fwD.nexttable =nextTab) ForwardingNode<K,V> FWD = new ForwardingNode<K,V>(nextTab); // Advance == true indicates that the object has already been processed. 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; Else if (U.compareAndSwapInt (this, transferIndex, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { int sc; If (finishing) {nextTable = null; table = nextTab; // Table points to nextTable sizeCtl = (n << 1) - (n >>> 1); // sizeCtl = 1.5x return; } // CAS increases the size of the threshold, in which the sizectl value is reduced by one, 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; If (tabAt(TAB, I) == f) {Node<K,V> ln, hn; If (fh >= 0) {int runBit = fh&n; 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); } // Insert setTabAt(nextTab, I, ln) at nextTable I; // Insert setTabAt(nextTab, I + n, hn) at nextTable I + n; // Insert ForwardingNode at table I to indicate that the node has already been setTabAt(TAB, I, FWD); Advance = true; advance = true; advance = true; 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; 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; else hiTail.next = p; hiTail = p; ++hc; }} // If the number of tree nodes is less than =6 after capacity expansion, convert the tree list to ln = (lc <= UNTREEIFY_THRESHOLD)? untreeify(lo) : (hc ! = 0)? new TreeBin<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 code

The purpose of the helpTransfer () method is to call multiple worker threads to help with capacity expansion, so that it’s more efficient, rather than having to check for the one thread to expand capacity and wait for the other threads to complete capacity expansion since capacity expansion is involved, Transfer ()

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 if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n << 1]; NextTab = nt; // Build a nextTable with twice the capacity nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; // Join point pointer used to mark bits (FWD hash value is -1, fwD.nexttable =nextTab) ForwardingNode<K,V> FWD = new ForwardingNode<K,V>(nextTab); // Advance == true indicates that the object has already been processed. 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; Else if (U.compareAndSwapInt (this, transferIndex, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { int sc; If (finishing) {nextTable = null; table = nextTab; // Table points to nextTable sizeCtl = (n << 1) - (n >>> 1); // sizeCtl = 1.5x return; } // CAS increases the size of the threshold, in which the sizectl value is reduced by one, 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; If (tabAt(TAB, I) == f) {Node<K,V> ln, hn; If (fh >= 0) {int runBit = fh&n; 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); } // Insert setTabAt(nextTab, I, ln) at nextTable I; // Insert setTabAt(nextTab, I + n, hn) at nextTable I + n; // Insert ForwardingNode at table I to indicate that the node has already been setTabAt(TAB, I, FWD); Advance = true; advance = true; advance = true; 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; 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; else hiTail.next = p; hiTail = p; ++hc; }} // If the number of tree nodes is less than =6 after capacity expansion, convert the tree list to ln = (lc <= UNTREEIFY_THRESHOLD)? untreeify(lo) : (hc ! = 0)? new TreeBin<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 code

The capacity expansion process is a little complicated, which mainly involves multi-threaded concurrent capacity expansion. The function of ForwardingNode is to support the capacity expansion operation. The processed nodes and empty nodes are set as ForwardingNode. The following figure shows the process of multi-threaded cooperation expansion:After introducing the expansion process, we return to the PUT process. In step 4, we add nodes to the list or red-black tree. In step 5, we call the treeifyBin () method to convert the list to a red-black tree

private final void treeifyBin(Node<K,V>[] tab, int index) { Node<K,V> b; int n, sc; if (tab ! = null) {// If the number of tables in the table is less than 64, expand the table to double the number of tables. If ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); else if ((b = tabAt(tab, index)) ! = null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode<K,V> hd = null, tl = null; for (Node<K,V> e = b; e ! = null; E = e.next) {// Encapsulate TreeNode TreeNode<K,V> p = new TreeNode<K,V>(e.bash, e.ey, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } // Convert TreeNode to a setTabAt(TAB, index, new TreeBin<K,V>(hd)); } } } } }Copy the code

Now call addCount() to calculate the size of ConcurrentHashMap and add one to it. Now look at the addCount() method

private final void addCount(long x, int check) { CounterCell[] as; long b, s; // Update baseCount, table number, counterCells 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; // If multiple threads are executing, CAS fails, execute fullAddCount, All join the count the if (as = = null | | (m = as length - 1) < 0 | | (a = as [ThreadLocalRandom. GetProbe () & m]) = = null | |! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } //check>=0 if (check >=0) {Node<K,V>[] TAB, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) ! = null && (n = tab.length) < MAXIMUM_CAPACITY) { 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; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } // The current thread initiates the library oh-oh-let operation, nextTable=null else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); }}}Copy the code

The process of PUT has been analyzed. As you can see, it uses an optimistic lock in concurrent processing, and only performs concurrent processing when there is a conflict. The process steps are clear, but the details are complicated

We are now going to go back to the original example, after we add personal information, we want to get the new information, using String name = map.get(” name “) to get the new name information, Get () ConcurrentHashMap get()

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); // Hash if ((TAB = table)! = null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) ! = null) {/ / read the first Node if the Node of elements (eh = e.h (ash) = = h) {/ / if the Node is the first Node is returned if (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek))) return e.val; Else if (eh < 0) return (p = e.type (h, key))! = null ? p.val : null; while ((e = e.next) ! First node = null) {/ / is neither nor ForwardingNode, then to traverse the if (e.h ash = = h && (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) return e.val; } } return null; }Copy the code

The get operation of ConcurrentHashMap is simple and clear. It can be divided into three steps to calculate the hash value, locate the index position of the table, and return the value if the first node matches. The find method that marks the ForwardingNode is being expanded is called to find the node and return null size if the node matches none of the above

Int size = map.size(); int size = map.size(); Now let’s look at the size() method

public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } final long sumCount() { 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

In JDK1.8, the size calculation is handled by the addCount() method. In JDK1.7, the size calculation is performed by calling the size() method. In JDK1.8, the size calculation is performed by calling the size() method. However, a moment is too fast, and human perception is a period of time, so it is not very accurate

Summary and Reflection

The ConcurrentHashMap data structure is similar to that of HashMap. ConcurrentHashMap only adds synchronous operations to control concurrency. From JDK1.7’s ReentrantLock+Segment+HashEntry to JDK1.8’s synchronized+CAS+HashEntry+ red-black tree, we can sum up the following:

The JDK1.8 implementation reduces the granularity of locks. The JDK1.7 version locks are segment-based and contain multiple hashentries, whereas the JDK1.8 lock granularity is HashEntry.

JDK1.8’s data structure has become simpler, making the operation more clear and smooth, because synchronized has been used to synchronize, so there is no need for the concept of Segment lock, so there is no need for data structure such as Segment, due to the reduction of granularity, implementation complexity has increased

JDK1.8 uses red-black trees to optimize linked lists. Traversal based on long linked lists is a long process, and red-black trees traversal efficiency is fast, instead of a certain threshold of linked lists, so as to form an optimal partner

Synchronized is not inferior to ReentrantLock in terms of low granularity. In coarse-grained locking, ReentrantLock can be more flexible using Condition to control various low-granularity boundaries, whereas in low-granularity locking, Condition’s advantages are lost and JVM development teams have never abandoned synchronized, In addition, synchronized optimization based on JVM has a larger space, and the use of embedded keywords is more natural than the USE of API. In the case of a large number of data operations, API-based ReentrantLock will consume more memory for the MEMORY pressure of JVM. Although it is not a bottleneck, it is also a selection basis

Source: www.cnblogs.com/study-every…