I've observed that ConcurrentHashMap has been entirely rewritten in Java 8 to be more "lock-free". I've browsed the code of the get()
method and see that there is no explicit lock mechanism:
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;
}
Question:
How it is possible to see from one thread, modifications done to this hashmap from other threads, since the code isn't under a synchronize umbrella (which would enforce a happens-before relation)?
Note: The entire ConcurrentHashMap is a wrapper of a table:
transient volatile Node<K,V>[] table;
So table
is a volatile reference to an array, not a reference to an array of volatile elements! Which means that if someone is updating an element inside this array, the modification won't be seen in other threads.
The Node#val
is volatile
which establishes your happens before ordering.
synchronized
isn't a requirement for thread safety, it's one tool in a toolbox to make a system thread safe. You'll have to consider an entire set of actions on this ConcurrentHashMap
to reason about thread safety.
It's useful to know the original ConcurrentHashMap
too is non-blocking. Notice pre-Java 8 CHM get
V get(Object key, int hash) {
if (count != 0) { // read-volatile
HashEntry<K,V> e = getFirst(hash);
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)
return v;
return readValueUnderLock(e); // ignore this
}
e = e.next;
}
}
return null;
}
In this case, there is no blocking, so how does it work? The HashEntry#value
is volatile
. That is the synchronization point for thread safety.
The Node
class for CHM-8 is the same.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
So a non-null val in this case should ensure thee happens-before relationship with respect to actions prior to a put.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With