Tech Master Tutorials
Email Facebook Google LinkedIn Pinterest Twitter
Home Java Java 8 Java Interview Questions Java Programming

ConcurrentHashMap

ConcurrentHashMap implements the same functional specification as Hashtable/SynchronizedHashMap but it does not lock the whole hash table for read or update operations. ConcurrentHashMap maintains a hashtable that supports full concurrency of retrievals and high expected concurrency for updates.

Internal Implementation details of ConcurrentHashMap:

Hashtable has all the synchronized methods which results in locking of the table for other operations. But ConcurrentHashMap does not lock the whole table but only a certain part of the hash table and that only is locked for updates not for read/retrieval operations. And this way ConcurrentHashMap supports full concurrency for the read/retrieval operations. Even for updates operations, CoincurrentHashMap does not lock the complete table but only a part of the hash table. This way it provides high expected concurreny for update operations. Retrieval operations generally do not block, so may overlap with update operations. Retrievals reflect the results of the most recently completed update operations holding upon their onset. An update operation for a given key bears a happens-before relation with any retrieval for that key reporting the updated value.



Why ConcurrentHashMap :
A Map implementation class that provides the capability to support multiple threads concurrently. ConcurrentHashMap supports concurrent read and update operations.
ConcurrentHashMap supports full concurrency for the read/retrieval operations.
ConcurrentHashMap provides high expected concurreny for update operations. Update operation blocks a particular portion of the internal hash table.

Important ConcurrentHashMap Parameters :

Load factor is is a measure of how full the hash table is allowed to get before its capacity is automatically increased. Default load factor for concurrentHashMap is 0.75.

private static final float LOAD_FACTOR = 0.75f;

The default initial table capacity of a concurrentHashMap is 16 that is represented by the below field.

private static final int DEFAULT_CAPACITY = 16;
The two parameters that affect the performance of HashMap are – initial capacity and load factor. Initial capacity is the initial size of the hash table and load factor is is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Below default constructor of the ConcurrentHashMap creates a new, empty map with the default initial table size (16).
   public ConcurrentHashMap() {
    }


Using the below ConcurrentHashMap constructor, initialCapacity and loadFactor can be passed by a programmer.
   
    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }
Using the initial capacity and load factor, threshold is calculated.
Threshold is the size limit after which table is resized/rehashed. The value of the threshold is (int)(capacity * loadFactor).)

Below Hashtable constructor passes an ecxtra parameter other than the initialCapacity and loadFactor that is concurrency level. The field concurrencyLevel, provides the estimated number of concurrently updating threads. The implementation may use this value as a sizing hint.
    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

0.75 load factor approximately corresponds to the rough average of maintaining 2 bins/entries per index bucket in the hashtable.

Resizing/Expanding the hash ConcurrentHashMap :

load factor is is a measure of how full the hash table is allowed to get before its capacity is automatically increased. Default load factor for concurrentHashMap is 0.75.

private static final float LOAD_FACTOR = 0.75f;
The two parameters that affect the performance of HashMap are – initial capacity and load factor. Initial capacity is the initial size of the hash table and load factor is is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Constructors :

Default constructor which creates a new instance of ConcurrentHashMap with an empty map. Since we are not passing any parameter it takes the default values.

    public ConcurrentHashMap() {
    }


Constructor which lets you pass the initial capacity as a parameter, empty map with an initial table size.
Provides an opportunity to set the initialCapacity such that the need to resize the table can be avoided for good by accommodating the specified number of elements without the need to dynamically resize.
    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }


Below constructor, allows to set initial capacity and also load factor.
    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }




Adding key-value pair to ConcurrentHashMap using put() method :
To add a key-value pair to the ConcurrentHashMap, we pass key-value pair arguments to the put() method, which maps the specified key to the specified value in this table. Neither the key nor the value can be null.
ConcurrentHashMap throws NullPointerException if the specified key or value is null

 
    public V put(K key, V value) {
        return putVal(key, value, false);
    }

Here we pass the key - K var1 and value – V var2.

The put() method calls putVal() method internally.
putVal() takes the three arguments : key, value and onlyIfAbsent(boolean).

putVal() first check for the HashMap table and if the table is null or empty then calls the resize() method. putVal method :

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }



putVal method receives the key and value mapping along with the onlyIfAbsent flag.
If onlyIfAbsent flag is true then it allows to add the mapping only if there is no mapping available with the passed key to the method.
ConcurrentHashMap does not allow any null either key or value.
if (key == null || value == null) 
	throw new NullPointerException();

If key and value are valid then it generates the hash code for the mapping. Then checks for the hash table, if table is null then table is initialized with the defined capacity.
Then using hash code the bin/bucket is identified to be inserted and if bucket is empty then a new mapping is added to the bucket. If bucket is not empty then a lock is acquired for that bucket.
Traversal is made in the identified bucket to find the key mapping if available and if key is available then if onlyIfAbsent is false then the value is overwritten with the passed value and the old value is returned. If there is no mapping with the given key then a new kay-value mapping is added.