A HashMap is a k-V storage container that is used very frequently in the workplace. In a multithreaded environment, using HashMap is unsafe and can produce all kinds of unintended results.
For more information on HashMap thread safety, please refer to another article by me: An in-depth look at HashMap thread safety
In response to the problem that HashMap is unsafe in multi-threaded environments, the authors of HashMap argue that this is not a bug, but that thread-safe HashMap should be used.
There are several ways to get a thread-safe HashMap:
- Collections.synchronizedMap
- HashTable
- ConcurrentHashMap
The first two methods have serious performance problems due to global locking. So Doug Lea, the renowned concurrency programmer, added a bunch of concurrency tools under the java.util.concurrent package in JDK1.5. This includes ConcurrentHashMap, a thread-safe HashMap.
This article will briefly introduce the implementation principle of ConcurrentHashMap.
PS: based on JDK8
0 ConcurrentHashMap review in JDK7
ConcurrentHashMap is implemented differently in JDK7 than in JDK8. First let’s review how ConcurrentHashMap works in JDK7.
0.1 Section lock technology
To solve the problem that HashTable locks the entire hash table, ConcurrentHashMap proposes a piecewise lock solution.
The idea of segmental locking is that instead of locking the entire hash table, only part of it is locked.
How do you do that? This uses the most critical Segment of the ConcurrentHashMap.
ConcurrentHashMap maintains an array of segments, each of which can be considered a HashMap.
The Segment itself inherits the ReentrantLock, which is itself a lock.
Maintains an internal hash table in the Segment using a HashEntry array.
Each HashEntry represents a K-V in the map, and a HashEntry can be used to form a linked list structure that is referenced to the next element through the next field.
The above content is expressed in the source code as follows:
public class ConcurrentHashMap<K.V> extends AbstractMap<K.V>
implements ConcurrentMap<K.V>, Serializable {
/ /... Omit...
/** * The segments, each of which is a specialized hash table. */
final Segment<K,V>[] segments;
/ /... Omit...
/** * Segments are specialized versions of hash tables. This * subclasses from ReentrantLock opportunistically, just to * simplify some locking and avoid separate construction. */
static final class Segment<K.V> extends ReentrantLock implements Serializable {
/ /... Omit...
/** * The per-segment table. Elements are accessed via * entryAt/setEntryAt providing volatile semantics. */
transient volatile HashEntry<K,V>[] table;
/ /... Omit...
}
/ /... Omit...
/** * ConcurrentHashMap list entry. Note that this is never exported * out as a user-visible Map.Entry. */
static final class HashEntry<K.V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
/ /... Omit...}}Copy the codeSo, the overall structure of the ConcurrentHashMap in JDK7 can be described as follows.
As you can see from the graph above, as long as our hash values are scattered enough, we will put them into different segments every time we put them. When a segment is put, the current segment will lock itself and no other thread will be able to operate on the segment. This is the benefit of lock segmentation.
0.2 Thread-safe PUT
ConcurrentHashMap put ();
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
// Locate a segment based on the hash of the key. If the segment specified by index is not initialized, call ensureSegment to initialize it
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
// Call the segment put method
return s.put(key, hash, value, false);
}
Copy the codeFinally, the segment put method is called to put the elements into the HashEntry array. The comments here give only lock-related instructions
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// Because segment itself is a lock
TryLock is called here to try to get the lock
// If the segment succeeds, no other thread can modify it
// If it fails, the scanAndLockForPut method is called to try to find the node based on the key and hash. If it doesn't exist, a node is created and returns, or null is returned if it does
// On a multi-core CPU, tryLock() will be tried 64 times. If it is not found 64 times, lock() will be called directly.
// This step must obtain the lock
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if(e ! =null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if(! onlyIfAbsent) { e.value = value; ++modCount; }break;
}
e = e.next;
}
else {
if(node ! =null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
/ / capacity
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break; }}}finally {
/ / releases the lock
unlock();
}
return oldValue;
}
Copy the code0.3 Thread-safe expansion (Rehash)
Most of the thread safety problems of HashMap are in the process of rehash.
The expansion of ConcurrentHashMap only expands the HashEntry array in each segment.
The ConcurrentHashMap is locked when rehashing the segment, so no other thread can operate on the segment’s hash table during rehashing.
1 Initialization of ConcurrentHashMap in JDK8
Using the no-argument constructor as an example, let’s see what happens when the ConcurrentHashMap class is initialized.
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
Copy the codeStatic code blocks are executed and class variables initialized. The following class variables are initialized:
// Unsafe mechanics
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 newError(e); }}Copy the codeThe Unsafe class is used here, where the objectFieldOffset method is used to get the memory offset of a specified Field(such as sizeCtl).
What is this offset used for? Don’t worry, in the following analysis, it is good to meet the time to study.
PS: For an introduction to and use of Unsafe, check out my other article on the Unsafe class
2 Internal data structure
Let’s take a look at how the storage structure is defined in JDK8 from a source code perspective.
/** * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by Iterators. * * Hash table, initialized at first put data, its size is always a multiple of 2. * /
transient volatile Node<K,V>[] table;
/** * used to store a key-value pair ** key-value entry. This class is never exported out as a * user-mutable map. entry (i.e., one supporting setValue; see * MapEntry below), but can be used for read-only traversals used * in bulk tasks. Subclasses of Node with a negative hash field * are special, and contain null keys and values (but are never * exported). Otherwise, keys and vals are never null. */
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 codeThe implementation of JDK8 is quite different from that of JDK7. In JDK8, the concept of Segment is not used. It is more like the implementation of HashMap.
PS: For the principle of HashMap, you can refer to another article of the author, HashMap principle and internal storage structure
This structure can be illustrated in the following figure
3 Thread-safe hash table initialization
ConcurrentHashMap uses the table member variable to hold the hash table.
Table initialization adopts the delayed initialization policy. The table is initialized at the first put execution.
The put method source code is as follows (temporarily irrelevant code is omitted) :
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// Computes the hash value of the key
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// If table is empty, initialize it
if (tab == null || (n = tab.length) == 0)
tab = initTable();
/ / to omit...
}
/ / to omit...
}
Copy the codeThe source code for initTable is as follows
/** * Initializes table, using the size recorded in sizeCtl. */
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
/ / # 1
while ((tab = table) == null || tab.length == 0) {
// sizeCtl defaults to 0, so the first thread to go there will enter the else if below
/ / # 2
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// Attempt to atomically update the int value of the specified object (this) with its memory offset SIZECTL from sc to -1
SizeCtl: -1
/ / # 3
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// Double check for reasons discussed below
/ / # 4
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0)? sc : DEFAULT_CAPACITY;// The default initial capacity is 16
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n];/ / # 5
table = tab = nt; // Create a hash table and assign the value to the member variable table
sc = n - (n >>> 2); }}finally {
/ / # 6
sizeCtl = sc;
}
break; }}return tab;
}
Copy the codeOne of the sizeCtl member variables in ConcurrentHashMap is equivalent to threshold in HashMap. When the number of elements in the hash table exceeds sizeCtl, expansion is triggered. For example, a value of -1 indicates that a thread is initializing the hash table. A value less than -1 indicates that a thread is resizing the hash table.
This method first determines whether sizeCtl is less than 0. If it is less than 0, the current thread is made ready.
When sizeCtl is greater than or equal to 0, the current thread will try to change sizeCtl to -1 through CAS. SizeCtl <0. The thread that fails to modify goes to the next loop. The thread that successfully modified continues to execute the initialization code below.
Before new Node[], check again if the table is empty. The reason for this double check is that if another thread suspends after executing code #1, another thread that initialized the table has finished executing code #6, and sizeCtl is set to a value greater than 0, then when the thread cuts back to the table, It is possible to repeat initialization. This is illustrated in the concurrency scenario below.
The hash table is initialized, the sizeCtl values are recalculated, and the initialized hash table is returned.
The following figure details several concurrent scenarios that can lead to reinitializing the hash table, assuming that Thread2 eventually successfully initializes the hash table.
- Thread1 simulates a concurrent CAS update sizeCtl variable scenario
- Thread2 simulates the need for double-checking tables
It is possible for Thread1 to go to the new Node[] step without concurrency control for sizeCtl updates. In Thread3, Thread3 will also go to the new Node[] step without double judgment.
4 Thread-safe PUT
Put operations can be classified into the following two types
- If there is no element in the index corresponding to the current key in the hash table
- If the index of the current hash table corresponds to the current key already has an element (hash collision)
4.1 No Element in the Hash Table
The corresponding source code is as follows
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
}
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);
}
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 codeThe tabAt method retrieves the index elements of an array using unsafe.getobjectVolatile (), which is volatile for the memory offset.
If the array is empty, try creating a new Node using cas on the specified index.
4.2 Hash Collision
The corresponding source code is as follows
else {
V oldVal = null;
// Lock f is obtained in 4.1 using the tabAt method
// That is, when a hash collision occurs, the head of the list is used as the lock
synchronized (f) {
// The reason for this check is:
// TAB refers to the member variable table. After table is rehash, the Node on index may change
// To ensure that there is no rehash during the put process, specify that the Node on index is still f
// If it is not f, then the lock is meaningless
if (tabAt(tab, i) == f) {
// Ensure that PUT does not occur during capacity expansion. If fh is -1, capacity expansion is under way
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) {
// Appends elements to the end of the list
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}else 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; }}}}if(binCount ! =0) {
// If the list is longer than 8, convert the list to a red-black tree, the same as HashMap, which optimizes lookups compared to JDK7
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break; }}Copy the codeDifferent from the concept of segment in JDK7, JDK8 uses the head of the list as a lock. In JDK7, a HashMap may form a ring-linked list in the case of concurrent put. ConcurrentHashMap uses this lock to ensure that only one thread performs a put on the list at the same time, thus solving the concurrency problem.
5 Thread safe capacity expansion
The last step of the PUT method is to count the number of elements in the hash table. If the number exceeds the sizeCtl value, expansion is triggered.
The code for expansion is slightly longer, so you can take a look at the Chinese annotations and refer to the following analysis. Our main goal is to figure out how ConcurrentHashMap solves the concurrency problem of HashMap. Just look at the source code with this question in mind. For problems with HashMaps, refer to another article I wrote at the beginning of this article.
In fact, the concurrency problem of HashMap is mostly caused by put and expansion concurrency.
Here’s how ConcurrentHashMap works.
The code involved in capacity expansion is as follows:
/** * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by Iterators. * Hash table used in services */
transient volatile Node<K,V>[] table;
/** * The next table to use; Non-null only while resizing. * Hash table to be used during expansion and assigned to table after expansion and reset nextTable to NULL. * /
private transient volatile Node<K,V>[] nextTable;
/** * Adds to count, and if table is too small and not already * resizing, initiates transfer. If already resizing, helps * perform transfer if work is available. Rechecks occupancy * after a transfer to see if another resize is already needed * because resizings are lagging additions. * *@param x the count to add
* @param check if <0, don't check resize, if <= 1 only check if uncontended
*/
private final void addCount(long x, int check) {
// ----- Calculate the number of key-value pairs start -----
CounterCell[] as; long b, s;
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();
}
// ----- Count the number of key-value pairs end -----
// ----- Determine whether expansion is required start -----
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// When the number of key/value pairs calculated above exceeds sizeCtl, the expansion is triggered and the core method transfer is called
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 expansion operations are already in progress, nextTable is the new hash table being expanded
// In case of concurrent expansion, transfer directly uses the new hash table being expanded to ensure that no hash table overwriting occurs
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// Set the sizeCtl value to a negative value
// If there is no concurrent expansion, a new hash table will be created in transfer to expand the capacity
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); s = sumCount(); }}// ----- Determine whether to expand end -----
}
/** * Moves and/or copies the nodes in each bin to new table. See * above for explanation. */
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
// Initializes a new hash table twice the previous size and assigns a value to the member variable nextTable
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;
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;
// When expansion is complete, set the member variable nextTable to NULL and replace table with nextTable after rehash
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 {
// The next step is to iterate through each list, rehash each list element
// We still use the header as the lock, so we can't put the list during expansion
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
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);
}
// the setTabAt method calls unsafe. putObjectVolatile to replace hash elements, with volatile memory semantics
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
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;
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 codeBased on the above code, a brief explanation of how ConcurrentHashMap resolves the HashMap concurrency problem is provided.
- First, create a new hash table (nextTable) that is twice the size of the previous one. All subsequent rehashes operate on the new hash table, not the original hash table.
- Each linked list in the original Hash table (table) is then rehash, at which point an attempt is made to obtain the lock on the head node. This step ensures that the list cannot be put during the rehash process.
- SizeCtl control prevents multiple new hash tables from being created during capacity expansion.
- Finally, after all key-value pairs are rehash into the new table (nextTable), the table is replaced with nextTable. This avoids the problem of getting to NULL when HashMap gets and expansion are concurrent.
- In the whole process, shared variables are stored and read by volatile or CAS to ensure thread safety.
6 summarizes
In a multithreaded environment, you must be careful with shared variables. Think fully in terms of the Java memory model.
The ConcurrentHashMap makes extensive use of the Unsafe class method. Although we can get an instance of Unsafe ourselves, it is not recommended to do so in production. In most cases, this can be done with the tools provided in the package, such as those under the Atomic package for CAS operations and under the Lock package for lock-related operations.
Use thread-safe container tools such as ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedQueue, etc. These concurrency tools are important because, like ConcurrentHashMap, the Unsafe getObjectVolatile and setObjectVolatile atomically update elements in arrays.
