Wednesday, April 3, 2019

ConcurrentHashMap in Java

ConcurrentHashMap in Java is introduced as another thread-safe alternative for Hashtable (or explicitly synchronizing the map using synchronizedMap method) from Java 5. ConcurrentHashMap class extends AbstractMap class and implements ConcurrentMap interface through which it provides thread safety and atomicity guarantees.

Why another Map

First thing that comes to mind is why another map when we already have a HashMap or HashTable.

If you need to use a Map like structure with in multi-threaded environment with thread safety you can use a Hashtable or a synchronized HashMap by using Collections.synchronizedMap() method. Then what unique does ConcurrentHashMap in Java offer?

Problem with Hashtable or synchronized Map is that all its methods are synchronized on a common lock thus only a single thread can access it at any given time, even for read operations. ConcurrentHashMap in Java tries to address these issues.

ConcurrentHashMap tries to provide better performance though still providing a thread safe alternative. So it can be said that ConcurrentHashMap is a HashMap whose operations are threadsafe.


How performance is improved in ConcurrentHashMap

ConcurrentHashMap in Java is also a hash based map like HashMap, how it differs is the locking strategy used by ConcurrentHashMap. Unlike HashTable (or synchronized HashMap) it doesn't synchronize every method on a common lock. ConcurrentHashMap in Java uses separate lock for separate buckets thus locking only a portion of the Map.

If you have idea about the internal implementation of the HashMap you must be knowing that by default there are 16 buckets. Same concept is used in ConcurrentHashMap and by default there are 16 buckets and also separate locks for separate buckets. So the default concurrency level is 16.

Since there are 16 buckets having separate locks of their own which effectively means at any given time 16 threads can operate on the map concurrently, provided all these threads are operating on separate buckets.

So you see how ConcurrentHashMap provides better performance by locking only the portion of the map rather than blocking the whole map resulting in greater shared access.

For locking any of the bucket independently of the other buckets the first node in the bucket is locked by using synchronized keyword. Note that before Java 8, implementation of Java ConcurrentHashMap used to have Segment array with with each segment having its own lock which has been changed from Java 8. Now the first node in the bucket itself is locked using the node's own builtin synchronized monitors.

ConcurrentHashMap Internal implementation in Java
ConcurrentHashMap implementation in Java

Further performance improvement in ConcurrentHashMap

Performance of Java ConcurrentHashMap is further improved by providing read access concurrently without any blocking. Retrieval operations (including get) generally do not block, so may overlap with update operations (including put and remove). Retrievals reflect the results of the most recently completed update operations which may mean that retrieval operations may not fetch the current/in-progress value (Which is one drawback). Memory visibility for the read operations is ensured by volatile reads. You can see in the ConcurrentHashMap code that the val and next fields of Node are volatile.

Also for aggregate operations such as putAll and clear which works on the whole map, concurrent retrievals may reflect insertion or removal of only some entries (another drawback of separate locking). Because read operations are not blocking but some of the writes (which are on the same bucket) may still be blocking.

Constructors in Java ConcurrentHashMap

There are five constructors in the ConcurrentHashMap class-

  • ConcurrentHashMap()- Creates a new, empty map with the default initial table size (16).
  • ConcurrentHashMap(int initialCapacity)- Creates a new, empty map with an initial table size accommodating the specified number of elements without the need to dynamically resize.
  • ConcurrentHashMap(int initialCapacity, float loadFactor)- Creates a new, empty map with an initial table size based on the given number of elements (initialCapacity) and initial table density (loadFactor).
  • ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)- Creates a new, empty map with an initial table size based on the given number of elements (initialCapacity), table density (loadFactor), and number of concurrently updating threads (concurrencyLevel).
  • ConcurrentHashMap​(Map<? extends K,? extends V> m)- Creates a new map with the same mappings as the given map.

Java ConcurrentHashMap example

At this juncture let's see a simple example of ConcurrentHashMap in Java. In this example a ConcurrentHashMap is created and (key, value) pairs are added to it. Then getting the collection view of the Map it is iterated to display the stored keys and values.

public class CHMDemo {

    public static void main(String[] args) {
        // Creating ConcurrentHashMap
        Map<String, String> cityTemperatureMap = new ConcurrentHashMap<String, String>();
        
        // Storing elements
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        //cityTemperatureMap.put(null, "26");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        
        for (Map.Entry<String, String> e : cityTemperatureMap.entrySet()) {
            System.out.println(e.getKey() + " = " + e.getValue());
        }
    }
}

Null is not allowed in ConcurrentHashMap

