Surprise concurrent programming JUC series demo code address: github.com/mtcarpenter…
In this section, let’s take a look at how this container can be thread-safe and efficient at the same time. ConcurrentHashMap is a thread-safe and efficient HashMap.
Why use ConcurrentHashMap
Using HashMap in concurrent programming can cause the program to loop forever. Using thread-safe Hashtables is very inefficient, and for these two reasons ConcurrentHashMap comes into play.
Thread unsafe HashMap
In a multithreaded environment, putting with HashMap causes an infinite loop that leads to CPU utilization approaching 100%, so you cannot use HashMap in concurrent situations. For example, executing the following code causes an infinite loop.
public class HashMapExample {
// Total requests
public static int clientTotal = 5000;
// The number of concurrent threads
public static int threadTotal = 200;
private static Map<Integer, Integer> map = new HashMap<>(2);
public static void main(String[] args) throws Exception {
ExecutorService executorService = Executors.newFixedThreadPool(threadTotal);
final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
for (int i = 0; i < clientTotal; i++) {
final int count = i;
executorService.execute(() -> {
try {
update(count);
} catch (Exception e) {
e.printStackTrace();
}
countDownLatch.countDown();
});
}
countDownLatch.await();
executorService.shutdown();
System.out.println("size:"+ map.size());
}
private static void update(int i) { map.put(i, i); }}Copy the codeThe concurrent execution of PUT operations on HashMap will cause an infinite loop, because multithreading will cause the Entry linked list of HashMap to form a ring data structure. Once the ring data structure is formed, the next node of the Entry will never be empty, and an infinite loop will occur to obtain the Entry.
Inefficient HashTable
The HashTable container uses synchronized to ensure thread-safety, but HashTable is very inefficient in the context of competitive threads. Because when one thread accesses the synchronization method of HashTable, other threads also access the synchronization method of HashTable, and enter the blocking or polling state. For example, thread 1 uses PUT to add elements, thread 2 cannot use either put method to add elements or GET method to obtain elements. Therefore, the more fierce the competition, the lower the efficiency.
ConcurrentHashMap’s lock fragmentation technique improves concurrent access rates
HashTable containers in the fierce competition in the concurrent environment show the cause of the inefficient competition is all access to the HashTable thread must be the same lock, if the container have much lock, every lock part used to lock the container data, then when multithreaded access container different data section of the data, the existed between threads lock contention, This is the lock fragmentation technique used by ConcurrentHashMap to improve concurrent access efficiency. Data is first stored in segments, and then each segment is assigned a lock. When a thread uses the lock to access one segment of data, other segments of data can also be accessed by other threads.
ConcurrentHashMapExample sample
public class ConcurrentHashMapExample {
// Total requests
public static int clientTotal = 5000;
// The number of concurrent threads
public static int threadTotal = 200;
private static Map<Integer, Integer> map = new ConcurrentHashMap<>();
public static void main(String[] args) throws Exception {
ExecutorService executorService = Executors.newFixedThreadPool(threadTotal);
final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
for (int i = 0; i < clientTotal; i++) {
final int count = i;
executorService.execute(() -> {
try {
update(count);
} catch (Exception e) {
e.printStackTrace();
}
countDownLatch.countDown();
});
}
countDownLatch.await();
executorService.shutdown();
System.out.println("size:" + map.size());
}
private static void update(int i) { map.put(i, i); }}Copy the codeConcurrentHashMap JDK 1.7 / JDK 1.8
- JDK 1.7 uses ReentrantLock + Segment + HashEntry, which is equivalent to dividing a HashMap into segments and assigning one lock to each Segment, to support multithreaded access. Lock granularity: Based on Segment and contains multiple Hashentries.
- JDK 1.8 uses CAS + synchronized + Node + red-black tree. Lock granularity: Node (the first Node) (implementing Map.Entry). Lock granularity has been reduced.
JDK 1.7 structure
JDK 1.7In theConcurrentHashMapInternallySegmentSection,SegmentinheritedReentrantLockCan be interpreted as a lock, eachSegmentThey are locked independently of each other and do not affect each other. Compared to the previous oneHashtableEach operation requires the entire object to be locked, greatly improving concurrency efficiency. Because its locks are independent of each other, rather than having only one lock for the entire object. The underlying data structure of each SegmentHashMapSimilarly, there is still a zipper structure of arrays and linked lists. The default value is 0 to 15Segment, so up to 16 concurrent operations can be supported at the same time (operations are distributed in differentSegmentOn). 16 The default value can be set to another value during initialization, but cannot be expanded once the initialization is confirmed.
JDK 1.8 structure
- The first is the simplest, with an empty position indicating that there are no elements to fill yet.
- The second is the sum
HashMapIn a very similar zipper structure, the first node is filled first in each slot, but if the same Hash value is calculated later, it is extended in the form of a linked list. - The third structure is the red-black tree structure, which is in Java 7
ConcurrentHashMapAnd we probably haven’t had much exposure to data structures like this before
If the list length is greater than a certain threshold (8 by default), the capacity can be converted from a linked list to a red-black tree. The red-black tree is each node binary search trees with a color attribute, color is red or black, red and black tree of binary search trees is the nature of a balance of BST strategy, we can understand as a balanced binary search trees, look for high efficiency, automatically balance, to prevent the extreme imbalance which influence the efficiency of the lookup happens, Every node in a red-black tree is either red or black, but the root node is always black.
ConcurrentHashMap source
Constants that
/** * table Indicates the maximum number of buckets, and the first two digits are used as control flags */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/** * table Number of buckets Initialize the default value, which must be a power of 2 */
private static final int DEFAULT_CAPACITY = 16;
/** * The possible maximum value of an array, which needs to be associated with the toArray () method */
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * concurrency level, left over, compatible with previous versions */
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/** * the load factor, the expansion threshold, can be defined in the constructor */
private static final float LOAD_FACTOR = 0.75 f;
/** * lists to red black tree threshold, over 8 lists to red black tree */
static final int TREEIFY_THRESHOLD = 8;
/** * Tree list threshold, < or equal to 6 (tranfer, lc, hc=0 two counters ++ record the number of original bin, new binTreeNode, <=UNTREEIFY_THRESHOLD untreeify(LO)) */
static final int UNTREEIFY_THRESHOLD = 6;
/** * tree threshold 2, the list tree can only be tree when the array bucket tree exceeds 64 */
static final int MIN_TREEIFY_CAPACITY = 64;
Copy the codeInitialize the table
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// Initialization successfully exits the loop
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // There is another thread initializing, spin waiting
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// Enter initialization sizeCtl = -1
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0)? sc : DEFAULT_CAPACITY; Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt;// sc = n-n/4 ???
sc = n - (n >>> 2); }}finally {
// sizeCtl was successfully initialized
sizeCtl = sc;
}
break; }}return tab;
}
Copy the codeThe get method
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// Check if table exists, hashCode index is null
if((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)))
return e.val;
}
// Walk through the Node tree to find
else if (eh < 0)
return(p = e.find(h, key)) ! =null ? p.val : null;
// Walk through nodes in a linked list
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
Copy the codeTo summarize the get process:
- Calculates the Hash value and finds the corresponding slot.
- If the array is empty or the location is NULL, then null is returned.
- If the node at that position is exactly what we want, return the value of that node directly;
- If the node is a red-black tree or is being expanded, use find to continue the search.
- Otherwise it’s a linked list, so we’re going to do a list lookup
Put Method Description
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
// Calculate the hashCode of the key
int hash = spread(key.hashCode());
int binCount = 0;
// Loop until insertion succeeds,
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
// Initialize the table
tab = initTable();
// tabAt calls getObjectVolatile
// The current position is empty and can be inserted directly
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// Insert through CAS without locking
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break;
}
// The following is the case where the position already has a value
// MOVED Indicates that the Map is being expanded
else if ((fh = f.hash) == MOVED)
// Help to expand, then enter the next loop to try to insert
tab = helpTransfer(tab, f);
// The capacity is not expanded
else {
V oldVal = null;
// Lock f, which is the head Node of the Node stored at the current location
synchronized (f) {
// Double check that the Node head has not changed
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// Perform operations on the linked list
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
// Update the value (judge onlyIfAbsent) or insert the end of the list...
break; }}else if (f instanceof TreeBin) {
// Operate on the tree...}}}// Determine whether treeify is needed
if(binCount ! =0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the codeTo summarize the put process:
- Check whether the Node[] array is initialized or not
- Hash the index coordinates of the array to determine whether there is a Node Node. If there is no Node, use CAS to add (the head Node of the list). If adding fails, the next loop will be entered.
- Check that the internal capacity is being expanded, and help it expand.
- If f! = null, synchronized locks the f element (head element of a list/binary tree)
- If it is a Node (linked list), add the list
- If it is a TreeNode, the tree add operation is performed.
- The length of the linked list has reached the critical value 8. Of course, 8 is the default value, and you can adjust it. When the number of nodes exceeds this value, you need to convert the list to a tree structure.
TryPresize method
private final void tryPresize(int size) {
// Calculate the target size for expansion
int c = (size >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>>1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// The TAB is not initialized
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
// CAS set sizeCtl=-1 before initialization
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = nt;// SC = 0.75N, which is the capacity expansion threshold
sc = n - (n >>> 2); }}finally {
// There is no CAS assignment at this point, because other threads that want to perform initialization, finding sizeCtl=-1, return directly, ensuring that only one thread will perform initialization in any case.sizeCtl = sc; }}}// If the target capacity expansion size is smaller than the capacity expansion threshold or the capacity exceeds the maximum limit, no capacity expansion is required
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
/ / capacity
else if (tab == table) {
int rs = resizeStamp(n);
// If sc<0, another thread is expanding capacity
if (sc < 0) {
Node<K,V>[] nt;
/** 1 (sc >>> RESIZE_STAMP_SHIFT) ! 2 SC == RS + 1 and SC == RS + MAX_RESIZERS: 3 (nt = nextTable) == NULL: nextTable is initializing. 4 transferIndex <= 0: All hash buckets are allocated */
// If you do not need to expand the capacity, return directly
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
/ / CAS set sizeCtl = sizeCtl + 1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// Help it expand
transfer(tab, nt);
}
// set sizeCtl to :(resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2)
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); }}}Copy the codeThis code reference site: www.jianshu.com/p/487d00afe…
Transfer method
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// Calculate the number of hash buckets to migrate (MIN_TRANSFER_STRIDE this value is used as the lower limit to avoid too many expansion threads)
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
// Double the size
@SuppressWarnings("unchecked")
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
//1 Migrate the obtained Hash buckets in reverse order. If the migration is complete, update the transferIndex to obtain the next batch of Hash buckets to be migrated
//2 If transferIndex=0, all hash buckets are allocated. Set I to -1 to exit the transfer method
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// Update the hash bucket index to be migrated
while (advance) {
int nextIndex, nextBound;
// Update migration index I.
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
//transferIndex<=0 indicates that no hash bucket needs to be migrated, sets I to -1, and the thread is ready to exit
i = -1;
advance = false;
}
// After migrating bound buckets, try updating transferIndex to get the next batch of Hash buckets to migrate
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false; }}/ / from the transfer
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// The last thread to migrate, recheck, do the finishing touches, and exit
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
/** sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2) before transfer SizeCtl = sizeCtl+1 will be set to sizeCtl = sizeCtl+1 for each thread exiting the Transfer method before exit, so when the last thread exits: There must be sc == (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2), i.e. (SC-2) == resizeStamp(n) << RESIZE_STAMP_SHIFT */
// Not equal, indicating that not the last thread, directly exit the transfer method
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
// The last thread to exit should check again to see if all migration is complete
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
// Migrate nodes
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// List migration
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;
}
// Divide the node list into two new node lists
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);
}
// Assign the new node list to nextTab
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
// Red-black tree migration
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 codeWelcome to pay attention to the public number Shanma carpenter, I am Xiao Chun brother, engaged in Java back-end development, will be a little front-end, through the continuous output of a series of technical articles to literary friends, if this article can help you, welcome everyone to pay attention to, like, share support, we see you next period!