Core Data Structures and Constants
The internal mechanics rely heavily on bitwise operations and volatile state variables. The maximum capacity is constrained to a power of two to allow bitwise masking for index calculation.
private static final int MAX_CAPACITY_LIMIT = 1 << 30;
private static final int MIN_RELOCATION_STRIDE = 16;
private static final int STAMP_BITS = 16;
private static final int MAX_RESIZE_THREADS = (1 << (32 - STAMP_BITS)) - 1;
private static final int STAMP_SHIFT = 32 - STAMP_BITS;
// Node hash field encodings
static final int RELOCATING = -1; // Slot is undergoing migration
static final int TREE_ROOT = -2; // Slot holds a Red-Black Tree
static final int PLACEHOLDER = -3; // Temporary reservation
static final int POSITIVE_MASK = 0x7fffffff; // Forces hash to be positive
// Core state variables
transient volatile Node<K,V>[] mainArray;
private transient volatile Node<K,V>[] targetArray;
private transient volatile long baseCounter;
private transient volatile int resizeControl; // Controls init and resizing
private transient volatile int relocationClaimIndex;
private transient volatile int counterLock;
private transient volatile CellCounter[] cellCounters;
Hash Distribution Strategy
To prevent hash collisions where only the lowest bits determine the slot, the high 16 bits are XORed with the low 16 bits. Additionally, the result is masked with POSITIVE_MASK to ensure the hash remains positive, as negative hashes denote special node states.
static final int distributeHash(int rawHash) {
return (rawHash ^ (rawHash >>> 16)) & POSITIVE_MASK;
}
Slot indexing uses a bitwise AND operation with the array length minus one. Since lengths are powers of two, length - 1 produces a bitmask (e.g., 15 = 00001111) that perfectly constrains the index within bounds.
Capacity Initialization
When creating the map, the desired capacity is adjusted to the nearest power of two to prevent immediate resizing.
public ConcurrentMap(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException();
int cap = (initialCapacity >= (MAX_CAPACITY_LIMIT >>> 1)) ?
MAX_CAPACITY_LIMIT :
calculatePowerOfTwo(initialCapacity + (initialCapacity >>> 1) + 1);
this.resizeControl = cap;
}
Read Operations
Retrieving a value requires no locks. It calculates the hash, locates the slot, and traverses the structure. If the slot header has a negative hash, it delegates to the specific node's find logic.
public V retrieveValue(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = distributeHash(key.hashCode());
if ((tab = mainArray) != 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;
} else if (eh < 0) {
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))))
return e.val;
}
}
return null;
}
Insert Operations
Inserting a key-value pair loops until successful. It handles uninitialized arrays, empty slots via CAS, ongoing resizes, and locked bucket heads for hash collisions.
final V insertEntry(K key, V value, boolean onlyIfMissing) {
if (key == null || value == null) throw new NullPointerException();
int hash = distributeHash(key.hashCode());
for (Node<K,V>[] tab = mainArray;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initializeArray();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break;
} else if ((fh = f.hash) == RELOCATING) {
tab = assistResizing(tab, f);
} else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// Linked list traversal and insertion logic
} else if (f instanceof RedBlackTreeBucket) {
// Tree insertion logic
}
}
}
// Treeification check and size increment
}
}
incrementSize(1L, binCount);
return null;
}
Array Initialization
Threads compete to initialize the array using CAS on resizeControl. A successful thread changes resizeControl to -1, initializes the array, and sets resizeControl to the expansion threshold (0.75 * capacity).
private final Node<K,V>[] initializeArray() {
Node<K,V>[] tab; int sc;
while ((tab = mainArray) == null || tab.length == 0) {
if ((sc = resizeControl) < 0)
Thread.yield(); // Spin while another thread initializes
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = mainArray) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
mainArray = tab = nt;
sc = n - (n >>> 2);
}
} finally {
resizeControl = sc;
}
break;
}
}
return tab;
}
Size Tracking and Resize Triggering
Element counting uses a striped approach similar to LongAdder to reduce contention. If CAS on baseCounter fails, threads attempt to update specific cellCounters. A historical bug (JDK-8214427) existed in the size control checks where the resize stamp wasn't properly shifted during comparison. The corrected logic ensures the stamp is shifted left by STAMP_SHIFT before comparing with resizeControl.
private final void incrementSize(long x, int check) {
CellCounter[] as; long b, s;
if ((as = cellCounters) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCounter, s = b + x)) {
// Striped counting logic
fullAddCount(x, uncontended);
return;
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = resizeControl) && (tab = mainArray) != null &&
(n = tab.length) < MAX_CAPACITY_LIMIT) {
int rs = resizeStamp(n) << STAMP_SHIFT;
if (sc < 0) {
if (sc == rs + MAX_RESIZE_THREADS || sc == rs + 1 ||
(nt = targetArray) == null || relocationClaimIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
relocateBuckets(tab, nt);
} else if (U.compareAndSwapInt(this, SIZECTL, sc, rs + 2))
relocateBuckets(tab, null);
s = sumCount();
}
}
}
Assisted Resizing
When an insert encounters a slot marked with RELOCATING, it attempts to join the ongoing resize effort. The corrected implementation ensures proper stamp shifting to accurately track the number of participating threads.
final Node<K,V>[] assistResizing(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof RelocationMarker) &&
(nextTab = ((RelocationMarker<K,V>)f).targetArray) != null) {
int rs = resizeStamp(tab.length) << STAMP_SHIFT;
while (nextTab == targetArray && mainArray == tab && (sc = resizeControl) < 0) {
if (sc == rs + MAX_RESIZE_THREADS || sc == rs + 1 || relocationClaimIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
relocateBuckets(tab, nextTab);
break;
}
}
return nextTab;
}
return mainArray;
}
Bucket Relocation and Splitting
The relocation process divides the array into strides, allowing multiple threads to migrate different segments concurrently. It uses a RelocationMarker to claim empty slots. For occupied slots, it locks the head node and splits linked lists or trees based on the high bit of their hash relative to the old capacity.
private final void relocateBuckets(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_RELOCATION_STRIDE)
stride = MIN_RELOCATION_STRIDE;
if (nextTab == null) { // Initiating thread creates the target array
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
targetArray = nextTab;
relocationClaimIndex = n;
}
int nextn = nextTab.length;
RelocationMarker<K,V> marker = new RelocationMarker<K,V>(nextTab);
boolean advance = true;
boolean finishing = false;
for (int i = 0, bound = 0;;) {
// Stride claiming logic via CAS on relocationClaimIndex
// ...
if (i < 0 || i >= n || i + n >= nextn) {
// Completion and final cleanup logic
} else if ((f = tabAt(tab, i)) == null) {
advance = casTabAt(tab, i, null, marker);
} else if ((fh = f.hash) == RELOCATING) {
advance = true;
} else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
// Split linked list into low (ln) and high (hn) lists
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; }
}
// Separate nodes before lastRun using head insertion
// Place ln at i, hn at i + n
} else if (f instanceof RedBlackTreeBucket) {
// Split tree into low and high TreeBins
}
}
}
}
}
}
Atomic Computation with Placeholders
Methods like computeIfAbsent use a PlaceholderNode to lock an empty slot before evaluating the mapping function, preventing redundant computations.
public V computeAtomicallyIfMissing(K key, Function<? super K, ? extends V> mapper) {
int h = distributeHash(key.hashCode());
V val = null;
for (Node<K,V>[] tab = mainArray;;) {
// ... initialization and resize checks ...
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
Node<K,V> r = new PlaceholderNode<K,V>();
synchronized (r) {
if (casTabAt(tab, i, null, r)) {
try {
if ((val = mapper.apply(key)) != null)
node = new Node<K,V>(h, key, val, null);
} finally {
setTabAt(tab, i, node); // Replace placeholder
}
}
}
}
// ... existing key logic ...
}
}
Relocation Marker Find Logic
During a resize, reads hitting a RelocationMarker are forwarded to the target array. It uses an outer loop to handle nested relocations gracefully.
static final class RelocationMarker<K,V> extends Node<K,V> {
final Node<K,V>[] targetArray;
RelocationMarker(Node<K,V>[] tab) {
super(RELOCATING, null, null, null);
this.targetArray = tab;
}
Node<K,V> find(int h, Object k) {
outer: for (Node<K,V>[] tab = targetArray;;) {
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 RelocationMarker) {
tab = ((RelocationMarker<K,V>)e).targetArray;
continue outer;
} else {
return e.find(h, k);
}
}
if ((e = e.next) == null) return null;
}
}
}
}