Though HashMap allows one null as key but ConcurrentHashMap in Java doesn't allow null as key. In the previous example you can uncomment the line which has null key. While trying to execute the program it will throw null pointer exception.

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class CHMDemo {

 public static void main(String[] args) {
        // Creating ConcurrentHashMap
        Map cityTemperatureMap = new ConcurrentHashMap();
        
        // Storing elements
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        // Adding null key
        cityTemperatureMap.put(null, "26");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        
        for (Map.Entry e : cityTemperatureMap.entrySet()) {
            System.out.println(e.getKey() + " = " + e.getValue());
        }
    }
}
Exception in thread "main" java.lang.NullPointerException
 at java.util.concurrent.ConcurrentHashMap.putVal(ConcurrentHashMap.java:1011)
 at java.util.concurrent.ConcurrentHashMap.put(ConcurrentHashMap.java:1006)
 at org.netjs.prog.CHMDemo.main(CHMDemo.java:16)

Atomic operations in ConcurrentHashMap

ConcurrentHashMap in Java provides a lot of atomic methods, let's see it with an example how these atomic methods help. Note that from Java 8 many new atomic methods are added.

Suppose you have a word Map that counts the frequency of every word where key is the word and count is the value, in a multi-threaded environment, even if ConcurrentHashMap is used, there may be a problem as described in the code snippet.

public class CHMAtomicDemo {

    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> wordMap = new ConcurrentHashMap<>();
        ..
        ..
        // Suppose one thread is interrupted after this line and 
        // another thread starts execution
        Integer prevValue = wordMap.get(word); 
        
        Integer newValue = (prevValue == null ? 1 : prevValue + 1);
        // Here the value may not be correct after the execution of 
        // both threads
        wordMap.put(word, newValue);  

    }

}

To avoid these kind of problems you can use atomic method, one of the atomic method is compute which can be used here.

wordMap.compute(word, (k,v)-> v == null ? 1 : v + 1);

If you see the general structure of the Compute method

compute(K key, BiFunction<? super K,? super V,? extendsV> remappingFunction)
Here BiFunction functional interface is used which can be implemented as a lambda expression.

So here rather than having these lines-

Integer prevValue = wordMap.get(word); 
Integer newValue = (prevValue == null ? 1 : prevValue + 1);
wordMap.put(word, newValue);
you can have only this line
wordMap.compute(word, (k,v)-> v == null ? 1 : v + 1);

The entire method invocation is performed atomically. Some attempted update operations on this map by other threads may be blocked while computation is in progress.

There are several other atomic operations like computeIfAbsent, computeIfPresent, merge, putIfAbsent.

Fail-safe iterator in ConcurrentHashMap

Iterator returned by the ConcurrentHashMap is fail-safe which means it will not throw ConcurrentModificationException. It can be seen in the example code where a new (key, value) pair is added while the map is iterated, still it doesn't throw ConcurrentModificationException.

public class CHMDemo {

    public static void main(String[] args) {
        // Creating ConcurrentHashMap
        Map<String, String> cityTemperatureMap = new ConcurrentHashMap<String, String>();
        
        // Storing elements
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        
        Iterator<String> iterator = cityTemperatureMap.keySet().iterator();   
        while (iterator.hasNext()){
            System.out.println(cityTemperatureMap.get(iterator.next()));
            // adding new value, it won't throw error
            cityTemperatureMap.put("Kolkata", "34");
            
        }
    }
}

Output

24
35
34
32
22

According to the JavaDocs- The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

When is ConcurrentHashMap a better choice

ConcurrentHashMap is a better choice when there are more reads than writes. As mentioned above retrieval operations are non-blocking so many concurrent threads can read without any performance problem. If there are more writes and that too many threads operating on the same segment then the threads will block which will deteriorate the performance.

Points to note

  • ConcurrentHashMap in Java is also a hash based map like HashMap, but ConcurrentHashMap is thread safe.
  • In ConcurrentHashMap thread safety is ensured by having separate locks for separate buckets, resulting in better performance.
  • In ConcurrentHashMap class, by default the bucket size is 16 and the concurrency level is also 16.
  • Null keys are not allowed in Java ConcurrentHashMap.
  • Iterator provided by the ConcurrentHashMap is fail-safe, which means it will not throw ConcurrentModificationException.
  • Retrieval operations (like get) don't block so may overlap with update operations (including put and remove).

Recommendations for learning

  1. Java Programming Masterclass Course
  2. Java In-Depth: Become a Complete Java Engineer!
  3. Spring Framework Master Class Course
  4. Complete Python Bootcamp Course
  5. Python for Data Science and Machine Learning

That's all for this topic ConcurrentHashMap in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Difference between HashMap and ConcurrentHashMap in Java
  2. CopyOnWriteArrayList in Java
  3. How HashMap internally works in Java
  4. CountDownLatch in Java concurrency
  5. Java Concurrency Interview Questions

You may also like-

  1. How to iterate a Hash map of arraylists of String in Java?
  2. How to sort HashSet in Java
  3. Difference Between Comparable and Comparator in Java
  4. Try-With-Resources in Java Exception Handling
  5. static reference to the non-static method or field error
  6. Race Condition in Java Multi-Threading
  7. interface default methods in Java 8
  8. ThreadLocal class in Java