Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java 8 ConcurrentHashMap

Tags:

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.

like image 705
Eddie Avatar asked Jun 09 '17 14:06

Eddie


1 Answers

Short answer

The Node#val is volatile which establishes your happens before ordering.

Longer answer

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.

like image 156
John Vint Avatar answered Sep 19 '22 15:09

John Vint