A preface.
Take JDK1.8 ConcurrentHashMap as an example to analyze how to ensure thread-safety for concurrent scenarios and what concurrency design can be inspired by this.
Ii. Core Ideas
2.1 Design should solve problems
Because ConcurrentHashMap is a basic container in the JDK, it is designed with the following points in mind:
- Structure simplification.
- High performance.
- Thread safety.
Simplified structure: 1.7 uses segment locking to control concurrency granularity, which makes concurrentHashMap a more complex structure. Many other operations need to be compatible with this complex structure.
High performance: Minimizes get congestion and speeds up PUT and capacity expansion.
Thread security: Ensures the thread security of GET, PUT, and capacity expansion in the case of high concurrency.
2.2 Core ideas of design
- Node[] is still used to store elements of ConcurrentHashMap, becoming the same as hashMap.
- Using volatile ensures that the values obtained are up to date, reducing synchronization blocking.
- Increase concurrency by reducing lock granularity, and ideally all thread PUT operations are parallel.
- When table[I] has no value, perform the CAS operation on table[I] to ensure the first security.
- When table[I] has a value, whether the linked list or red-black tree, the table[I] is locked, directly lock the head node, to ensure thread safety.
3. Thread safety when initializing nodes
3.1 Initialization Time
The Node[] array is uninitialized when ConcurrentHashMap is initialized, and initTable is not initialized until the first put call.
final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; / / judgment Node array is empty if (TAB = = null | | (n = TAB. Length) = = 0) / / initializes the Node array TAB = initTable (); . }Copy the code3.2 Concurrency Security during initialization
What if multiple threads simultaneously call initTable to initialize the Node array?
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// Each loop gets the latest Node array reference
while ((tab = table) == null || tab.length == 0) {
//sizeCtl is a flag bit. If it is -1, it is less than 0, indicating that a thread is doing initialization
if ((sc = sizeCtl) < 0)
// Allocate CPU time slices
Thread.yield();
//CAS operation to set the sizeCtl variable of this instance to -1
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// If the CAS operation succeeds, this thread will take care of the initialization
try {
// Check if the array is empty again
if ((tab = table) == null || tab.length == 0) {
// When initializing the Map, sizeCtl represents the array size, 16 by default
// By default, n is 16
int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
/ / the Node array
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n];// Assign it to the table variable
table = tab = nt;
// By bit operation, n minus n binary is shifted 2 bits to the right, equivalent to multiplying by 0.75
// For example, 16 equals 12, which is the same as multiplying by 0.75, but faster
sc = n - (n >>> 2); }}finally {
// directly assign the calculated sc (12) to sizeCtl, indicating expansion when the size reaches 12
// Since there is only one thread executing, the assignment can be done directly, there is no thread-safety problem
// Just ensure visibility
sizeCtl = sc;
}
break; }}return tab;
}
Copy the code- SizeCtl = -1. If sizeCtl < 0, the other threads will yield to release CPU resources, thus reducing the CPU increase caused by the lock loop.
- Yield does not eliminate CPU problems, however, because threads will have to compete again after the release, possibly until the CPU is still high.
- The table variable and sizeCtl both use volatile to ensure visibility;
- The CAS operation ensures that the sizeCtl flag bits are set atomically and that only one thread can be set successfully
TreeNode becomes TreeBin
In 1.8 hashMap, red-black trees are made up of relationships between TreeNode nodes, while concurrentHashMap wraps a tree with a treeBin object. The structure of the tree preserved in treeBin.
Why do they do that?
Because thread-safe concurrentHashMap locks the head node in a linked list, it cannot lock the root node in a red-black tree because the root node can change. It is better to lock the whole tree.
The thread safety of the PUT node
The following operations are not very different from hashMap. Let’s look at the code directly
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// Hash key hashCode
int hash = spread(key.hashCode());
int binCount = 0;
// An infinite loop until the put operation completes and exits the loop
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// Initialize when the Node array is empty
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// Unaddressed is the volatile method for retrieving the Node object corresponding to the underlying values of the Node array after the hashCode hash
// If the Node object is empty, it indicates that no thread has inserted the Node
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// Insert data in CAS mode
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
// Insert successfully, exit the loop
break; // no lock when adding to empty bin
}
// Check whether the system is expanding
else if ((fh = f.hash) == MOVED)
// Help expand capacity
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// Lock the Node object
synchronized (f) {
// Double check that the Node object is the same as the original one
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// Loop indefinitely until put is done
for (Node<K,V> e = f;; ++binCount) {
K ek;
// Like HashMap, compare hash first, then equals
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) {
// If there is no conflict with the list head Node, initialize it as the next of the previous Node
// Create a linked list
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}}Copy the codeAt its core is the tabAt(TAB, I) method, which uses the Unsafe class volatile operation to look for values volatile, ensuring that the value is the latest every time it is retrieved.
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 codeNote: Even though volatile is used for the table variable above, it only ensures that its reference is visible, not that the objects in its array are the latest. Therefore, the volatile class is needed to retrieve the latest Node.
Vi. Capacity expansion thread security
6.1 Expansion Opportunity
Since it reduces the granularity of locks, n threads can be put simultaneously if Hash is perfect and does not conflict. N is the size of the Node array. Under the default size of 16, a maximum of 16 threads can be put simultaneously without contention and it is thread safe. When hash conflicts are serious, the Node linked list becomes longer and longer, leading to serious lock contention. In this case, capacity expansion is performed.
If the Node[] array has Node values and a thread is processing busy = true, the Node[] array is rehash to try to find the latest location. If the latest location is still locked, Node[] is not discrete enough (serious conflicts) and needs to be expanded.
Capacity expansion restriction: The capacity expansion will not be unlimited. If the original array is found to be changed by other threads during capacity expansion, the capacity will not be expanded.
6.2 Expansion Mode
-
Each Node supports only one thread for capacity expansion. Multiple nodes support multi-threading. Which thread controls which Node is randomly determined, and how much control is determined by step size.
-
When capacity expansion occurs, the Node being transferred is set to FWD. If a thread wants to put the Node to this position, it cannot be put directly (it is not safe to put the Node directly, but it can be put to other nodes that have not been added).
-
A thread that fails to put does not wait, but helps the expansion thread complete the transition (if a thread completes the transition, the node that is responsible for the transition also checks to see if it needs help), recalculates the index after the expansion, and then puts it. If the thread finds that all nodes are handled by threads, finish = true, that is, no help is needed.
-
In the process of capacity expansion, it also supports get to check data. If there are threads to put data, it will also help to expand capacity together. This non-blocking algorithm maximizes the design of parallelism.
6.3 Expanding the thread Independent scope
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// A thread is responsible for the number of migrations in the Node array, based on the number of CPU cores in the machine
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
// The amount of migration allocated to this thread
// Assume 16 (default also 16)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// If nextTab is empty, the thread is the first to migrate
// Initializes the new Node array after migration
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
// Where n is the length of the old array, a shift to the left is equivalent to multiplying by 2
For example, the original array length is 16, and the new array length is 32
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;
}
// Set nextTable to a new array
nextTable = nextTab;
// Suppose it is 16
transferIndex = n;
}
// Assume 32
int nextn = nextTab.length;
// identifies the Node object, whose hash variable is -1
// If you encounter this Node during get or PUT, you will know that the Node is being migrated
// Pass in the nextTab object
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;
// I is the subscript of the Node array currently being processed. Each Node is decayed by 1
if (--i >= bound || finishing)
advance = false;
/ / assume nextIndex = 16
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// Based on the above assumptions, nextBound is 0
// And set nextIndex to 0
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
//bound=0
bound = nextBound;
//i=16-1=15
i = nextIndex - 1;
advance = false; }}if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
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}}// Select the Node whose subscript is 15 from the array I =15
// Directly set the placeholder flag to indicate that the Node has been processed
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// Check whether the Node's hash is MOVED. MOVED is a constant -1, which is the hash of the placeholder Node
// If it is a placeholder Node, prove that the Node has been processed, skip I =15 and continue the loop
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// Lock the Node
synchronized (f) {
// Verify that Node is the original Node
if (tabAt(tab, i) == f) {
//ln is lowNode, hn is highNode, hn is highNode
// These two concepts are illustrated in the following diagram
Node<K,V> ln, hn;
if (fh >= 0) {
// Fh and the length of the original Node array
// If the high X bit is 0, runBit=0
// If the high X bit is 1, runBit=1
int runBit = fh & n;
Node<K,V> lastRun = f;
for(Node<K,V> p = f.next; p ! =null; p = p.next) {
// These nodes are all nodes in the same list of nodes
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// As mentioned above, runBit=0, indicating that this Node is a low-level Node
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
//Node is a high-order Node
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 hash and n and are 0, prove to be low level Node
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
// There are two linked lists of high and status nodes
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// Set the low Node to the new Node array with the original subscript
setTabAt(nextTab, i, ln);
// Set the high-order Node to the new Node array, subscript the original Node location plus the length of the original Node array
setTabAt(nextTab, i + n, hn);
// Set this Node as a placeholder Node to indicate that the processing is complete
setTabAt(tab, i, fwd);
// Continue the loop
advance = true; }... } } } } }Copy the codeThe essence of this is to separate the scope of each thread from Node, preventing a Node from being processed concurrently by multiple threads.
This is done by performing a CAS to transIndex, which calculates bound, nextIndex, nextBound, and so on from each thread’s value to transIndex.
6.4 Design of high and low linked list
As you can see from the code above, this migration is divided into ln (low Node) and HN (high Node). Why do they do that?
We know that when we put a value, we first compute the hash value and then hash it to the specified Node index:
// Hash according to the key hashCode
int hash = spread(key.hashCode());
// Use the (n-1) & hash to locate the subscript value in the Node array, where n is the length of the Node array, let's say 16
(f = tabAt(tab, i = (n - 1) & hash);
Copy the codeThe following is an example of capacity expansion:
If I have a key that comes in, and its hash is equal to 9, what is its underlying value?
-
(16-1) and 9 -> 0000 1111 and 0000 1001 return 0000 1001 = 9
Suppose the Node array needs to be expanded to 32, what would be the subscript value?
-
And 9 -> 0001 1111 and 0000 1001 return 9
And suppose a key comes in, and the hash after the hash changes to 20, what happens?
- (16-1) and 20 perform and operations -> 0000 1111 and 0001 0100 result 0000 0100 = 4
- (32-1) and 20 perform and operations -> 0001 1111 and 0001 0100 result 0001 0100 = 20
If the hash bit at high X is 1 (X is the highest bit of binary -1 of array length), the index value in the Node array needs to be changed during expansion. Otherwise, the hash will fail and the data will be lost. Therefore, nodes with high X bit 1 are classified as HN and nodes with high X bit 0 are classified as ln during migration.
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);
}
Copy the codeThis operation forms the high and low bits into two linked list structures, as shown below:
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
Copy the codeThe lower-order list is placed at the original subscript, while the higher-order list needs to add the length of the original Node array. In this way, the higher-order Node array can still be hashed into the array with the corresponding subscript using the hash algorithm.
Finally, the corresponding subscript Node object in the original Node array is set as FWD marked Node, indicating that the Node migration is completed. Here, the migration of one Node is completed and the next Node will be migrated.
6.5 Get Operations during Capacity Expansion
Suppose a Node with subscript 16 is migrating, and a thread calls get and hashes the key to the Node with subscript 16.
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
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;
}
// If the hash value of Node is less than 0
// It can be FWD node
else if (eh < 0)
// Call the find method of the node object to find the value
return(p = e.find(h, key)) ! =null ? p.val : null;
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
Copy the codeCheck whether the hash in Node is less than 0, remember our placeholder Node, the hash is MOVED, the constant value is -1, so check whether the thread is migrating the Node. Let’s look at the find method:
// Inside the ForwardingNode class
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
// The search here is to find the new Node array
// The following lookup process is the same as a HashMap lookup
outer: 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)
return null; }}}Copy the codeThe GET method does not modify the data, so a scale-up migration should support a non-blocking GET operation in which placeholder nodes need to hold references to the new Node array.
6.6 Multi-Threading for Capacity Expansion
6.6.1 Assisting Expansion Opportunity
- If a Node is found to be a placeholder Node (FWD) during the PUT value, the Node will assist in capacity expansion.
- After a node is added, if the linked list length is greater than 8 and the array length is smaller than 64, the node will be expanded.
- After each new node, the addCount method is called to check whether the container element has reached the threshold.
6.6.2 Assisting in Expansion
During the put operation, suppose a thread comes in and wants to put the value to the migrated Node.
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// If a placeholder Node is found, the HashMap is being migrated
else if ((fh = f.hash) == MOVED)
// Perform assisted migrationtab = helpTransfer(tab, f); . }Copy the codefinal Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if(tab ! =null && (f instanceofForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! =null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
//sizeCtl = 1 to allow one more thread to assist in capacity expansion
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
/ / capacity
transfer(tab, nextTab);
break; }}return nextTab;
}
return table;
}
Copy the codeIn this case, the sizeCtl variable is used to indicate that HashMap is expanding. When the HashMap is ready to expand, it will set sizeCtl to a negative value (for example, when the array length is 16), its binary representation is:
1000 0000 0001 1011 0000 0000 0000 0010
Copy the codeThe unsigned bit is 1, indicating a negative number. One high 16 bits represent the array length algorithm identification, low 16 says there are several threads are doing migration, beginning to 2, take up from 1, thread migration for minus 1 operation, after the meeting, that is, if the low 16 to 2, on behalf of a thread is migration, if for 3, on behalf of the two threads are migration and so on.
As long as the array length is long enough, it can accommodate enough threads at the same time to expand together, maximizing parallel tasks and improving performance.
Thread-safe container size statistics
The key value mentioned above is the size of the container, which directly controls the hash and expansion operations, and addCount is added every time a node is added. How can we ensure the safety of multiple threads with this size?
7.1 count barrels
/ Count and check whether the length reaches the thresholdprivate final void addCount(long x, int check) {
/ / count
CounterCell[] as; long b, s;
// If counterCells is not null, it is initialized and goes directly to the if block
// If the competition is not serious, counterCells may not be initialized to null, so try the CAS operation to increment baseCount value
if((as = counterCells) ! =null| |! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// There are two possible ways to enter this block
//1. CounterCells are initialized and not null
//2. The CAS operation failed to increment the baseCount value
CounterCell a; long v; int m;
// Whether the flag is competing
boolean uncontended = true;
Check whether the counter bucket is not initialized. If as=null, the statement block is entered
//2. Check whether the bucket length is empty or, if yes, enter the statement block
//3. Create a thread variable with a random number, and the bucket size -1, if the bucket position is empty, enter the statement block
//4. The bucket is initialized, and the random position is not empty
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;
// Count the container sizes = sumCount(); }... }Copy the code7.2 Optimization of Counting Buckets
Counting bucket optimization, when there is less competition, counting bucket has little meaning. So actually two ideas are used:
- Increment baseCount directly in CAS mode: When threads are not in contention, the CAS operation is used to increment baseCount
- Divide-and-conquer bucket counting: If the CAS operation fails, then threads are contended and the counting mode changes from CAS to divide-and-conquer bucket counting
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; longv; .// If count buckets! =null, indicating that the statement block is initialized
if((as = counterCells) ! =null && (n = as.length) > 0) {... }// Enter this statement block to initialize the count bucket
//CAS set cellsBusy=1, so now count bucket Busy...
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
// If a thread initializes the count bucket at the same time, only one thread enters here due to the CAS operation
boolean init = false;
try { // Initialize table
// Double check that the count bucket is empty
if (counterCells == as) {
// Initialize a count bucket of length 2
CounterCell[] rs = new CounterCell[2];
//h is a random number, and 1 represents the random result of 0 or 1
// Select a bucket from the index 0 and 1, x=1, and add 1 to the bucket to increase the capacity
rs[h & 1] = new CounterCell(x);
// Assign the initialized count bucket to ConcurrentHashMap
counterCells = rs;
init = true; }}finally {
// Set the busy flag to 0 to stop busy
cellsBusy = 0;
}
if (init)
break;
}
// If the wired program initializes the count bucket at the same time, the CAS increment baseCount is performed by the thread that does not get the BUSY qualification
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base}}Copy the code7.3 Expanding the Capacity of count Buckets
As we know from the above analysis, the length of the count bucket after initialization is 2, which will certainly not be enough when the competition is large, so there must be an expansion operation of the count bucket.
7.3.1 Expansion Timing of Count Buckets
After the CAS operation fails to increase the number of counting buckets for three times, the system expands the number of counting buckets. Note that two random positions are performed to increase the number of counting buckets at the same time to increase the NUMBER of counting buckets. Therefore, it is highly likely that the number of counting buckets is insufficient
7.3.2 Capacity Expansion
The count bucket is twice as long, and the data is directly traversed. Since the count bucket is not as complex as the HashMap data structure, it has the influence of the hash algorithm, and the count bucket only holds a long value, so it can be directly assigned to the reference.
7.3.3 Design inspiration
- CAS is used to sense whether there is thread competition. If the competition is not large, the CAS increment value can be directly used, and there is little difference between performance and direct addition.
- If there are threads competing, divide and conquer is used to disperse threads, reduce conflicts, and “load balance” is used to distribute thread count requests evenly in each bucket.
Eight. JDK1.7 version design ideas
Since the mainstream versions are all 1.8 and above, the 1.7 design is a bit behind, but there are still a lot of lessons to learn, which I will briefly discuss here.
8.1 Transforming hashMap to be thread-safe
- First: borrow from hashTable
Synchronized object lock is used for PUT method to ensure security, but its disadvantages are coarse granularity and poor concurrency performance.
- The second kind: sectional lock
ConcurrentHashMap => Segment[] =>Entry[]; So the granularity is a little bit smaller.
The first performance defect is too obvious, 1.7 adopted the second scheme.
8.2 How to Segment
Derive segmentation rules based on three important parameters:
- The first parameter represents the total number of entries
- The second parameter is the load factor
- The third parameter is the total number of segments
How many entries are in a segment? The relationship is not fixed. Round up the total number of entries/total number of seGs
So CEIL of 17/16 is equal to 2
In addition, following the standard of hashMap, the length of each entry array must be a power of 2, so if the above calculation is not a power of 2, it needs to be converted to a power of 2
CEIL(33/16) = 3, toSize(3) = 4. That is, there are four entries in a segment
8.3 Thread safety during PUT
Find the Segment first and then the entry below.
Use hashCode & (segments. Length-1) to find segment index;
Unsafe is used to ensure thread-safety when inserting segments, and the internal mechanism is spinlock + CAS
To find the index of an entry, use hashCode & (entrys.length-1);
Use tryLock and lock to ensure thread-safety when inserting entry
A few tricky details about implementation:
-
Use while + tryLock to spin non-blocking and create nodes during non-blocking
-
Set the number of retries. When the retries expires, the lock blocks to avoid CPU consumption
-
An even number of retries determine whether the head node has been updated by another thread. If the update needs to be fetched from the new head node, repeat 123.
Note: Put is still inserted by head
8.4 How To Expand Capacity
Without breaking the idea of HashMap, expansion is still done in entry, and partial expansion is adopted, that is, an entry within a SegMeng for expansion.
The segment length is invariant after initialization.
Details: Why does the Transfor method loop twice? Just loop through the list once like a hashMap.
Here is a small optimization. The purpose of the first loop is to search the linked list from back to front for the continuous nodes with the same index after rehash. In this way, the continuous nodes can be directly put to the new location by breaking the chain once to improve performance. (Similar to Spider solitaire)