How does ConcurrentHashMap work internally

Data Structure

ConcurrentHashMap main motive is to allow concurrent access to the map. HashTable offers synchronized access to the map but the entire map is locked to perform any sort of operation.

In ConcurrentHashMap, the basic strategy is to subdivide the table among segments so that the lock is applied only on a segment rather than the entire table. Each segment manages its own internal hash table in size 2^x >=(capacity/no. of segments).

Locking is applied only for updates. In case of of retrievals, it allows full concurrency, retrievals reflect the results of the most recently completed update operations.

If we assume four threads are going to concurrently work on a map of initial capacity 32, we would want the table to be partitioned into four segments, each managing a hash table of capacity 8.
ConcurrentHashMap Data Structure would be:

For comparison sake, below figure shows the data structure of a HashMap.

Segment

The collection maintains a list of 16 segments by default, each of which is used to guard (or lock on) a single bucket of the map. This effectively means that 16 threads can modify the collection at a single time (as long as they’re all working on different buckets). This level of concurrency can be increased using the optional concurrencyLevel constructor argument.

public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel)

The maximum size it can go up to is 2¹⁶. Greater the concurrency level, greater would be the no. of segments and lesser the size of hash table that the segment manages. Using a significantly higher value than you need can waste space and time, and a significantly lower value can lead to thread contention.

Put Entry

New Entry

ConcurrentHashMap doesn't allow NULL values. The key cannot be NULL, it is used to locate the segment index and then the actual bucket within the segment. The key's hash is re-hashed to strengthen the hash value to defend against poor quality hash functions. This is important as the hash will be used to locate both segment and hash table index. The upper bits will be used to locate the segment index and the lower bits to locate the table index within the segment. This is why re-hashing function is different from that of HashMap as the hash bits need to be spread better to regularize both segment and index locations.

    private static int hash(int h) {
        h += (h <>> 10);
        h += (h <>>  6);
        h += (h <<   2) + (h <>> 16);
    }

Put If Absent

ConcurrentMap offers new method putIfAbsent() which is similar to put except that the value will not be overridden if key already exists. This is equivalent to

if (!map.containsKey(key))
    return map.put(key, value);
else
   return map.get(key);

except that the action is performed atomically.

containsKey is not synchronized so the above code may cause unexpected behavior. Lets look into the below scenario:

Thread A is trying to remove a key, calls remove(key), acquires lock.
Thread B tries to execute above code, calls containsKey(key). The key exists as Thread A has not yet released the lock so the old value is returned.
Thread A removes the key and releases the lock.

The above scenario proves that the code is not atomic as it returned a key which it thinks exists but actually doesn't.
Also, performance wise it is slow, containsKey has to locate the segment and traverse through the table to find the key. Method put needs to do the same traversing to locate the bucket and put the value. The new methodputIfAbsent is a bit faster as it avoids double traversing. It goes through the same internal flow as put, avoids overriding the old value if key already exists and simply returns the old value.

Class Diagram

Below class diagram shows that ConurrentHashMap is made up of Segments which in turn is made up ofHashEntries.

Remove Entry

HashEntry is an immutable class so the next link can't be adjusted. All entries following removed node stays in the list, but all preceding ones need to be cloned.

HashEntry newFirst = e.next;
for (HashEntry p = first; p != e; p = p.next)
newFirst = new HashEntry(p.key, p.hash, newFirst, p.value);
tab[index] = newFirst;

Re-sizing

Since power-of-two expansion is used, the elements from each bin must either stay at same index, or move with a power of two offset.

int idx = e.hash & sizeMask;

For a capacity of 16 elements, sizeMask would be 1111 so the lower 4 bits of hash will form the index.
When the capacity is doubled, sizeMask would be 11111 and now the lower 5 bits of hash will form the index.

So the index would be same if the 5^th is 0 else the index would be incremented by 2⁴.
The trailing consecutive sequence nodes can be re-used instead of unnecessary node creation if they they point to the same slot after the re-hashing. Here in the below example the trailing nodes in blue hues will all end up in the same index.

ConcurrentHashMap example:-

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map;

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapTest {

public static void main(String[] args) {

// ConcurrentHashMap implementation details

Map concurrentHMap = new ConcurrentHashMap();

concurrentHMap.put("FIRST", "1");

concurrentHMap.put("SECOND", "2");

concurrentHMap.put("THIRD", "3");

concurrentHMap.put("FOURTH", "4");

concurrentHMap.put("FIFTH", "5");

concurrentHMap.put("SIXTH", "6");

System.out.println("ConcurrentHashMap before iteration : " + concurrentHMap);

Iterator ccHMapIterator = concurrentHMap.keySet().iterator();

while (ccHMapIterator.hasNext()) {

String key = ccHMapIterator.next();

if (key.equals("FOURTH"))

concurrentHMap.put(key + "-GAURAV", "I AM NEW KEY IN CCHMAP");

}

System.out.println("ConcurrentHashMap after iteration : " + concurrentHMap);

System.out.println("**************************************");

// HashMap implementation details

Map hMap = new HashMap();

hMap.put("FIRST", "1");

hMap.put("SECOND", "2");

hMap.put("THIRD", "3");

hMap.put("FOURTH", "4");

hMap.put("FIFTH", "5");

hMap.put("SIXTH", "6");

System.out.println("HashMap before iteration : " + hMap);

Iterator hashMapIterator = hMap.keySet().iterator();

while (hashMapIterator.hasNext()) {

String key = hashMapIterator.next();

if (key.equals("FOURTH"))

hMap.put(key + "-SHIVAM", "I AM NEW KEY IN HMAP");

}

System.out.println("HashMap after iteration : " + hMap);

}

Result:-

ConcurrentHashMap before iteration : {THIRD=3, FIRST=1, SIXTH=6, FOURTH=4, FIFTH=5, SECOND=2}

ConcurrentHashMap after iteration : {THIRD=3, FIRST=1, SIXTH=6, FOURTH-GAURAV=I AM NEW KEY IN CCHMAP, FOURTH=4, FIFTH=5, SECOND=2}

**************************************

HashMap before iteration : {FIFTH=5, THIRD=3, FOURTH=4, SECOND=2, SIXTH=6, FIRST=1}

Exception in thread "main" java.util.ConcurrentModificationException

at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793)

at java.util.HashMap$KeyIterator.next(HashMap.java:828)

at com.gaurav.collection.ConcurrentHashMapTest.main(ConcurrentHashMapTest.java:43)

ConcurrentHashMap advantages summary

ConcurrentHashMap allows concurrent read and thread-safe update operation. All operations of ConcurrentHashMap are thread-safe.

With update operation, ConcurrentHashMap only lock a specific part of Map instead of whole Map.

Concurrent update is achieved by internally dividing Map into small segments which is defined using concurrency level.

Iterator returned by ConcurrentHashMap is fail safe and never throw ConcurrentModificationException.

ConcurrentHashMap doesn’t allow null as key or value.