Inside Java 8’s ConcurrentHashMap: How the New Lock‑Free Design Works
This article explains the structural changes of ConcurrentHashMap in JDK 8, covering the new table layout, node types, hash spreading, initialization, resizing mechanics, treeification, and the lock‑free algorithms that enable concurrent expansion and high‑performance operations.
Important Concepts
Before analysing the source we must understand a few key fields and their meanings.
table
All entries are stored in the table array, which expands as needed. Each slot can hold one of three node types:
TreeBin – wraps a red‑black tree node
ForwardingNode – used during resizing
Node – ordinary linked‑list node
nextTable
Temporary array used while resizing; it is set to null after the resize finishes.
sizeCtl
A volatile field that controls table initialization and resizing. Its possible values are:
// not initialized: 0 // no initial capacity specified
// initialized: >0 // derived from the requested initial capacity, rounded up to the nearest power of two
// initializing: -1 // table is being initialized
// resizing: negative value where high bits encode the resize stamp and low bits encode the number of threads participating in the resize
// resize completed: table.length * 0.75 // threshold for the next resizeput()
public V put(K key, V value) {
return putVal(key, value, false);
}
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;;) {
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // initialize
Node<K,V> f; int i, fh;
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<>(hash, key, value, null)))
break; // create first node
} else if ((fh = f.hash) == MOVED) {
tab = helpTransfer(tab, f);
} else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { // linked list
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) {
pred.next = new Node<>(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 (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null) return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}spread()
The hash spreading function reduces collisions:
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}initTable()
Initialises the table array without a lock. Concurrency is handled by CAS on sizeCtl:
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield();
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2); // 0.75 * n
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}tabAt() / casTabAt() / setTabAt()
Low‑level memory operations on the table array. ABASE and ASHIFT compute the memory offset of table[i]:
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);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}Writes performed by setTabAt occur only inside locked regions, so they use volatile semantics conservatively.
TreeBin
When a bucket exceeds TREEIFY_THRESHOLD (default 8), the linked list is transformed into a red‑black tree to achieve O(log n) lookup.
Every node is either red or black.
The root is always black.
All leaves are null (black).
Red nodes cannot have red children.
Every path from a node to its descendant leaves contains the same number of black nodes.
treeifyBin()
If a bucket’s size reaches the threshold, it is converted to a TreeBin. If the overall table is too small ( MIN_TREEIFY_CAPACITY), the table is first resized.
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p = new TreeNode<>(e.hash, e.key, e.val, null, null);
if ((p.prev = tl) == null) hd = p; else tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<>(hd));
}
}
}
}
}TreeBin Constructor
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);
this.first = b;
TreeNode<K,V> r = null;
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (r == null) {
x.parent = null;
x.red = false; // root is black
r = x;
} else {
// insert x into the tree rooted at r
// ... (comparison logic omitted for brevity) ...
r = balanceInsertion(r, x);
}
}
this.root = r;
}Resizing Implementation
The author wrote this article to explain how resizing works.
When does resizing happen?
Adding an entry via put() calls addCount(), which checks sizeCtl. tryPresize() is also invoked in two situations:
When a bucket is about to be tree‑ified and the table size is less than MIN_TREEIFY_CAPACITY.
When bulk operations like putAll() insert many elements at once.
addCount()
After a successful insertion, addCount() decides whether a resize is needed based on the current threshold.
private final void addCount(long x, int check) {
// ... omitted ...
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
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 (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
} else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}resizeStamp()
Encodes the current capacity into a stamp used to coordinate concurrent resizes.
static final int RESIZE_STAMP_BITS = 16;
static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}The high 16 bits of the stamp are zero, the 16th bit is one, and the low 15 bits store the capacity identifier.
tryPresize()
Computes the target capacity (next power of two) and attempts to initialise or expand the table.
private final void tryPresize(int size) {
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;
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
} else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
// already resizing – help
// ... omitted ...
} else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}transfer()
The core of concurrent resizing. Threads claim a range of buckets (minimum stride 16) and move entries to the new table.
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;
if (nextTab == null) {
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) {
sizeCtl = Integer.MAX_VALUE; // protect against OOME
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<>(nextTab);
boolean advance = true, finishing = false;
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;
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; // re‑check before commit
}
} else if ((f = tabAt(tab, i)) == null) {
advance = casTabAt(tab, i, null, fwd);
} else if ((fh = f.hash) == MOVED) {
advance = true;
} else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) { // linked list
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<>(ph, pk, pv, ln);
else
hn = new Node<>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
} else if (f instanceof TreeBin) {
// tree migration (omitted for brevity)
}
}
}
}
}
}helpTransfer()
When a thread encounters a ForwardingNode it assists the ongoing resize.
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && f instanceof ForwardingNode &&
(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;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}Concurrent Expansion Summary
A single thread creates nextTable, usually double the old capacity.
When a thread accesses a bucket that holds a ForwardingNode, it helps finish the resize before proceeding.
Buckets are assigned to threads in reverse order, with a minimum stride of 16 to reduce contention.
During migration, reads are delegated to the ForwardingNode which forwards the lookup to nextTable. sizeCtl tracks the number of threads participating in the resize; after completion it is set to 0.75 × new capacity.
get()
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;
} 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;
}remove()
public V remove(Object key) {
return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key || (ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev || (ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null) break;
}
} else if (f instanceof TreeBin) {
// tree removal (omitted)
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}Main Improvements in JDK 8
The new implementation combines CAS‑based lock‑free updates with synchronized blocks for bucket‑level safety, supports concurrent resizing, and replaces the old segmented lock structure with an array of nodes, linked lists, and red‑black trees, resulting in higher throughput.
Deprecated Variables from Earlier Versions
Segment– retained only for serialization. loadFactor – used only during construction; the resize threshold is now fixed at 0.75. concurrencyLevel – influences only the initial capacity, not the runtime table size.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
Java Interview Crash Guide
Dedicated to sharing Java interview Q&A; follow and reply "java" to receive a free premium Java interview guide.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.