NOTE
6.29 ConcurrentHashMap in JDK 1.8
1. What it is. A thread-safe HashMap implemented with synchronized + CAS + the HashMap structure (array + linked list + red-black tree). 2. How to use it. 3. Principle analysis: constructor, Node, put, initialization, insertion, resizing, get, remove, and containsKey.
This is a historical learning note and may contain outdated or incomplete understanding.
1. What It Is
A thread-safe HashMap. Its underlying implementation uses synchronized + CAS + the HashMap structure (array + linked list + red-black tree).
2. How to Use It
public class ConcurrentHashMapTest
{
public static void main(String[] args) throws InterruptedException
{
ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
Thread thread1 = new Thread(()->{
for (int i = 0; i < 100000; i++)
{
map.put(i, i);
}
});
Thread thread2 = new Thread(()->{
for (int i = 100000; i < 200000; i++)
{
map.put(i, i);
}
});
thread1.start();
thread2.start();
thread1.join();
thread2.join();
System.out.println(map);
System.out.println(map.size());
for (int i = 0; i < 200000; i++)
{
if (!map.contains(i))
{
throw new RuntimeException("There is a problem with concurrent put");// If no exception is thrown, concurrent put works correctly
}
System.out.println(map.remove(i));
}
}
}3. Principle Analysis
3.1. Constructor
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
private static final long serialVersionUID = 7249069246763182397L;
// Maximum array length. Must be a power of two
private static final int MAXIMUM_CAPACITY = 1 << 30;
// Default array length. Must be a power of two
private static final int DEFAULT_CAPACITY = 16;
// Default load factor.
// Resize when the number of entries containing elements in the array >= array length * LOAD_FACTOR
private static final float LOAD_FACTOR = 0.75f;
// When the number of elements in a linked list (excluding the head node) reaches 8,
// it needs to be converted into a red-black tree
static final int TREEIFY_THRESHOLD = 8;
// When the number of elements in a red-black tree (excluding the head node) reaches 6,
// it needs to be converted back into a linked list
static final int UNTREEIFY_THRESHOLD = 6;
// Convert to a red-black tree only when the number of entries in the array reaches 64
static final int MIN_TREEIFY_CAPACITY = 64;
// -1 means initialization is in progress, or (-1 + number of threads currently resizing)
// 0 or a positive number means the hash table has not yet been initialized
private transient volatile int sizeCtl;
// The Node array is declared volatile. If the array reference itself (not its contents) changes,
// other threads can immediately observe it (volatile visibility).
// This should be used when resizing changes the Node array.
transient volatile Node<K,V>[] table;
public ConcurrentHashMap() {
}
}3.1.1. Node
static class Node<K,V> implements Map.Entry<K,V> {
// final on key and hash indicates that these are constants
// Constants are thread-safe
final int hash;
final K key;
// val and next are both volatile (visibility + ordering)
// Combined with CAS operations (atomicity), this can ensure thread safety
// This is also why get does not need to acquire a lock
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
}3.2. The put Method [Uses Locking]
public V put(K key, V value) {
// Pass key and value to putVal
return putVal(key, value, false);
}putVal
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();// null keys or values are not allowed
// (h ^ (h >>> 16)) & HASH_BITS(0x7fffffff)
int hash = spread(key.hashCode());
int binCount = 0;
// Infinite loop combined with CAS
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// If table is empty, initialize table the first time
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// The linked-list head is null, so try to CAS-set the head node
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // CAS successfully set the head node; break directly
}
// Another thread is moving elements
else if ((fh = f.hash) == MOVED)
// Help the other thread resize
tab = helpTransfer(tab, f);
// The linked-list head is not null. Reaching here means a hash collision occurred
else {
V oldVal = null;
// Contention may be high, so use synchronized instead of CAS
// Compared with JDK 7, the lock granularity is smaller here:
// it is reduced to the head node of each linked list in the array
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {// A head-node hash >= 0 means this is a linked list
binCount = 1;
// Traverse the linked list, using binCount to count the number of nodes
for (Node<K,V> e = f;; ++binCount) {
K ek;
// Found an equal node: save oldVal, update val, and exit the loop
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;
// Reached the tail node: insert directly at the end
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// If it is a tree node, delegate to the tree
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;
}
}
}
}
// Determine whether treeification is needed
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// Update the count
addCount(1L, binCount);
return null;
}- Line 4: calculate the key’s hash. This is not simply
key.hashCode(). - Line 7: infinite loop until success.
- Lines 10-11: on the first pass,
tableis empty, so it needs to be initialized. - Lines 13-17: on the second pass,
tableis non-empty and the linked list is empty [the head node is null], so CAS is used to set the head node. - Lines 22-72: on the third pass, if the linked list is not empty [the head node is non-null], lock the head node and insert using either linked-list operations or tree operations.
- Line 75: increment the count and determine whether resizing is needed.
3.2.1. Calculate the Key’s Hash
spread
static final int spread(int h) {
// XOR the high 16 bits and low 16 bits of hashCode so that every bit participates in the calculation,
// reducing the probability of hash collisions
// AND with HASH_BITS (0x7fffffff) to ensure that no negative number appears?
return (h ^ (h >>> 16)) & HASH_BITS;
}3.2.2. Infinite Loop
for (Node<K,V>[] tab = table;;) {
//....
}3.2.3. First Pass: table Is Empty, So Initialize table
// If table is empty, initialize table the first time
if (tab == null || (n = tab.length) == 0)
tab = initTable();initTable
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// This is also an infinite loop
while ((tab = table) == null || tab.length == 0) {
// sizeCtl < 0 means another thread is initializing or resizing
if ((sc = sizeCtl) < 0)
// Yield the CPU so the thread performing resize or initialization can run
Thread.yield(); // lost initialization race; just spin
// The current thread tries to change sizeCtl to -1 (meaning the array is being initialized).
// On success, enter the initialization logic
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// First initialization
if ((tab = table) == null || tab.length == 0) {
// Capacity is 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// Create a Node array of length n
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// sizeCtl becomes 8
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}3.2.3.1. Use CAS as a Lock to Prevent Multiple Threads from Initializing table at the Same Time
// The current thread tries to modify sizeCtl. On success, enter the initialization logic
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// First initialization
if ((tab = table) == null || tab.length == 0) {
// Capacity is 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// Create a Node array of length n
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// sizeCtl becomes 8
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}3.2.3.2. Other Threads Yield the CPU Until Resizing Finishes
while ((tab = table) == null || tab.length == 0) {
// sizeCtl < 0 means initialization or resizing is in progress
if ((sc = sizeCtl) < 0)
// Yield the CPU so the resizing or initializing thread can run
Thread.yield(); // lost initialization race; just spin
}3.2.4. Second Pass: table Is Non-Empty and the Linked List Is Empty [Head Node Is Null], So CAS-Set the Head Node
// The linked-list head is null
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// Try to CAS-set the head node
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}3.2.4.1. Get the First Element
First calculate the element position through (n - 1) & hash. Since n is a power of two, n - 1 is equivalent to having the highest bit set to 0 and all the remaining lower bits set to 1. AND-ing hash with this value produces the same result as taking the hash modulo the array length, but is more efficient.
Then obtain the element at that position through an Unsafe volatile operation [each element is either the head node of a linked list or the root node of a red-black tree].
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
// Obtained through Unsafe
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}3.2.4.2. CAS-Set the Head Node
casTabAt
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
// Also set through Unsafe
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}3.2.5. Third Pass: If the Linked List Is Non-Empty [Head Node Is Non-Null], Lock the Head Node and Insert Using Linked-List or Tree Operations
// The linked-list head is non-null
else {
V oldVal = null;
// Contention may be high, so use synchronized instead of CAS
// Compared with JDK 7, the lock granularity is smaller here:
// the lock granularity is reduced to the head node of each linked list in the array
// JDK 7 locks a Segment (similar to multiple linked-list head nodes)
synchronized (f) {
// The head node really has not changed -- when would it change?
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// Traverse the linked list and use binCount to count the number of nodes
for (Node<K,V> e = f;; ++binCount) {
K ek;
// Found an equal node: save oldVal, update val, and exit the loop
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;
// Reached the tail node: insert directly at the end and exit the loop
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// If it is a tree node, delegate to the tree
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;
}
}
}
}
// Determine whether treeification is needed
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}3.2.5.1. Specific Insertion Operations
- Line 7: first lock the head node.
- Lines 13-32: if it is a linked-list node, call the linked-list logic to insert the node.
- Line 13: traverse the linked list.
- Lines 16-22: if an equal node is found, replace
value. - Lines 26-29: if no equal node is found, insert at the end of the linked list.
- Lines 34-43: if it is a tree node, call the tree logic to insert the node.
3.2.6. Resizing
I do not really understand this part yet, so I will leave it here for now.
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
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) {
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();
}
}
}3.3. The get Method [No Locking]
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// Calculate the key's hash value
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
// Find the first element
(e = tabAt(tab, (n - 1) & h)) != null) {
// The first node in the linked list is equal
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// eh is the hash value of the first element
// What does hash < 0 mean? It means another thread is resizing
else if (eh < 0)
// What is find used for??
return (p = e.find(h, key)) != null ? p.val : null;
// eh >= 0 means this is a linked list, so traverse it directly to find an equal node
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
// Return null if not found
return null;
}3.3.1. Calculate the Key’s Hash Value
spread
static final int spread(int h) {
// XOR the high 16 bits and low 16 bits of hashCode so that every bit participates in the calculation,
// reducing the probability of hash collisions
// AND with HASH_BITS (0x7fffffff) to ensure that no negative number appears?
return (h ^ (h >>> 16)) & HASH_BITS;
}3.3.2. Get the First Element
First calculate the element position through (n - 1) & hash. Since n is a power of two, n - 1 is equivalent to having the highest bit set to 0 and all the remaining lower bits set to 1. AND-ing hash with this value produces the same result as taking the hash modulo the array length, but is more efficient.
Then obtain the element at that position through an Unsafe volatile operation [each element is either the head node of a linked list or the root node of a red-black tree].
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
// Obtained through Unsafe
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}3.3.3. The First Element Is the Node Being Searched For
if ((eh = e.hash) == h) {// hash values are equal
// key references are equal or key contents are equal
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}3.3.4. The First Element Is Not the Target Node and hash <= 0
3.3.5. The First Element Is Not the Target Node and hash >= 0, Meaning It Is a Linked List; Traverse the List to Find an Equal Node
// Traverse the linked list to find an equal node
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}3.4. The remove Method [Uses Locking]
public V remove(Object key) {
return replaceNode(key, null, null);
}replaceNode
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
// Infinite loop
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// table is empty
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// Resizing
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
// Use synchronized for locking
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
// Traverse every node in the linked list
for (Node<K,V> e = f, pred = null;;) {
K ek;
// Found an equal node
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;
// e is not the head node: update the linked-list pointer directly
else if (pred != null)
pred.next = e.next;
// e is the head node
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
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;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}3.4.1. Infinite Loop
for (Node<K,V>[] tab = table;;) {
}3.4.2. If table Is Empty or the Linked-List Head Is Null, the Key Does Not Exist, So Return Null
// table is empty
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;// Break the loop; null is returned at the end3.4.3. If the Head Node Is Non-Null, Lock It First, Then Delete the Node Using Tree or Linked-List Operations
else {
V oldVal = null;
boolean validated = false;
// Use synchronized for locking
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
// Traverse every node in the linked list
for (Node<K,V> e = f, pred = null;;) {
K ek;
// Found an equal node
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;
// e is not the head node: update the linked-list pointer directly
else if (pred != null)
pred.next = e.next;
// e is the head node
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
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;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}3.4.3.1. Delete a Node from the Linked List — Update the Pointers
// Traverse every node in the linked list
for (Node<K,V> e = f, pred = null;;) {
K ek;
// Found an equal node
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;
// This node e is not the head node, so update the previous node's next pointer directly
else if (pred != null)
pred.next = e.next;
// This node e is the head node, so set e.next as the head node
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}setTabAt
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}3.5. The containsKey Method [No Locking]
public boolean containsKey(Object key) {
// Calls get, which also does not acquire a lock
return get(key) != null;
}
Discussion
Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub