preface
This article concludes with JDK 1.8’s ConcurrentHashMap.
Suggest not read the source code can be seriously, read the source code can be directly jumped summary.
attribute
/ / bucket array
transient volatile Node[] table;
// Expand the array, only during the expansion will not be empty
private transient volatile Node[] nextTable;
// Control the expansion variables. When the value is negative, the table is being initialized or expanded. -1 indicates that the table is being initialized, and -n indicates the number of threads being expanded. When the table is null, the variable is the size or 0 value of the created table. After the table is initialized, the variable is the size of the next expansion
private transient volatile int sizeCtl;
/* ---------------- Constants -------------- */
// The maximum capacity of the table. 2 ^ 30 =1073741824
private static final int MAXIMUM_CAPACITY = 1 << 30;
// The initial default capacity of the table.
private static final int DEFAULT_CAPACITY = 16;
// Maximum array size. 2 ^ 31-1 = 2147483647
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// The default concurrency level. The maximum number of threads that can simultaneously update ConccurentHashMap without lock contention was actually the number of Segment locks in ConcurrentHashMap prior to Java8, i.e., the array length of Segment[]. It is important to estimate correctly, when underestimated, data structures will block based on additional contention, resulting in threads trying to write to the currently locked segment; Conversely, if you overestimate the concurrency level, you encounter excessive bloat due to the unnecessary number of segments; This bloat can cause performance degradation due to high number of cache misses. In Java8, it is reserved only for compatibility with older versions. The only effect is to ensure that the initial capacity of the map is not smaller than concurrencyLevel.
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// Load factor for capacity expansion
private static final float LOAD_FACTOR = 0.75 f;
// The list tree threshold
static final int TREEIFY_THRESHOLD = 8;
// The tree list threshold
static final int UNTREEIFY_THRESHOLD = 6;
// The minimum capacity of a red-black tree. The minimum value is 4 times TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
/** * Minimum number of rebinnings per transfer step. Ranges are * subdivided to allow multiple resizer threads. This value * serves as a lower bound to avoid resizers encountering * excessive memory contention. The value should be at least * DEFAULT_CAPACITY. */
private static final int MIN_TRANSFER_STRIDE = 16;
/** * The number of bits used for generation stamp in sizeCtl. * Must be at least 6 for 32bit arrays. */
private static int RESIZE_STAMP_BITS = 16;
static final int MOVED = -1; // hash for forwarding nodes
static final int TREEBIN = -2; // hash for roots of trees
static final int RESERVED = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
// The number of CPU cores
static final int NCPU = Runtime.getRuntime().availableProcessors();
Copy the codeput
- Computes the hash (16 bits higher and 16 bits lower in the hashCode of the key, then modulates according to the capacity)
- Iterate over table and insert:
- Table is empty and initialized
- If bucket is empty, insert
- If the table is being expanded, expand the table
- If the bucket is not empty, lock the head/root and insert
- The number of nodes in the bucket was greater than the threshold and the number of buckets reached 64
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// Perform a conversion on the key's hashcode
int hash = spread(key.hashCode());
int binCount = 0;
// walk through the table. It's an infinite loop until the insert is successful
for (Node[] tab = table;;) {
// f current bucket; N Total length of the bucket; I The location of the barrel; Fh Hash of elements in the bucket
Node f; int n, i, fh;
// If the table is empty, initialize it
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// If the table is not empty. Then determine whether the inserted position in the table is empty. The inserted position is obtained by modulo the transformed hash value and the length of the table
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// cas operation inserts the value
if (casTabAt(tab, i, null.new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// If it is detected that the capacity is being expanded elsewhere, it will assist the capacity expansion
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// Synchronize code blocks to ensure thread safety
synchronized (f) {
if (tabAt(tab, i) == f) {
// If fh is zero, the data structure in the bucket is linked list
if (fh >= 0) {
binCount = 1;
for (Node 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 pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key,value, null);
break; }}}// If it is TreeBin, fh is -1. If f's class type is TreeBin, it is inserted into the tree structure
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if((p = ((TreeBin)f).putTreeVal(hash, key, value)) ! =null) {
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! =0) {
// If the number of buckets is greater than the tree threshold, the linked list tree needs to be red
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the codeget
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// If the table is not empty and the bucket corresponding to the index is not empty
if((tab = table) ! =null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) ! =null) {
// If the hash of the header is equal to that of the hash, and the key extracted is the same, return the value
if ((eh = e.hash) == h) {
if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
return e.val;
}
// The data structure corresponding to the bucket is a tree (TreeBin's hash is -2)
else if (eh < 0)
return(p = e.find(h, key)) ! =null ? p.val : null;
// Bucket corresponds to a linked list of data structures
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
return e.val; }}return null;
}
Copy the codereplaceNode
- Calculate the hash
- Traversing the table
- Table is empty or index is empty, break
- Help him while table is expanding
- Linked list -> Locks -> Delete
- Red black tree -> lock root -> Delete -> determine if you need to degenerate into a linked list
/ / the key; Value: indicates the new value. CV: old values
final V replaceNode(Object key, V value, Object cv) {
/ / convert the hash
int hash = spread(key.hashCode());
// Walk through the table until the replacement is complete
for (Node[] tab = table;;) {
Node f; int n, i, fh;
// If the node to be replaced does not exist, break
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// If the capacity is being expanded, expand the capacity for the group first
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// Indicates whether the operation is valid
boolean validated = false;
/ / lock
synchronized (f) {
if (tabAt(tab, i) == f) {
/ / list
if (fh >= 0) {
validated = true;
for (Node e = f, pred = null;;) {
K ek;
// Find the hash is equal and the key is equal
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
V ev = e.val;
/ / if the new value is empty | | new value is equal to the old value | | if the old value is not empty, and the old value is equal to the value found
if (cv == null|| cv == ev || (ev ! =null && cv.equals(ev))) {
oldVal = ev;
// If the new value is not empty, replace it with the new value. The corresponding replace method
if(value ! =null)
e.val = value;
// If the new value is null and the successor node is not null, change the pointer. Corresponding remove method
else if(pred ! =null)
pred.next = e.next;
// If the preceding node is empty and the current remove is the head node, change the head, that is, bin
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break; }}/ / the red-black tree
else if (f instanceof TreeBin) {
validated = true;
TreeBin t = (TreeBin)f;
TreeNode r, p;
// If the root node of the tree is not empty and can be found
if((r = t.root) ! =null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null|| cv == pv || (pv ! =null && cv.equals(pv))) {
oldVal = pv;
/ / replace
if(value ! =null)
p.val = value;
/ / delete. If true is returned, the tree is small and needs to be made a linked list
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// If the operation is valid
if (validated) {
if(oldVal ! =null) {
if (value == null)// If the value is not null, the new value is null, indicating that the operation is deleted. Count needs to be reduced by one
addCount(-1L, -1);
return oldVal;
}
break; }}}return null;
}
Copy the codetransfer
private final void transfer(Node[] tab, Node[] nextTab) {
int n = tab.length, stride;
// Divide tasks equally for each kernel and ensure that the number is not less than 16
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// If nextTab is null, initialize it as twice as the original table.
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
// The bucket index location to move first
transferIndex = n;
}
int nextn = nextTab.length;
// Forward node
ForwardingNode fwd = new ForwardingNode(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node f; int fh;
// The index of the bucket that initializes the transformation, and the boundary that the thread handles
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; }}// The index location of the bucket exceeds the boundary. Capacity expansion is complete
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// Clean up the mess
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}}// If the current bucket is empty, there is no list to transfer
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// If the hash state of the current bucket is MOVED, it has been processed
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// Perform the transfer process, need to synchronize, lock
synchronized (f) {
if (tabAt(tab, i) == f) {
// the low ln header and the high hn header
// The table size is increased by one bit. So during the rehash process, you only need to calculate whether the added bit of mod is followed by 0 or 1 for a bucket.
// if = 0, keep position I unchanged. If it is 1, it needs to be moved to the position I + (increase size)
Node ln, hn;
// If the hash value of the head node is greater than 0, it is a linked list
if (fh >= 0) {
int runBit = fh & n;
Node lastRun = f;
for(Node p = f.next; p ! =null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// Only the head node of the status
if (runBit == 0) {
ln = lastRun;
hn = null;
}
// There are only high level headers
else {
hn = lastRun;
ln = null;
}
// Convert a single list to two lists
for(Node 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(ph, pk, pv, ln);
else
hn = new Node(ph, pk, pv, hn);
}
// Set the linked list to the corresponding bucket
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
// Handle red-black trees
else if (f instanceof TreeBin) {
TreeBin t = (TreeBin)f;
// Lo and hi are bucket and high list headers, respectively
TreeNode lo = null, loTail = null;
TreeNode hi = null, hiTail = null;
int lc = 0, hc = 0;
// Add all nodes to the lo and HI lists according to whether the highest bit of the mod is 1
for(Node e = t.first; e ! =null; e = e.next) {
int h = e.hash;
TreeNode p = new TreeNode
(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; }}// If the length of the list is smaller than the threshold of listization, the list is converted to a list, otherwise a red-black tree is formedln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc ! =0)?newTreeBin(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! =0)?new TreeBin(hi) : t;
// Set each to the corresponding TAB
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Copy the codecount
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// If counterCells is not null, the counterCells count is used because concurrency has occurred
// If counterCells is null, CAS fails to 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 is null, the array needs to be initialized
// If as is not null, find the index of the array according to the rule, and cas updates the technique
// If the CAS fails, there are multiple threads competing for the segment, and a loop is needed to make the update successful, which is performed in the fullAddCount method
// When counterCells become unstable, they will also be expanded
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) {
// ...
// Check whether the hashtable needs to be expanded}}Copy the codeconclusion
- implementation
For 1.7, which is an array of segments and multiple hashentries, concurrently lock segments
For 1.8, which is a (volatile) Node array + linked list + red-black tree, Synchronized and CAS are used concurrently
- size
Size is calculated differently in JDK1.7 and JDK1.8.
In 1.7, it is calculated three times without locking. If the results of three times are different, the lock will be added.
1.8 Size is obtained by CAS calculation of baseCount and counterCell, and finally by baseCount and traversal of counterCell array.
1.8 The mappingCount method is recommended because it returns a long value and does not limit the maximum value because size is an int.
- Initialize the
Node val and next will change during capacity expansion, so volatile is needed to ensure visibility and to prevent instruction reordering and disallow pseudo-sharing.
- put
CAS tried spin write, failed spin write and Synchronized lock again.
ConcurrentHashMap cannot store elements whose Key/Value is null.
- get
CAS guarantees atomicity of variables.