preface

Welcome to our GitHub repository Star: github.com/bin39232820… The best time to plant a tree was ten years ago, followed by now

omg

Having done with HashMap, let’s look at ConcurrentHashMap, which has a similar internal structure

🔥 Introduction to the most complete Collection of Java containers 🔥 the most complete collection of Java containers the most basic data structures (hand tear list) 🔥 the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers 🔥 Equals and hashCode 🔥 HashMap of the most complete Java container collection

ConcurrentHashMap is used to solve thread-safe problems, and HashTable is used to solve thread-safe problems.

ConcurrentHashMap

Thread-safe container is a thread safe container. It is a thread safe container. Thread-safe container is a thread safe container

  • Pessimistic locks and optimistic locks
  • Atomicity, instruction ordering, and thread visibility
  • Lock-free algorithm
  • The memory barrier
  • Java memory model

We’ll talk about that for now when we talk about the JVM, but we’ll just go through it today, and we’ll see what happens when we put it all together.

HashTable 1.7 vs. 1.8

ConcurrentHashMap is a class in the ConcCurrent family. Because it supports concurrent operations efficiently and is widely used, the classical open source framework Spring uses ConcurrentHashMap to implement the underlying data structures. It’s already a step up from its thread-safe big brother, HashTable, and as a result its locks are more detailed than the synchronized locks that HashTable adds to almost every method, which can undoubtedly affect performance.

In 1.7 and 1.8, the idea of thread safety has been completely changed, in which the original Segment locking is abandoned, and CAS + synchronized is adopted to ensure concurrency security. It follows the philosophy of its contemporary version of HashMap. The bottom layer is still “array” + linked list + red-black tree, but in order to achieve concurrency, a number of auxiliary classes are added, such as TreeBin, Traverser and other internal object classes.

Inheritance structure

It’s exactly like HashMap

In fact, a class is used for what kind of the beginning of the introduction is very detailed, but my poor English level, too difficult, if the ability of children shoes can go to have a good look. To sum up what was said:

  • Underlying JDK1.8 is a hash table + red-black tree
  • ConCurrentHashMap supports highly concurrent access and updates and is thread-safe
  • The retrieve operation is unlocked, and the GET method is non-blocking
  • Neither key nor value can be null

constant

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; // Default concurrency level 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 UNTREEIFY_THRESHOLD = 6; Static final int MIN_TREEIFY_CAPACITY = 64; static final int MIN_TREEIFY_CAPACITY = 64; Private static final int MIN_TRANSFER_STRIDE = 16; Private static int RESIZE_STAMP_BITS = 16; Private static final int MAX_RESIZERS = (1 << (32-resize_stamp_bits)) - 1; private static final int MAX_RESIZERS = (1 << (32-resize_stamp_bits)) - 1; Private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; Static final int MOVED = -1; // hash for forwarding nodes static final int TREEBIN = -2; // hash for roots of trees static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // Usable bits of normal node hash static final int NCPU = Runtime.getruntime (). AvailableProcessors (); // Usable bits of normal node hash Private static final ObjectStreamField[] serialPersistentFields = {new ObjectStreamField("segments", Segment[].class), new ObjectStreamField("segmentMask", Integer.TYPE), new ObjectStreamField("segmentShift", Integer.TYPE) };Copy the code

Most are similar to HashMap, with a few differences

Member variables

Transient volatile node <K,V>[] table; transient volatile node <K,V>[] table; Private TRANSIENT volatile Node<K,V>[] nextTable; Private TRANSIENT Volatile long baseCount; private transient volatile long baseCount; // A concurrent package has many similar uses // -1 is being initialized; -N (n-1) Threads are expanding. Table has no data initialization size; SizeCtl = -(1 + nThreads), sizeCtl = -(1 + nThreads), SizeCtl > 0, the size to be used in the actual initialization operation, or threshold // sizeCtl = 0 after the initialization/capacity expansion is complete, default, //sizeCtl = -(1 + nThreads) // ConcurrentHashMap of 16 sizes is constructed by default. SizeCtl = -2145714174 when there is only one thread running the capacity expansion task, // The sizeCtl value should be -(1 + 1) = -2. -(1 + nThreads) // Actually uses a generate stamp, which is used to calculate the base of the generated stamp, so that the different rounds of the expansion operation are unique, to ensure that there is no overlapping between multiple threads. SizeCtl {sizeCtl = (cardinality + n) // 1.8.0_111, line 383-384: A generation stamp in field sizeCtl ensures that resizings do not overlap. private transient volatile int sizeCtl; ** * The next table index (plus one) to split while resizing. */ /transfer table index private transient volatile int transferIndex; // Expand or create counterCells spin lock private TRANSIENT volatile int cellsBusy; // CounterCell array private TRANSIENT CounterCell[] counterCells; // views private transient KeySetView<K,V> keySet; private transient ValuesView<K,V> values; private transient EntrySetView<K,V> entrySet;Copy the code

