1. ConcurrentHashMap
- Relevant properties
// Maximum capacity 2 to the 30th power
private static final int MAXIMUM_CAPACITY = 1 << 30;
// Default initial capacity
private static final int DEFAULT_CAPACITY = 16;
// The maximum size of an array, mainly used by the toArray() method
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// Number of concurrent requests, not used in jdk1.8
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// Load factor
private static final float LOAD_FACTOR = 0.75 f;
// If the number of nodes in the list is greater than 8, turn to red black tree
static final int TREEIFY_THRESHOLD = 8;
// If the number of nodes in a red-black tree is less than 6, the tree becomes a linked list
static final int UNTREEIFY_THRESHOLD = 6;
// If the hash attribute of the node is MOVED, the map is being expanded
static final int MOVED = -1;
// is -2, indicating that this element is followed by a red-black tree
static final int TREEBIN = -2;
static final int RESERVED = -3;
// It is used to compute Hash values
static final int HASH_BITS = 0x7fffffff;
// This is used for capacity expansion
ForwardingNode
// The container's counter can represent the length of elements in the container when there are no races
private transient volatile long baseCount;
Tab. length*LOAD_FACTOR(factor 0.75) indicates that initialization is complete. **/
private transient volatile int sizeCtl;
Copy the code-
The PUT method, JDK1.8 ConcurrentHashMap, is thread-safe based on CAS and synchronized
- PutVal (K key, V value, Boolean onlyIfAbsent) method
final V putVal(K key, V value, boolean onlyIfAbsent) { // Check key and value if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) {/ / death cycle // f is the head node Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0)// If the array is not initialized, the array is initialized tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// Get the node with I subscript in the current TAB, which is actually a linked list or red-black tree head node // Cas operation, if the current TAB head node at index I is null, create a new node and add it to index I if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null))) break; } else if ((fh = f.hash) == MOVED)// Help expand capacity tab = helpTransfer(tab, f); else { // List processing V oldVal = null; // lock f for the head node synchronized (f) { // Check whether the newly obtained node is equal to f again. If not, the loop starts again. If so, the next step is performed 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; } // Assign e to pred, then e=e.next; Loop until the last node of the current list, then create a new node with the new key value and append it to the end of the current list. 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 operation 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; }}}}// The current key value is successfully added if(binCount ! =0) { // Determine if you need to convert to a red-black tree if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if(oldVal ! =null) return oldVal; break; }}}// After the element is added, count the number of elements and verify whether the element needs to be expanded addCount(1L, binCount); return null; } Copy the code- InitTable () method
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { // Indicates that the initialization is already underway, releasing CPU resources until the loop is broken after TAB initialization if ((sc = sizeCtl) < 0) //yield() yields a CPU resource and then competes for it again Thread.yield(); else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {// Cas operation, assign -1 to SIZECTL 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;// This calculation is equivalent to n*0.75(loading factor) sc = n - (n >>> 2); }}finally { sizeCtl = sc; } break; }}return tab; } Copy the code- casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v)
// Use cas to add node to TAB at subscript I, which is the head node 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 code- Final Node
[] helpTransfer(Node
[] TAB, Node
f) final Node
[] helpTransfer(Node
[] TAB, Node
f
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { Node<K,V>[] nextTab; int sc; // Expansion can be performed only when the following conditions are met if(tab ! =null && (f instanceofForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! =null) { int rs = resizeStamp(tab.length); // loop, using cas to form a spin lock 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)) { / / capacity transfer(tab, nextTab); break; }}return nextTab; } return table; } Copy the code- Private final void Transfer (Node
[] TAB, Node
[] nextTab) expansion method, mainly using high-low algorithm
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) {// Initialize the new array try { //n << 1 The new array is twice as long as the previous one 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; // Create a placeholder node to indicate that the map is being expanded ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); boolean advance = true; 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; 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) advance = casTabAt(tab, i, null, fwd); else if ((fh = f.hash) == MOVED) advance = true; // already processed else { synchronized (f) { if (tabAt(tab, i) == f) { //ln, the low level node, which does not change its array subscript during expansion //hn high level node, this node will be moved back during expansion, the new subscript in the array is the current subscript + expansion length Node<K,V> ln, hn; if (fh >= 0) { // The reason for this calculation is that the map uses the high-low algorithm for capacity expansion, which will be explained later int runBit = fh & n; Node<K,V> lastRun = f; //lastRun defaults to the head of the list, loop the list, to determine whether the current list all conform to ln or hn 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; } // If the head of the current list is not equal to lastRun, there are nodes in the list that need to be moved. Rebuild the node 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); } // Place ln and hn at the corresponding subscripts of the new array setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); // Place the placeholder node at the subscript of the old array I setTabAt(tab, i, fwd); advance = true; } // Red black tree processing 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; 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); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } } } Copy the code- High-low algorithm
int runBit = fh & n; Hash value of the head node & the length of the original array. If it is 0, the node will remain at the original subscript of the array during migration; otherwise, the new subscript of migration is the current subscript + the expanded length. It has to do with the algorithm that gets the subscript position of the node in the array that I = (n-1) &hash
Figure (a) shows the example of determining the index position of key1 and KEY2 before capacity expansion, and Figure (b) shows the example of determining the index position of key1 and KEY2 after capacity expansion, where Hash1 is the hash and high-order operation result corresponding to key1. After the element recalculates the hash, the mask range of n-1 is 1bit more (red) at the high end, so the new index changes this way
So what does that mean? Well, by calculating this, any number to the NTH power of 2 is either equal to 0 or equal to 2 to the NTH power. When the number equal to 0 happens to pass I = (n-1) &the hash index is exactly the index before the expansion. If the number is not equal to 0, the subscript obtained after calculation is exactly the subscript before expansion plus the length of expansion.
- Private final void addCount(long x, int check), addCount and check whether expansion is required
private final void addCount(long x, int check) { //CounterCell counter array CounterCell[] as; long b, s; // Cas operation to assign baseCount if((as = counterCells) ! =null| |! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; // Randomly fetch CounterCell from as array and assign cas to value property in CounterCell if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null| |! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {// More on that later fullAddCount(x, uncontended); return; } if (check <= 1) return; // Count the quantity s = sumCount(); } // Handle capacity expansion if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; //s >= (long)(sc = sizeCtl) : Capacity expansion is required 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); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); }}}Copy the code
