ConcurrentHashmap in JDK8 code explanation

Question

I have been trying to understand the ConcurrentHashMap functions in JDK8, in contrast of how it was in JDK7 (which, in addition to the source code, can be found explained quite well by some nice folks out there such as Richard http://www.burnison.ca/articles/the-concurrency-of-concurrenthashmap). It looks like have been changed quite a bit in JDK8 - e.g. there is no more 'segment' per se, but somehow I got a feeling that the changes are meant to make the code simpler?

1. I'm having some difficulty to understand the method ConcurrentHashMap.putVal(...), especially the following section - is this straight-forward locking on the head of the 'segment' list anyway for insertion in the else{}?:

       else if ((fh = f.hash) == MOVED)
           tab = helpTransfer(tab, f);
       else {//...}
   

2. Not so sure about code of the ConcurrentHashMap.casTabAt(...) either.

3. Also, about the source code of ConcurrentHashMap.get(Object key) in JDK8, is it strictly no lock at all (I'm not seeing any, if so, how does it work without lock as I don't see a loop 'try-again' either?) or there is some kind of optimistic lock that I'm not observing?

Appreciate if someone could offer some hint.

Answer 1

About the putVal(K key, V value, boolean onlyIfAbsent) method

Each bin/bucket contains a hash field, which combines two purposes in a very clever way:

• For regular bins (most bins containing just a single item), it stores the hash code of the mapped here key. The top bit is cleared though (it's always set to 0).
• For special bins (currently there are 3 types of these), it contains a special negative value. The clever part is that you need just the top bit to distinguish positive from negative values and therefore regular bins from special bins. Distinguishing between the different types of special bins is free to use the remaining 31 bits.

This section

else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);
else {//...}

is the first check after finding that the map is not empty and that the bin for the key you're trying to map is not empty.

It's satisfied in case the bin that you've found is one of the special types of bins - a forwarding bin. Forwarding bins are required because resizing is done concurrently and iteratively and already transferred (to the new table) entries still need to be accessible (through the forwarding bin in the old table).

About the casTabAt((Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) method

The casTabAt() method is used to atomically set a map entry using compare-and-swap operation for object references. You can still see the typical CAS loop in practically all places where casTabAt() is used - you construct the object that you want to put and then try to CAS it in its rightful place. If it feels weird that a complex construction can precede the CAS attempt, you can take a look at Jeff Preshing's You Can Do Any Kind of Atomic Read-Modify-Write Operation.

In a sense, ConcurrentHashMap still uses striped locking, but with finer lock granularity (the contended area is now minimized from multi-bin segments to individual bins) and with locks being almost entirely replaced by CAS operations.

About the get(Object key) method

The get() method can get away without any locking, because in most cases the bin contents are being set and retrieved using volatile semantics (through the aforementioned casTabAt() method and the related tabAt() method). The situation is trickier in case the bin contains a red-black tree of entries that were mapped to the same bin, and you can see that traversal within the accessed TreeBin is always done in a synchronized block.