I’m going to focus on sizeCtl. It is a highly visible attribute in ConcurrentHashMap because it is a control identifier that has different uses in different places and has different values that represent different meanings.

  • A negative value indicates that initialization or capacity expansion is in progress
  • -1 indicates initialization
  • -n Indicates that N-1 threads are performing capacity expansion
  • A positive value or 0 indicates that the hash table has not been initialized. This value indicates the size of the initialization or next expansion, which is similar to the concept of expansion threshold. As you will see later, its value is always 0.75 times the capacity of the current ConcurrentHashMap, which corresponds to loadFactor.

A constructor

The constructor logic of ConcurrentHashMap is basically the same as that of HashMap, except for the addition of concurrencyLevel and SizeCtl. And it doesn’t initialize the table, it doesn’t initialize the table until the first put,

Members of the method

ConcurrentHashMap#initTable()

So in our put method, we’re going to first check if our table is null and if it’s null, then we’re going to initialize our method

private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; While (= (TAB table) = = null | | TAB. The length = = 0) {if (= sizeCtl (sc) < 0) / / sizeCtl < 0 other threads are marked initialized is operating, the thread to yield the CPU, For cook operations on tables, only one Thread can perform thread.yield (); // lost initialization race; SIZECTL, sc, -1) {if (U.compareAndSwapInt(this, SIZECTL, sc, -1) {if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { SizeCtl <0 // If the initialization is not complete by the time of the next loop, the logic of if <0 goes to the top and the CPU goes out // If the next loop is complete, Is the table length! =0, exit loop try {<br> If go to the following the finally changed sizeCtl value, is likely to other threads will enter this logic the if ((TAB = table) = = null | | TAB. The length = = 0) {int n = > 0 (sc)? sc : DEFAULT_CAPACITY; // The default size is 16 @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

During this initialization process, there is already an implementation of optimistic locking. You can see that the table initialization takes place in a CAS method and enters the while method when the table is null or has a length of 0.

If sizeCtl is less than 0, the thread will yield. Since the initial sizeCtl state is equal to 0, it indicates that a thread has entered the elseif section. Set the value of SC to -1, indicating that initialization is underway.

If sc is greater than 0, the value is sc. Otherwise, the default value is 16. Then calculate the resize required for the next number of elements. Summarize the initialization methods

  • If sizeCtl is less than 0, another array is being initialized, giving up execution
  • If sizeCtl is greater than 0, initialize an array with sizeCtl
  • Otherwise, initialize an array of the default size (16)
  • Then set sizeCtl to 3/4 of the array length

ConcurrentHashMap#transfer(Node<K, V>[],Node<K, V>)

The purpose of this method is to implement the array transfer, that is, the expansion logic of ConcurrentHashMap. That’s the resize method of the HashMap

In ConcurrentHashMap, expansion doubles the length of Node array as in HashMap, but nextTable is introduced in ConcurrentHashMap to ensure synchronization of multiple threads. The expansion process can be roughly divided into three steps:

  • Initializes an empty array, nextTable, twice the length of node, to be used as temporary storage for the expanded array.
  • Copy the original Node array to nextTable.
  • Assign nextTable to the original Node array and set nextTable to null. Modify sizeCtl.

ConcurrentHashMap copies the array by traversing it, depending on the type of Node in the array. – (1) Common Node type, representing nodes in the linked list, which are placed in I and N + I in the corresponding nextTable according to the subscript I. The order of the linked list is reversed. – (2) ForwardingNode type, representing nodes that have been processed – (3) TreeBin type, Represents a node of a red-black tree, copies the red-black tree, and considers whether it needs to be de-tree-ized. – (4) NULL: Indicates that there is no node and the node is added to ForwardingNode. ConcurrentHashMap#helpTransfer(Node<K,V>[], Node<K,V>) In addition, the traversal when ConcurrentHashMap copies the array is traversal from n to 0, and it is not traversal completely, but divided into several small people according to the number of threads, and each thread is responsible for copying the stride(stride, Transfer-1) bucket ([Transfer-stride, Transfer-1]) at a time. You can apply again when the task is completed. The stride is determined by the number of cpus, and the minimum is 16.

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; Stride if ((stride = (NCPU > 1)? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // if (nextTab == null) {// initiates the same state that initiates the same state. Try {@suppressWarnings ("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[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; ForwardingNode<K,V> FWD = new ForwardingNode<K,V>(nextTab); //advance indicates whether the object is successfully processed. If the object is successfully processed, continue to iterate. Otherwise, the object is processed again. // Loop whether to accept flag 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); 1.75 times the length of the original array, that is, 0.75 times of the expanded array return; } // Update sizeCtl with CAS method, where 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; Else if ((f = tabAt(TAB, tabAt)) i)) == null) advance = casTabAt(tab, i, null, fwd); Else if ((fh = f.hash) == MOVED) advance = true; Synchronized (f) {if (tabAt(TAB, I) == f) {Node<K,V> ln, hn; If (fh >= 0) {int runBit = fh&n; if (fh >= 0) {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); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } // Red-black tree nodes, the ln and HN linked lists composed of Treenodes are obtained by tail-insert method, corresponding to elements with subscripts I and N + I in nextTable respectively. 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; } } 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

I can only say a complicated batch. Capacity expansion is the most complex, multi-threaded data replication, and red-black tree conversion. Not enough brains. Explore, gods, and I will note the conclusion

Put method

Pure PUT method

/* * The putVal method is simply called, and putVal's third argument is set to false. */ public V put(K key, V value) {return putVal(key, value, false); }Copy the code

Look at putVal

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); Int hash = spread(key.hashcode ()); 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 (f = tabAt(TAB, I = (n-1) & hash)) == null) { If (casTabAt(TAB, I, null, // If there are no elements in this position, try adding them via cas, New Node<K,V>(hash, key, value, null))) // Create a Node to add to the array, null means the next Node is null break; // No lock when adding to empty bin} /* * No lock when adding to empty bin} // No lock when adding to empty bin} */ else if ((fh = f.hash) == MOVED) TAB = helpTransfer(TAB, f); Else {/* * if there are elements at this location, synchronized is used. * If there are elements at this location, synchronized is used. * If there are elements at this location (hash > 0), synchronized is used for all elements in the list. If it is not found, it is added to the end of the list. If it is a tree, it is added to the tree by calling putTreeVal. After the addition, the number of associations on the node is evaluated. */ V oldVal = null; Synchronized (f) {if (tabAt(TAB, I) == f) {if (fh >= 0) {synchronized (f) {if (tabAt(TAB, I) == f) { The hash value is -2 binCount = 1. for (Node<K,V> e = f;; ++binCount) {// Walk through the list; If (e.h ash = = hash && / / to the hash of the elements, the key to store the location of the nodes with the same time, replace the value of the node can be (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) { oldVal = e.val; if (! OnlyIfAbsent) // When using putIfAbsent, set e.void = value only if the key is not worth setting. break; } Node<K,V> pred = e; If ((e = e.ext) == null) {// If (e = e.ext) == null) {// If (e = e.ext) == null) {// If (e = e.ext) == null) { Next = new Node<K,V>(hash, key, // if null, set this Node to the next Node value, null); break; }}} else if (f instanceof TreeBin) {Node<K,V> p; binCount = 2; If ((p = ((TreeBin<K,V>)f).puttreeval (hash, key, putTreeVal))! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; } } } } if (binCount ! = 0) {if (binCount >= TREEIFY_THRESHOLD) // If (binCount >= TREEIFY_THRESHOLD); if (oldVal ! = null) return oldVal; break; } } } addCount(1L, binCount); // count return null; }Copy the code

So let’s summarize the put method

  • The first step, as soon as you go in, is to make sure that the key value is null and if it is null throw an exception
  • In the second step, when adding a pair of key-value pairs, it first determines whether the array holding these key-value pairs is initialized, and if not, it initializes the array.
  • The third step is to compute the hash value to determine which position to place in the array. If this position is empty, add it (CAS lock). If it is not empty, fetch the node
  • Step 4, if the hash value of the fetched node is MOVED(-1), it means that the array is being expanded, copied to a new array, and the current thread will help with the replication
  • Step 5: If the node is not empty or expanded, use synchronized to lock and add the node
  • The sixth step, if it is a linked list, traverses the whole list until the keys of the extracted nodes are compared with the keys to be placed. If the keys are equal and the hash value of the keys is equal, it indicates that they are the same key and the value is overwritten; otherwise, it is added to the end of the linked list
  • Seventh, if it is a tree, call putTreeVal to add the element to the tree
  • Finally, after the addition is complete, it determines how many nodes there are at the node. If there are more than eight nodes, it calls the treeifyBin method to try to convert the list to a tree or expand the number

The get method

The get operation of concurrentHashMap is simple and can be described in three steps:

  • Compute the hash value, locate the table index position, return if the first node matches.
  • If capacity expansion occurs, the find method of ForwardingNode, which marks the node being expanded, will be called to find the node and return if the node matches.
  • If none of the above is true, the node is traversed and returns if it matches, otherwise null is returned
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 size method

AddCount () = addCount() = addCount() = addCount() = addCount()

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

The Unsafe and CAS

In ConcurrentHashMap, U can be seen everywhere, and it makes extensive use of U.compareAndSwapXXX method, which uses a CAS algorithm to implement lock-free operation of changing values, which can greatly reduce the performance cost of the lock agent. The basic idea of this algorithm is to constantly compare the value of a variable in memory to whether the value of a variable you specify is equal, if so, accept the value you specify, otherwise reject your operation. Because the value in the current thread is not the latest value, your changes may overwrite the results of changes made by other threads. This is similar to the idea of optimistic locking and SVN.

The unsafe code block controls the modification of attributes, such as the most commonly used SIZECTL. In this version of concurrentHashMap, a large number of CAS methods are used to modify variables and attributes. Using CAS for lock-free operation can greatly improve performance.

private static final sun.misc.Unsafe U; private static final long SIZECTL; private static final long TRANSFERINDEX; private static final long BASECOUNT; private static final long CELLSBUSY; private static final long CELLVALUE; private static final long ABASE; private static final int ASHIFT; static { try { U = sun.misc.Unsafe.getUnsafe(); Class<? > k = ConcurrentHashMap.class; SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class<? > ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class<? > ak = Node[].class; ABASE = U.arrayBaseOffset(ak); int scale = U.arrayIndexScale(ak); if ((scale & (scale - 1)) ! = 0) throw new Error("data type scale not a power of two"); ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); }}Copy the code

ConcurrentHashMap defines three atomic operations that operate on nodes at a specified location. It is these atomic operations that make ConcurrentHashMap thread-safe.

// Static final <K,V> Node<K,V> tabAt(Node<K,V>[] TAB, int i) { return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); } // Use the CAS algorithm to set the Node at position I. Concurrency can be achieved because it specifies the original value of the node. // In the CAS algorithm, the value in memory is compared to the value you specify. If the value is equal, your changes will be accepted, otherwise your changes will be rejected. SVN 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); Static final <K,V> void setTabAt(Node<K,V>[] TAB, int I, Node<K,V> v) { U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); }Copy the code

conclusion

HashMap, Hashtable, ConccurentHashMap

  • HashMap thread is not safe, array + linked list + red-black tree
  • Hashtable is thread safe, locks the entire object, array + linked list
  • ConccurentHashMap thread safety, CAS+ synchronous lock, array + linked list + red-black tree
  • The key and value of a HashMap can be null.

Differences between JDK1.7 and JDK1.8

The main design improvements in JDK1.8 are as follows:

  1. Use node instead of segment to reduce lock granularity.
  2. Designed the MOVED state while thread 2 is still putting data in the process of resize, thread 2 will help resize.
  3. Instead of locking, three CAS operations are used to ensure atomicity of some node operations.
  4. SizeCtl uses different values to represent different meanings and controls.

Use synchronized instead of ReentrantLock

Release notes

  • The source code here is JDK8 version, different versions may vary, but the basic principle is the same.

I have a goal to write two or three articles a week. I hope I can keep it up for a year. I hope you can give me more suggestions so that I can learn more and make progress together.

Daily for praise

All right, everybody, that’s all for this article. All the people here are talented.

Creation is not easy, your support and recognition, is the biggest motivation for my creation, we will see in the next article

Six pulse excalibur | article “original” if there are any errors in this blog, please give criticisms, be obliged!