ConcurrentHashMap internal architecture

what is internal architecture of concurenthash map?

• The underlined data structure for ConcurrentHashMap is Hashtable.
• ConcurrentHashMap class is thread-safe i.e. multiple thread can operate on a single object without any complications.
• At a time any number of threads are applicable for read operation without locking the ConcurrentHashMap object which is not there in HashMap.
• In ConcurrentHashMap, the Object is divided into number of segments according to the concurrency level.
• Default concurrency-level of ConcurrentHashMap is 16.
• In ConcurrentHashMap, at a time any number of threads can perform retrieval operation but for updation in object, thread must lock the particular segment in which thread want to operate.This type of locking mechanism is known as Segment locking or bucket locking.Hence at a time 16 updation operations can be performed by threads.
• null insertion is not possible in ConcurrentHashMap as key or value.

A ConcurrentHashMap has internal final class called Segment so we can say that ConcurrentHashMap is internally divided in segments of size 32, so at max 32 threads can work at a time.

It means each thread can work on a each segment during high concurrency and atmost 32 threads can operate at max which simply maintains 32 locks to guard each bucket of the ConcurrentHashMap.

he definition of Segment is as below:

/** Inner Segment class plays a significant role **/

protected static final class Segment {

  protected int count;

  protected synchronized int getCount() {

    return this.count;

  }

  protected synchronized void synch() {}

}

/** Segment Array declaration **/

public final Segment[] segments = new Segment[32];

As we all know that Map is a kind of data structure which stores data in key-value pair which is array of inner class Entry, see as below:














 static class Entry implements Map.Entry {      






   protected final Object key;






   protected volatile Object value;






   protected final int hash;






   protected final Entry next;













   Entry(int hash, Object key, Object value, Entry next) {













     this.value = value;






     this.hash = hash;






     this.key = key;






     this.next = next;






   }













   // Code goes here like getter/setter






 }

And ConcurrentHashMap class has an array defined as below of type Entry class: 

 protected transient Entry[] table; 

This Entry array is getting initialized when we are creating an instance of ConcurrentHashMap, even using a default constructor called internally as below:

public ConcurrentHashMap(int initialCapacity, float loadFactor) {

  //Some code

  int cap = getCapacity();

  this.table = newTable(cap); // here this.table is Entry[] table

}

protected Entry[] newTable(int capacity) {

  this.threshold = ((int)(capacity * this.loadFactor / 32.0F) + 1);

  return new Entry[capacity];



}



Inserting (Put) Element in ConcurrentHashMap:

Most important thing to understand the put method of ConcurrentHashMap, that how ConcurrentHashMap works when we are adding the element. As we know put method takes two arguments both of type Object as below:

put(Object key, Object value)    



So it wil 1st calculate the hash of key as below:



int hashVal = hash(key);

static int hash(Object x) {

  int h = x.hashCode();

  return (h << 7) - h + (h >>> 9) + (h >>> 17);

}



After getting the hashVal we can decide the Segment as below:

Segment seg = segments[(hash & 0x1F)];     // segments is an array defined above 



synchronized (seg) {

  // code to add

  int index = hash & table.length - 1; // hash we have calculated for key and table is Entry[] table

  Entry first = table[index];

  for (Entry e = first; e != null; e = e.next) {

    if ((e.hash == hash) && (eq(key, e.key))) { // if key already exist means updating the value

      Object oldValue = e.value;

      e.value = value;

      return oldValue;

    }

  }

  Entry newEntry = new Entry(hash, key, value, first); // new entry, i.e. this key not exist in map

  table[index] = newEntry; // Putting the Entry object at calculated Index 



}



Size of ConcurrentHashMap

Now when we are asking for size() of the ConcurrentHashMap the size comes out as below:

for (int i = 0; i < this.segments.length; i++) {

  c += this.segments[i].getCount();         //here c is an integer initialized with zero

}



Getting (get) Element From ConcurrentHashMap

When we are getting an element from ConcurrentHashMap we are simply passing key and hash of key is getting calculated. The defintion goes something like as below:




public Object get(Object key){

  //some  code here

  int index = hash & table.length - 1;  //hash we have calculated for key and calculating index with help of hash

  Entry first = table[index];          //table is Entry[] table

  for (Entry e = first; e != null; e = e.next) {

    if ((e.hash == hash) && (eq(key, e.key))) {

      Object value = e.value;

      if (value == null) {

        break;

      }

      return value;

    }

  }

  //some  code here

}





Note: No need to put any lock when getting the element from ConcurrentHashMap.

Removing Element From ConcurrentHashMap

Now question is how remove works with ConcurrentHashMap, so let us understand it. Remove basically takes one argument 'Key' as an argument or takes two argument 'Key' and 'Value' as below:












Object remove(Object key);













boolean remove(Object key, Object value);