From the school to A factory all the way sunshine vicissitudes of life

Please visit www.codercc.com[1]


1. Introduction of ConcurrentHashmap

Since HashMap is not thread-safe, we can usually use the old HashTable class in Java architecture, Basically, all methods of this class use synchronized for thread-safe control. It can be imagined that in the case of high concurrency, only one thread can acquire the object monitor lock at a time, which is really not satisfactory concurrency performance. Another way to wrap a Hashmap as a thread-safe Map is through the Collections Map

synchronizedMap(Map

m). SynchronzedMap put ();
,v>
,v>

public V put(K key, V value) {
    synchronized (mutex) {return m.put(key, value);}
}
Copy the code

The SynchronizedMap implementation still uses synchronized exclusive locks for thread-safe concurrency control. Similarly, the performance of this scheme is not satisfactory. Doug Lea has gone out of his way to create some thread-safe concurrent containers that will make every Java developer happy. In contrast to hashMap, ConcurrentHashMap is a thread-safe map that uses the idea of lock segmentation to improve concurrency.

ConcurrentHashMap is available online in JDK1.6 for those interested. JDK 1.6 key elements:

  1. Segments inherit the lock function of ReentrantLock, providing thread-safety for each segment.
  2. The segment maintains a hash table of buckets, each of which is a linked list of hashentries.

In JDK 1.8, ConcurrentHashMap has changed a lot. The amount of code alone has increased considerably. Version 1.8 discarded segments and made extensive use of synchronized and CAS lock-free operations to ensure thread-safe ConcurrentHashMap operations. Why Synchronzied instead of ReentrantLock? Synchronzied does a number of optimizations, including biased, lightweight, and heavyweight locks, which can be upgraded up, but not down (see this article [2] for synchronized). The performance of synchronized is equal to or even better than ReentrantLock in some cases. For specific performance tests, check online. In addition, the underlying data structure is changed to the data form of array + linked list + red-black tree.

2. Key attributes and classes

Before we look at the implementation of ConcurrentHashMap, we need to take a systematic look at a few key points.

Key attributes of ConcurrentHashMap

  1. [] table volatile Node

    [] table:// Load an array of nodes as a data container for ConcurrentHashMap. The size of an array is always a power of two.
    ,v>

  2. nextTable volatile Node

    [] nextTable; // The value is null during capacity expansion and non-null only during capacity expansion
    ,v>

  3. sizeCtl volatile int sizeCtl; This attribute is used to control the size of the table array. There are several situations according to whether the table array is initialized or being expanded: ** When the value is negative: ** If the value is -1, the table array is being initialized; if the value is -n, the table array is being expanded by n-1 threads. SizeCtl specifies the size of the array to be created during table initialization. If it has been initialized, it indicates that the available capacity of the current data container (table array) can also be regarded as the critical value (if the number of inserted nodes exceeds the critical value, the capacity needs to be expanded). Specifically, it refers to the length of the array N times the loading factor loadFactor. When the value is 0, the array length is the default initial value.

  4. Sun.misc.Unsafe U In the ConcurrentHashMapde implementation, numerous U.compareAndSwapXXXX methods are used to modify properties of ConcurrentHashMap. These methods actually use the CAS algorithm to ensure thread-safety, which is an optimistic strategy, assuming that every operation will not cause a conflict, and try it if and only if a conflict occurs. The CAS operation relies on the modern processor instruction set and is implemented through the underlying CMPXCHG instruction. The core idea of CAS(V,O,N) is as follows: If the actual value V of the current variable is the same as the expected old value O, it indicates that the variable has not been modified by other threads, so the new value N can be safely assigned to the variable. If the current value V is different from the expected value O, it indicates that the variable has been processed by another thread. In this case, it is unsafe to assign the new value N to the variable operation and retry. The use of CAS in numerous implementations of synchronized components and concurrent containers is made possible by the Sun.misc. Unsafe class, which provides low-level operations that directly manipulate memory and threads, known as “Pointers” in Java. The member variable is retrieved in a static code block:

    static { try { U = sun.misc.Unsafe.getUnsafe(); . } catch (Exception e) { throw new Error(e); }}Copy the code

Key inner classes in ConcurrentHashMap

  1. The Node class implements the Map.Entry interface, mainly stores key-value pairs, and has the next field

    static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; . }Copy the code

