Concurrent Hash Map internal working

Created on: Sep 12, 2024

Concurrent collections are essential in Java for applications that require high performance, scalability, and thread safety. They allow multiple threads to access and modify shared data structures simultaneously without causing race conditions or deadlocks.

ConcurrentHashMap is a enhancement of HashMap which supports concurrent retrieval and updates. It’s used in a multi-threaded environment to avoid ConcurrentModificationException.

Let's consider a example using simple hashmap.

public class ConcurrentHashMapDemo {
    public static void main(String[] args) {

        Map<String, Integer> map = new HashMap<>();
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);

        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();

        while (iterator.hasNext()) {
            Map.Entry<String, Integer> entry = iterator.next();
            map.put("D", 4);
        }
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1511)
	at java.base/java.util.HashMap$EntryIterator.next(HashMap.java:1544)
	at java.base/java.util.HashMap$EntryIterator.next(HashMap.java:1542)
	at org.learning.collection.ConcurrentHashMapDemo.main(ConcurrentHashMapDemo.java:20)

You can see that, above code will throw ConcurrentModificationException as Hashmap is failfast. Concurrent hashmap provides the capability to work concurrently. Let's change map implementation with ConcurrentHashMap, you will not see the error.

  Map<String, Integer> map = new ConcurrentHashMap<>();

Let's take a below example, where a map is accessed from different thread concurrently. Since it is using ConcurrentHashMap, all thread can work simultaneously.

public class ConcurrentHashMapDemo {
    public static void main(String[] args) {

        Map<String, Integer> map = new ConcurrentHashMap<>();

        Runnable runnable = () -> {
            String thread = Thread.currentThread().getName();
            for(int i=0; i<10; i++) {
                map.compute(thread, (key, value) -> (value == null) ? 1 : value + 1);
                System.out.println("updated map " + map + "in thread "+ thread);
            }
        };
        Thread thread1 = new Thread(runnable, "thread-1");
        Thread thread2 = new Thread(runnable, "thread-2");

        thread1.start();
        thread2.start();

        try{
            thread1.join();
            thread2.join();
        }catch (Exception e){
            e.printStackTrace();
        }

        System.out.println("map "+map);
    }
}

updated map {thread-2=1, thread-1=1}in thread thread-1
updated map {thread-2=1, thread-1=1}in thread thread-2
updated map {thread-2=1, thread-1=2}in thread thread-1
updated map {thread-2=2, thread-1=3}in thread thread-1
updated map {thread-2=2, thread-1=4}in thread thread-1
updated map {thread-2=2, thread-1=2}in thread thread-2
updated map {thread-2=2, thread-1=5}in thread thread-1
updated map {thread-2=3, thread-1=5}in thread thread-2
updated map {thread-2=3, thread-1=6}in thread thread-1
updated map {thread-2=4, thread-1=6}in thread thread-2
updated map {thread-2=4, thread-1=7}in thread thread-1
updated map {thread-2=5, thread-1=7}in thread thread-2
updated map {thread-2=5, thread-1=8}in thread thread-1
updated map {thread-2=6, thread-1=9}in thread thread-1
updated map {thread-2=6, thread-1=10}in thread thread-1
updated map {thread-2=6, thread-1=8}in thread thread-2
updated map {thread-2=7, thread-1=10}in thread thread-2
updated map {thread-2=8, thread-1=10}in thread thread-2
updated map {thread-2=9, thread-1=10}in thread thread-2
updated map {thread-2=10, thread-1=10}in thread thread-2
map {thread-2=10, thread-1=10}

Process finished with exit code 0

Internal Working

Let's understand the internal working of ConcurrentHashMap ( say CSH). CSH never locks the whole map, it divides the map into segment and locking is done on these segment. CHM is separated into different regions(default-16) and locks are applied to them. When setting data in a particular segment, the lock for that segment is obtained.

CHM has a array of Segment ( default size = 16 ).

static class Segment<K,V> extends ReentrantLock implements Serializable {
    private static final long serialVersionUID = 2249069246763182397L;
    final float loadFactor;
    Segment(float lf) { this.loadFactor = lf; }
}
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

Segment<K,V>[] segments = (Segment<K,V>[]) new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];

When there is a write operation, a thread obtains a locks on a particular segment and call the method of Segment to do write operation. When operation is done lock is released. In the same time another thread can do lock on another segment and work parallelly.

In case of read operation, CHM itself has the real implementation.

Concurrent Hash Map internal working

Internal Working

References