Abstract
When it comes to Java multithreaded development, using HashMap can cause deadlock issues, and using HashTable is inefficient. ConcurrentHashMap can maintain synchronization and improve concurrency efficiency, so ConcurrentHashMap is our best choice.
Why use ConcurrentHashMap
-
Using the PUT method of a HashMap in a multithreaded environment can cause the program to loop because multithreading can cause the HashMap to form a looped linked list, i.e. the next node of one of the nodes in the list is never null, resulting in an infinite loop. At this point, CPU utilization is close to 100%, so you cannot use HashMap in concurrent cases.
-
Hashtables are thread-safe through the use of synchronized, but are inefficient in the context of hotly contested threads. Because when one thread accesses the synchronous method of the HashTable, other threads can only block and wait for the occupying thread to finish.
-
ConcurrentHashMap uses the idea of segmented locking. Different locks are used for different data segments to allow multiple threads to access different data segments at the same time. In this way, there is no lock contention between threads, thus improving concurrency efficiency.
Introduction to the
There is a description of ConcurrentHashMap when reading the source code.
The primary design goal of this hash table is to maintain concurrent readability(typically method get(), but also iterators and related methods) while minimizing update contention. Secondary goals are to keep space consumption about the same or better than java.util.HashMap, and to support high initial insertion rates on an empty table by many threads.
The main purpose of ConcurrentHashMap is to maintain concurrent readability (usually the use of get() methods, but also iterators and related methods) while minimizing update entrainments (that is, preserving access to other data segments during insertions or expansions). The second goal is to be consistent with or better than HashMap in terms of space utilization and to support the initial insertion rate of multiple threads into empty tables.
ConcurrentHashMap in Java7 and Java8:
In ConcurrentHashMap, lock segmentation is used to achieve the above goals.
In Java7, ConcurrentHashMap consists of a Segment array structure and a HashEntry array. A Segment is a reentrant lock. It is an array and a linked list structure. A Segment contains a HashEntry array, and each HashEntry is a linked list structure. It is through Segment Segment locking that ConcurrentHashMap achieves efficient concurrency.
In Java8, ConcurrentHashMap removes the data structure of Segment Segment lock, mainly ensures data acquisition based on CAS operation and locks corresponding data segments with synchronized keyword, which further improves concurrency. In order to improve the addressing performance under hash collisions, Java 8 converts linked lists (O(N)) to red-black trees (O(long(N)) when the list length exceeds a certain threshold (8).
The structure of ConcurrentHashMap in Java8
In Java8, ConcurrentHashMap deprecates the Segment class, but retains the Segment attribute for serialization. Currently, ConcurrentHashMap uses the Node class as the basic storage unit, and each key-value pair is stored in a Node. Node also has some subclasses. TreeNodes are used in tree structures (if the list length is greater than 8, it becomes a red-black tree). TreeBins are used to maintain TreeNodes. Used to encapsulate TreeNode when the linked list is converted to a tree. That is, ConcurrentHashMap’s red-black tree stores the TreeBin, not the treeNode; ForwordingNodes is an important structure used for ConcurrentHashMap expansion. It is a flag node with an attribute pointing to nextTable and provides lookup methods.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; final K key; volatile V val; // Volatile Node<K,V> next; // Volatile Node(int) is usedhash, K key, V val) {
this.hash = hash;
this.key = key;
this.val = val;
}
Node(int hash, K key, V val, Node<K,V> next) {
this(hash, key, 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() {... } public final VsetValue(V value) {... } public final boolean equals(Object o) {... } /** * Virtualized supportfor map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {...}
}
Copy the codeIn addition to processing Node, ForwardingNodes, a subclass of Node, is also an important structure. ForwardingNodes, also known as ConcurrentHashMap, acts as a token and plays a key role in handling concurrency. ForwardingNodes, also known as ConcurrentHashMap, has a segmentation feature to improve concurrency efficiency.
/**
* A node inserted at head of bins during transfer operations.
*/
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
//hashThe default value is MOVED(-1) super(MOVED, null, null); this.nextTable = tab; } Node<K,V> find(int h, Object K) {// loop to avoid deep recursion on forwarding nodes // Find in nextTable, NextTable can be considered currenthashOuter:for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (;;) {
int eh; K ek;
if((eh = e.hash) == h && ((ek = e.key) == k || (ek ! = null && k.equals(ek))))return e;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
if ((e = e.next) == null)
returnnull; }}}}Copy the codeAtomic operation in ConcurrentHashMap
Find, replace, and set elements through atomic operations in ConcurrentHashMap. These atomic operations play a critical role, and you can see them in all the basic functions of ConcurrentHashMap.
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
}
Copy the codeConcurrentHashMap function implementation
1. ConcurrentHashMap initialization
Before we introduce initialization, we will introduce one important parameter, sizeCtl, with the following implications:
/**
* Table initialization and resizing control. When negative,the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon whichTo resize the table. * Control flags for initializing and resizing the Hash table. If the value is negative, the Hash table is being initialized or expanded. * (-1 indicates that the table is being initialized, and -n indicates that n-1 threads are expanding.) * Otherwise, when the table is null, the initialization size used when the table was created is saved, or the default is 0. * Saves the size of the next resize after initialization. */ private transient volatile int sizeCtl;Copy the codeThis parameter acts as a control flag and is used for ConcurrentHashMap initialization and expansion. The ConcurrentHashMap constructor simply sets some parameters and does not initialize the Hash table. The Hash table is initialized only when the element is inserted from. SizeCtl < 0 indicates that there is a thread initializing, and the current thread will abandon initialization. Otherwise, set SIZECTL to -1 and initialize the Hash table. After successful initialization, set the sizeCtl value to the current capacity value.
/**
* 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) {/ / sizeCtl less than zero, is initializedif((sc = sizeCtl) < 0) // Call yield() to yield CPU resources thread.yield (); // lost initialization race; Just spin // Set SIZECTL to -1, indicating initializationelse if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n]; table = tab = nt; sc = n - (n >>> 2); //n-(1/4)n, i.e. Default capacity (n * loadFactor)}} finally {sizeCtl = sc; // reset sizeCtl}break; }}return tab;
}
Copy the code2. Determine the index of the element in the Hash table
The hash algorithm is used to split elements into hash buckets. Determine the array index in ConcurrentHashMap using the following method:
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
Copy the codeStep 2 :(length-1) &(h ^ (h >>> 16)) &hash_bits);
ConcurrentHashMap put method
-
If key or value is null, a null pointer exception is thrown.
-
If the table is null or the length of the table is 0, the table is initialized and the initTable() method is called.
-
Computes the index position of the current key value, and if the current node in the Hash table is null, inserts the element directly. (Note that the CAS operation is used here.)
-
If the hash value of the node element is -1, the ForwaringNodes node is in expansion mode. Then the current thread joins the expansion.
-
The current node is not null, the current node is locked, the element is inserted into the current node. In Java8, nodes are converted to a tree structure when their length is greater than 8.
/** Implementation forPut and putIfAbsent */ final V putVal(K key, V value, Boolean onlyIfAbsent) {// The data is invalid. An exception is thrownif(key == null || value == null) throw new NullPointerException(); // The first step in calculating the index, passing in the key valuehashValue of the inthash= spread(key.hashCode()); int binCount = 0; // Save the length of the current nodefor (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if(tab == null || (n = tab.length) == 0) tab = initTable(); // Initialize the Hash tableelse if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// Insert elements into the Hash table using CAS operationsif (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // No lock when adding to empty bin}else if((fh = f.hash) == MOVED) // F.hash == -1 // The current thread is adding TAB =helpTransfer(tab, f);
else if (onlyIfAbsent && fh == hash&& // check first node ((fk = f.key) == key || fk ! = null && key.equals(fk)) && (fv = f.val) ! = null)return fv;
else{ V oldVal = null; // synchronized (f) {if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for(Node<K,V> e = f;; ++binCount) { K ek; // Insert the key value of the elementhashValue of an element in a nodehashReplaces the current element value with the same valueif (e.hash == hash&& ((ek = e.key) == key || (ek ! = null && key.equals(ek)))) { oldVal = e.val;if(! OnlyIfAbsent) // Replace the current element's value e.var = value;break; } Node<K,V> pred = e; // Insert directly into the node without the same valueif ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break; }}} // Nodes are treeselse 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) // replace the old value p.val = value; }}else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update"); }}if(binCount ! = 0) {// If the node length is greater than 8, convert to treeif (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! = null)return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the codeConcurrentHashMap Capacity expansion mechanism
When the number of elements in ConcurrentHashMap reaches cap * loadFactor, expansion is required. Capacity expansion is performed by Transfer(). If a thread is performing put operations and capacity expansion is in progress, helpTransfer() can be used to help capacity expansion. That is, ConcurrentHashMap supports multithreading, with multiple threads processing different nodes.
-
To start capacity expansion, calculate the step size, which is the number of nodes allocated to each thread for capacity expansion (the default is 16). Stride = (NCPU > 1)? (n >>> 3)/NCPU: n), the minimum value is 16.
-
Next, initialize the temporary Hash table nextTable. If nextTable is null, initialize the length of nextTable twice as long as the original one.
-
Start traversing the Hash table by calculating the step size, where the coordinates are recorded by an atomic operation (compareAndSetInt). Through a while loop, the node is skipped if it is within the step of a thread. Otherwise, go to the next step.
-
If the current node is empty, set the node to a ForwardingNodes node in the old Hash table to indicate that the node has been processed.
-
If the hash value of the current node element is MOVED(f.hash == -1), this is a ForwardingNodes node, and the node is skipped. Otherwise, start reprocessing the node;
-
In this step, the operation of recalculating the position of the element is the same as in HashMap, that is, the hash and length of the current element key value are performed. If the result is 0, the position remains unchanged, and the position of 1 is I +n. The element to be processed is the last one to qualify, so it might be in reverse order after expansion, but that order doesn’t matter much in the Hash table.
-
Finally, in the case of the linked list structure, the high-order and low-order new linked list nodes are directly obtained; in the case of the tree structure, the high-order and low-order nodes are also calculated. However, it is necessary to judge whether the nodes need to be converted to the tree structure according to the length of the nodes.
/**
* Moves and/or copies the nodes in each bin to new table. See
* above forexplanation. */ private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; // Calculate the step size based on the length and number of cpus. The minimum step size is 16if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked") // Initializes a new Hash table twice as long as the original one. 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; // Initialize the ForwardingNodes node ForwardingNode<K,V> FWD = new ForwardingNode<K,V>(nextTab); boolean advance =true; // Whether to override the node's tag Boolean finishing =false; // to ensure sweep before committing nextTab
for(int i = 0, bound = 0;;) { Node<K,V> f; int fh; // Determine whether to cross nodes based on the step sizewhile(advance) { int nextIndex, nextBound; // Reach the index of the unprocessed nodeif (--i >= bound || finishing)
advance = false;
else if((nextIndex = transferIndex) <= 0) {// All nodes have received processing I = -1; advance =false;
}
else if(U.compareAndSetInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {// Set transferIndex to transferIndex and omit bound = nextBound; i = nextIndex - 1; advance =false; }} // All nodes have been received or processedif(i < 0 || i >= n || i + n >= nextn) { int sc; // The processing is completeif(finishing) { nextTable = null; table = nextTab; SizeCtl sizeCtl = (n << 1) - (n >>> 1);return; } // Determine whether all nodes are processedif (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if((sc - 2) ! = resizeStamp(n) << RESIZE_STAMP_SHIFT)return;
finishing = advance = true; i = n; // recheck before commit}} // If the node is null, it is marked as receivedelse if((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd); / / key valueshashA value of -1 indicates that this is a ForwardingNodes node and has been processedelse if ((fh = f.hash) == MOVED)
advance = true; // already processed
else{// lock the current node synchronized (f) {if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if(fh >= 0) {// Index position change flag int runBit = fh & n; Node<K,V> lastRun = f; // The last elementfor(Node<K,V> p = f.next; p ! = null; p = p.next) { int b = p.hash & n; // Recalculate updates to the last elementif(b ! = runBit) { runBit = b; lastRun = p; }} //runBit = 0, keep position unchangedif(runBit == 0) { ln = lastRun; hn = null; } //runBit = 1, I +nelse{ hn = lastRun; ln = null; } // Iterate over the node elementfor(Node<K,V> p = f; p ! = lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; // Build a new low (position invariant) listif((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln); // Build a new list with high order (I +n)elsehn = new Node<K,V>(ph, pk, pv, hn); } // Set the new list to the corresponding position in the new Hash tablesetTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn); // Set the node at the corresponding position in the original Hash table to the ForwardingNodes nodesetTabAt(tab, i, fwd);
advance = true; } // If the node is a tree structureelse 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); // Compute the new index position in the same wayif((h & n) == 0) {// Build a new list structureif ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else{// Build a new list structureif ((p.prev = hiTail) == null)
hi = p;
elsehiTail.next = p; hiTail = p; ++hc; }} // Determine whether to convert to tree 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; // Set the new list to the corresponding position in the new Hash tablesetTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn); // Set the node at the corresponding position in the original Hash table to the ForwardingNodes nodesetTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Copy the codeConcurrentHashMap get method
The get method of ConcurrentHashMap reads data from the Hash table and does not conflict with expansion. This method has no synchronization lock.
-
The index position is calculated using the hash of the key value. If the condition is met, the corresponding value is directly returned.
-
If the hash value of the node is less than 0, the node is being expanded. Call the find method of ForwardingNodes to search for the node.
-
Otherwise, iterate over the current node until the corresponding element is found.
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException ifthe specified key is null */ public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); // Return the corresponding value if the condition is metif((tab = table) ! = null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) ! = null) {if ((eh = e.hash) == h) {
if((ek = e.key) == key || (ek ! = null && key.equals(ek)))returne.val; } //e.hash<0, expanding capacityelse if (eh < 0)
return(p = e.find(h, key)) ! = null ? p.val : null; // Iterate over the current nodewhile((e = e.next) ! = null) {if(e.hash == h && ((ek = e.key) == key || (ek ! = null && key.equals(ek))))returne.val; }}return null;
}
Copy the codeconclusion
ConcurrentHashMap (ConcurrentHashMap, ConcurrentHashMap, ConcurrentHashMap, ConcurrentHashMap, ConcurrentHashMap)