You can also see that many of the attributes are volatile to ensure memory visibility.

  1. TreeNode TreeNode, inherited from the Node class that holds data. The red-black tree operation is for the TreeBin class, and the class’s comments indicate that the TreeBin encapsulates the TreeNode again

    ** * Nodes for use in TreeBins */ 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; . }Copy the code

  2. The TreeBin class is not responsible for wrapping the user’s key and value information, but for wrapping many TreeNode nodes. The actual ConcurrentHashMap “array” stores TreeBin objects, not TreeNode objects.

    	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;
	        // values for lockState
	        static final int WRITER = 1; // set while holding write lock
	        static final int WAITER = 2; // set when waiting for write lock
	        static final int READER = 4; // increment value for setting read lock
			......
	}
Copy the code

  3. ForwardingNode A special node that is available only during capacity expansion. Its key,value, and hash values are all null. And has a nextTable pointer to reference the new TABLE array.

    static final class ForwardingNode<K,V> extends Node<K,V> { final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; }... }Copy the code

Key CAS Operations

We mentioned above that CAS is heavily used in ConcurrentHashMap to modify its properties and operations. Therefore, before we understand the ConcurrentHashMap method, we need to understand the following common thread-safe operations using the CAS algorithm.

  1. tabAt

    	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);
	}
Copy the code

    This method is used to get the Node element in the table array whose index is I.

  2. casTabAt

    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

    Set the element in the table array with index I using the CAS operation

  3. setTabAt

    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

    This method is used to set the element in the table array whose index is I

3. Explain key methods

With this core information in mind, let’s take a look at how several common methods are implemented in turn.

3.1 Instance constructor method

The first thing you do when using ConcurrentHashMap is create a new ConcurrentHashMap object, which provides the following constructor methods:

ConcurrentHashMap(); ConcurrentHashMap(); ConcurrentHashMap(); ConcurrentHashMap(int initialCapacity) // 3. Given a map ConcurrentHashMap(map <? extends K, ? Extends V> m) // 4. ConcurrentHashMap(int initialCapacity, float loadFactor) // 5. ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)Copy the code

ConcurrentHashMap provides 5 constructor methods for using ConcurrentHashMap. For example, the ConcurrentHashMap provides 5 constructor methods for using ConcurrentHashMap.

