Tuesday 21 July 2015

Internal working of ConcurrentHashMap

Internal working of ConcurrentHashMap

ConcurrentHashMap utilizes the same principles of HashMap, but is designed primarily for a multi-threaded application and hence it does not require explicit synchronization. The only thread safe collection objects were Hashtable and synchronized Map prior to JDK 5.

Why need ConcurrentHashMap when already have Hashtable?

Hashtable provides concurrent access to the Map.Entries objects by locking the entire map to perform any sort of operation (update, delete, read, create).

Suppose we have a web application, the overhead created by Hashtable (locking the entire map) can be ignored under normal load. But under heavy load, the overhead of locking the entire map may prove fatal and may lead to delay response .

This is where ConcurrentHashMap comes to rescue. ConcurrentHashMap class is fully interoperable with Hashtable in programs that rely on its thread safety but not on its synchronization details.

So the main purpose of this class is to provide the same functionality as of Hashtable but with a performance comparable to HashMap.

How ConcurrentHashMap works in Java?

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

initialCapacity - The implementation performs internal sizing to accommodate this many elements.
concurrencyLevel - The estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads.

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

ConcurrentHashMap maintains a list of 16 locks by default (number of locks equal to the initial capacity, which is by default 16) each of which is used to lock on a single bucket of the Map.

This indicates that 16 can modify the collection at the same time, given, each thread works on different bucket.

So unlike hashtable, we perform any sort of operation (update, delete, read, create) without locking on entire map in ConcurrentHashMap.

Retrieval operations (including get) generally do not block so may overlap with update operations (including put and remove).

The allowed concurrency among update operations is guided by the optional concurrencyLevel constructor argument (default 16), which is used as a hint for internal sizing. Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table. Using a significantly higher value than you need, can waste space and time, and a significantly lower value can lead to thread contention

Can two threads update the ConcurrentHashMap simultaneously?
Yes, because default implementation allows 16 threads to read and write in parallel.

But in the worst case scenario, when two objects lie in the same segment or same partition, then parallel write would not be possible.

Why ConcurrentHashMap does not allow null keys and null values?

The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs. the key isn't mapped.

In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

The code is like this:

if (map.containsKey(k)) {
      return map.get(k);
} else {
      throw new KeyNotPresentException();
}


It might be possible that key k might be deleted in between the get(k) and containsKey(k) calls. As a result, the code will return null as opposed to KeyNotPresentException (Expected Result if key is not present).

What is the difference between HashMap and ConcurrentHashMap?

The HashMap was not thread safe and therefore could not be utilized in multi-threaded applications.

The ConcurrentHashMap was introduced to overcome this shortcoming and also as an alternative to using HashTable and synchronized Maps for greater performance and uses the standard Hashing algorithms to generate hash code for storing the key value pairs.

Can multiple threads read from the Hashtable concurrently?

No, multiple threads cannot read simultaneously from Hashtable.
Reason, the get() method of Hashtable is synchronized. As a result, at a time only one thread can access the get() method.

It is possible to achieve full concurrency for reads (all the threads read at the same time) in ConcurrentHashMap by using volatile keyword.

Does ConcurrentHashMap Iterator behave like fail fast iterator or fail safe Iterator?

ConcurrentHashMap iterator behaves like fail safe iterator. It will not throw ConcurrentModificationException.

Why does Java provide default value of partition count as 16 instead of very high value?

Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table.
Using a significantly higher value than you need, can waste space and time, and a significantly lower value can lead to thread contention.

Can you write the simple example which proves ConcurrentHashMap class behaves like fail safe iterator?



import java.util.concurrent.ConcurrentHashMap;
import java.util.Iterator;
public class ConcurrentHashMapExample {
      public static void main(String[] args) {
            ConcurrentHashMap<String,String> failSafe =
                             new ConcurrentHashMap<String,String>();
            failSafe.put("A", "Apple");
            failSafe.put("B", "Bat");
            failSafe.put("C","Cat");

            Iterator iterator = failSafe.keySet().iterator();

            while (iterator.hasNext()) {
                  System.out.println(failSafe.get(iterator.next()));
                  failSafe.put("D", "Dog");
            }
      }
}
Output:
      Apple
      Bat
      Cat

3 comments:

  1. package com.collection;

    import java.util.Iterator;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.Set;
    import java.util.concurrent.ConcurrentHashMap;

    public class ConcurrentMapExp {

    public static void main(String[] args) {
    Map concurrentMap = new ConcurrentHashMap();
    concurrentMap.put("key", "value");
    Set> entrySet = concurrentMap.entrySet();
    Iterator> iterator = entrySet.iterator();

    while(iterator.hasNext()) {
    System.out.println(iterator.next());
    iterator.remove(); // no exception here. bcoz bucket level locking
    }
    }
    }

    Output:
    key=value

    ReplyDelete
  2. Here (Aa, BB) and (AaAa, BBBB) has same hashcode.
    ConcurrentHashMap works of bucket level locking,
    It will add ("BBBB", "Bat bat") pair while iteration.
    And will modify the iterator and no exception.


    package com.collection;

    import java.util.concurrent.ConcurrentHashMap;
    import java.util.Iterator;


    public class ConcurrentHashMapExample {
    public static void main(String[] args) {
    ConcurrentHashMap failSafe=new ConcurrentHashMap();
    failSafe.put("Aa", "Apple");
    failSafe.put("BB", "Bat");
    failSafe.put("AaAa","Apple Apple");

    Iterator iterator = failSafe.keySet().iterator();

    while (iterator.hasNext()) {
    System.out.println(failSafe.get(iterator.next()));
    failSafe.put("BBBB", "Bat bat");
    }
    }
    }

    output:

    Bat
    Apple
    Bat bat
    Apple Apple

    ReplyDelete
  3. Output should also include Dog as CHM iterator is fail-safe iterator.

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...