public ConcurrentHashMap(int initialCapacity) { //1. If (initialCapacity < 0) throw new IllegalArgumentException(); Int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); SizeCtl this. SizeCtl = cap; }Copy the code

If the specified value is greater than the maximum value allowed, the maximum value is taken. Otherwise, the specified value is processed further. Finally, cap is assigned to sizeCtl, as described above. When the constructor method is called, sizeCtl should represent the size of ConcurrentHashMap, the size of the table array. What did tableSizeFor do? The source code for:

/** * Returns a power of two table size for the given desired capacity. * See Hackers Delight, SEC 3.2 */ private static Final int tableSizeFor(int c) {int n = c-1; SEC 3.2 */ private static final int tableSizeFor(int c) {int n = c-1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }Copy the code

As is clear from the comments, this method converts the size specified when the constructor method is called to a power of 2. That is, the ConcurrentHashMap must be a power of 2. For example, when the size is specified as 18, to satisfy the power of 2 property, In fact, concurrentHashMapd has a size of 2 ^ 5 (32). Note also that the constructor method does not construct the table array (the ConcurrentHashMap data container), but evaluates the length of the table array. The first insertion into the ConcurrentHashMap actually completes the initialization of the table array.

3.2 initTable method

Direct source code:

private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) // 1. Ensure that only one Thread is initializing thread.yield (); // lost initialization race; just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if ((tab = table) == null || tab.length == 0) { // 2. Int n = (sc > 0)? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") // 3. Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n]; table = tab = nt; // 4. Calculate the size available in the array: actual size n*0.75 (load factor) sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }Copy the code

The logic of the code is described in the comment. There may be a case where multiple threads go to this method at the same time. In order to ensure proper initialization, the first step is to check if. At this point, other threads call Thread.yield() to yield the CPU slice If the value is true. The initializing thread calls the U.compareAndSwapInt method to change sizeCtl to -1, the initializing state. Another thing to note is that in step 4 the available size of the array is further calculated as the actual size of the array n times the load factor 0.75. 0.75 is three quarters, and n-(n >>> 2) is exactly n-(1/4)n=(3/4)n. If the constructor is selected with no arguments, the default size for the new Node array is DEFAULT_CAPACITY (16), multiplied by the loading factor 0.75 to get 12, which means the available size of the array is 12.

3.3 put method

The most commonly used ConcurrentHashMap methods are put and get. Let’s look at how the PUT method is implemented. PutVal (); putVal (); putVal (); putVal ();

/** 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 ()); //1. int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; / / 2. If the current table has not been initialized to call initTable method will first TAB to initialize the if (TAB = = null | | (n = TAB. Length) = = 0) TAB = initTable (); //3. The element in TAB where index = I is null, 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 } //4. Else if ((fh = f.hash) == MOVED) TAB = helpTransfer(TAB, f); else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) == f) { //5. 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; If (f instanceof TreeBin) {Node<K,V> p; 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; }}}} // 7. If (binCount! = 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! = null) return oldVal; break; }}} //8. Check the current capacity. If the capacity exceeds the threshold (actual size x loading factor), you need to expand the capacity. return null; }Copy the code

The put method is a bit long, so let’s follow the decomposition steps above. Overall, ConcurrentHashMap uses synchronzied and CAS approaches to address thread-safety issues. ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap

ConcurrentHashMap Hash bucket array structure diagram

As shown, ConcurrentHashMap is a hash bucket array, and each element is evenly distributed in the hash bucket array if no hash conflicts occur. When hash conflicts occur, it is the standard way to solve the chain address. Nodes with the same hash value are formed into a linked list, which is called “zipper method”. In addition, in version 1.8, in order to prevent the zipper from being too long, the linked list will be converted into a red-black tree when the length of the list is greater than 8. Each element in the table array is actually the head of a singly linked list or the root of a red-black tree. When inserting a key-value pair, you should first locate the bucket to be inserted at index I of the table array. So, how do I compute index I? Based on the hashCode of the key, of course.

  1. Spread () is rehashed to reduce Hash collisions

We know that for a hash table, if the hash values are not evenly distributed, the probability of hash conflicts will greatly increase, which will affect the performance of the hash table. Therefore, a rehash is performed through the spread method to greatly reduce the possibility of hash conflicts. The spread method is:

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
Copy the code

In this method, xOR operation is performed by placing the lower 16 bits of the hashCode of the key at the higher 16 bits. In this way, hash values can be dispersed and the probability of hash conflicts can be uniformly reduced. In addition, xOR operation is used only to achieve a balanced trade-off in terms of performance cost.

2. Initialize the table

Then step 2 checks whether the current table array is initialized and calls initTable to initialize it, as described above.

3. Can you directly insert the new value into the table array

As can be seen from the above structure diagram, there is a case where the insert value can be directly inserted if the position of the table array to be inserted is NULL. How do I hash index I into the table? You can obviously determine where to insert the new value into the array by modulating the hash value against the length of the array. ConcurrentHashMap is always a power of 2, (n-1) & hash is equivalent to modulo n of length n, that is, hash%n, but bitwise is much more efficient than modulo. Doug Lea has also done an admirable job of optimizing the performance of concurrent containers.

Once you’ve determined the index I of the array, you can use the tabAt() method to get the element at that position, or if the Node f is currently null, you can use the casTabAt method to insert the new value.

4. Check whether the capacity is being expanded

If the current node is not null and the node is a forwardingNode, a capacity expansion operation is being performed on concurrentHashMap. The following describes the capacity expansion operation as a specific method. How do you determine if the current Node is a special Node? MOVED (fh = f. Hash) == MOVED (fh = f. Hash)

static final int MOVED     = -1; // hash for forwarding nodes
Copy the code

5. Insert a new value into the linked list when table[I] is the first node

If table[I] is not null and forwardingNode, and the hash value of current Node f is greater than 0 (fh >= 0), the current Node F is the head of the list of all nodes of the current bucket. So the next thing you want to do is insert new values into the ConcurrentHashMap is insert new values into this list. Lock through synchronized (F) to achieve thread safety. The code for inserting a node into a linked list is as follows:

if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; / / find the hash value of the same key, covering the old value 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); if ((e = e.ext) == null) {// Next = new Node<K,V>(hash, key, value); break; }}}Copy the code

This code is easy to understand, there are two cases: 1. In the linked list, if the node is found with the same key as the key pair to be inserted, it can directly overwrite; 2. 2. If the end of the list is not found, append the key/value pair to the end of the list

6. When table[I] is the root node of a red-black tree, insert a new value into the red-black tree

According to the previous design scheme of array + linked list, there is a problem here. Even if the load factor and Hash algorithm are designed reasonably, it is inevitable that the zipper is too long. Once the zipper is too long, even in extreme cases, the time complexity of searching a node will be O(n). The performance of ConcurrentHashMap is severely affected. Therefore, in JDK1.8, the data structure is further optimized and red-black tree is introduced. When the length of the linked list is too long (more than 8 by default), the linked list is converted to a red-black tree, and the performance of ConcurrentHashMap is improved by making use of the characteristics of red-black tree’s rapid addition, deletion, modification and query, in which the insertion, deletion and search algorithms of red-black tree are used. Table [I] is a tree node of a red-black tree.

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; }}Copy the code

If (f instanceof TreeBin) {if (f instanceof TreeBin) {if (f instanceof TreeBin) { Operations on red-black trees are performed against the TreeBin, not the TreeNode. Insert a new node into a red-black tree by calling putTreeVal. The same logic overwrites the old node if it exists in a red-black tree with the same hash value and equals true. Otherwise, new nodes are appended to the red-black tree.

7. Adjust the number of nodes based on the current number

After the data is inserted, the size of the current linked list will be further adjusted as follows:

if (binCount ! = 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! = null) return oldVal; break; }Copy the code

It is easy to understand that the treeifyBin method is called to convert the Tabel [I] zipper to a red-black treeif the current list node number is greater than or equal to 8 (TREEIFY_THRESHOLD).

Now that the logic of the Put method is pretty much there, let’s wrap things up:

Overall process:

  1. First, for each value put into the table, the spread method is used to hash the key’s hashcode to determine the position of the value in the table.
  2. If the current table array is not initialized, initialize the table array first.
  3. If the position is null, it is placed directly using the CAS operation;
  4. If there is a node at this location, it indicates that a hash collision has occurred, and the type of the node is determined first. If fh==MOVED(forwardingNode, array is being expanded), the node is being expanded.
  5. If it is a linked list node (fH >0), the resulting node is the head of the list of nodes with the same hash value. You need to iterate backwards to determine where this new value is added. If a node with the same key is encountered, only the value of the node needs to be overridden. Otherwise, iterate backwards until the end of the list is inserted into the node;
  6. If the node type is TreeBin, insert the new node directly by calling the red-black tree insert method.
  7. After inserting the node, check the length of the list again. If the length is greater than 8, convert the list to a red-black tree.
  8. Check the current capacity. If the capacity exceeds the threshold (actual size x load factor), the capacity needs to be expanded.

3.4 the get method

It’s easy to look at the get method after you look at the put method, just think about it the other way around, and if I put it this way, I’ll just take it the other way around. Get method source code:

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // 1. Hash int h = spread(key.hashcode ()); if ((tab = table) ! = null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) ! = null) {/ / 2. The table [I] barrels of key nodes and looking for the same key, is returned directly if (eh = e.h (ash) = = h) {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) ! = null) {/ / 4. From the chain table lookup, it returns the node to find the value, otherwise it returns null can be an if (e.h ash = = h && (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) return e.val; } } return null; }Copy the code

Table [I] is the current hash bucket array node. If table[I] is the current hash bucket array node, it will return directly. If not, continue to see if the current tree node? Check whether the hash value of the node is less than 0. If it is less than 0, the node is a tree node. If it’s a tree node look for a node in a red-black tree; If it is not a tree node, then there is only one possibility left in the form of a linked list, traversing backwards to find the node, returning the value of the node if found, or null if not found.

3.5 transfer method

When the capacity of ConcurrentHashMap is insufficient, expand the table. The basic idea of this method is similar to HashMap, but it is much more complicated because it supports concurrent scaling. The reason is that it supports multiple threads for expansion operations, and does not lock. I would like to do this not just to satisfy concurrent requirements, but to take advantage of concurrent processing to reduce the time impact of capacity expansion. Transfer method source code:

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 //1. If (nextTab == null) {// Initiating 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); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node<K,V> f; int fh; I 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; }} / / 4. The original copy of the elements in an array into the new array / / 4.5 for loop exits, expansion end modified sizeCtl attribute the 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}} ForwardingNode 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) { Node<K,V> ln, hn; Int runBit = fh &n; 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 a linked list setTabAt(nextTab, I, ln) in I of nextTable; // Insert another linked list setTabAt(nextTab, I +n, hn) at I +n of nextTable; // Insert forwardNode into table I to indicate that forwardNode has been processed setTabAt(TAB, I, FWD); // Set advance to true and return to the above while loop to execute I -- 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; } } 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

Please refer to the comments for the code logic. The expansion operation is divided into two parts:

The first part is to build a nextTable, which is twice as big. This is done single-threaded. Node

[] nt = (Node

[])new Node
[n << 1], based on the original capacity size to the right.
,v>
,v>

The second part copies elements from the original table to nextTable, essentially iterating through the copying process. According to the operation, the position I of the current traversal array is obtained, and then the tabAt method is used to obtain the elements at the position of I for judgment:

  1. If this position is empty, the forwardNode node is placed in the I position of the original table, which is also the key to trigger concurrent expansion.
  2. If the location is Node (fH >=0) and if it is the head of a linked list, construct an antilist and place them at I and I +n in nextTable
  3. If it is a TreeBin node (fH <0), do a reverse process and determine whether untreefi is required. Place the process at I and I +n in nextTable respectively
  4. After all nodes have been replicated, make nextTable the new table and update sizeCtl to 0.75 times the new size. Set to 0.75 times the new capacity code tosizeCtl = (n << 1) - (n >>> 1)N <<1 is the same thing as n moving one bit to the left means that n is twice as big as 2n,n>>>1, N to the right is equal to n divided by 2, which is 0.5n, and then the two subtract to 2N minus 0.5n= 1.5N, which is exactly equal to 0.75 times the new capacity, which is 2n*0.75= 1.5N. Finally, I conclude with a schematic diagram (picture taken from the Internet) :
ConcurrentHashMap Expansion diagram

3.6 Some methods related to size

For ConcurrentHashMap, the exact amount of stuff in the table is an indeterminate amount, because it’s impossible to call size() and cause other threads to stop counting like GC’s “stop the world.” So we can only say that this quantity is an estimate. ConcurrentHashMap also worked out this estimate with great effort.

To count elements, ConcurrentHashMap defines variables and an inner class

/** * A padded cell for distributing counts. Adapted from LongAdder * and Striped64. See their internal docs for explanation. */ @sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; }}
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /


/ * *


     
    

      
  • It actually holds the number of elements in the hashMap updated using the CAS lock but it does not return the number of elements in the current HashMap
    • 

     


/ private transient volatile long baseCount; / *


     
    

      
  • Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
*/
private transient volatile int cellsBusy;
    • 

     


/ * *

Copy the code

  • Table of counter cells. When non-null, size is a power of 2. */ private transient volatile CounterCell[] counterCells;

MappingCount and size methods

MappingCount is similar to size. From the comments given, mappingCount should be used instead of size. Neither method returns basecount directly but instead counts the value once, which is actually an approximate value, Therefore, it is possible that another thread is performing an insert or delete operation at the time of the count.

public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } /** * Returns the number of mappings. This method should be used * instead of {@link #size} because a ConcurrentHashMap may * contain more mappings than can be represented as an int. The * value returned is an estimate; the actual count may differ if * there are concurrent insertions or removals. * * @return the number of mappings * @since 1.8 */ public long mappingCount() {long n = sumCount(); return (n < 0L) ? 0L : n; // ignore transient negative values } 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

AddCount method

The addCount method is called at the end of the put method, and the number of elements in the current ConcurrentHashMap +1. This method does two things: updates the baseCount value and checks for expansion.

private final void addCount(long x, int check) { CounterCell[] as; long b, s; // Update baseCount if ((as = counterCells)! = null || ! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { 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))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); If (check >= 0) {Node<K,V>[] TAB, nt; // 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); } nextTable=null else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); }}}Copy the code

4. To summarize

ConcurrentHashmap in JDK6 and 7 mainly uses segments to reduce the lock granularity and divide them into several segments. Put locks the Segment, get does not lock the Segment, and volatile ensures visibility. When a global count is required (such as size), the first attempt is to calculate modCount several times to determine if any other threads made changes during those attempts, and if not, size is returned. If yes, lock all segments in sequence to calculate.

1.8 Before PUT, locate a node in a segment and then locate a bucket in the segment. In 1.8, the design of segment bloat was abandoned and each bucket in the Node[] tale array was directly targeted, further reducing the lock granularity. And to prevent the performance decline caused by too long zipper, when the length of the list is greater than 8, the design of red black tree is used.

The main design changes 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.
  5. Use synchronized instead of ReentrantLock

See this article [3] for more information on the 1.7 versus 1.8 implementation of ConcurrentHashMap.

Refer to the article

Version 1.8 ConcurrentHashMap

  1. http://www.importnew.com/22007.html[4]
  2. http://www.jianshu.com/p/c0642afe03e0[5]

HashMap version 1.8

http://www.importnew.com/20386.html[6]

The resources

[1]

www.codercc.com: https://www.codercc.com


[2]

Look at this article: https://juejin.cn/post/6844903600334831629


[3]

In this article: http://www.jianshu.com/p/e694f1e868ec


[4]

http://www.importnew.com/22007.html: http://www.importnew.com/22007.html


[5]

http://www.jianshu.com/p/c0642afe03e0: http://www.jianshu.com/p/c0642afe03e0


[6]

http://www.importnew.com/20386.html: http://www.importnew.com/20386.html