How ConcurrentHashMap Works Internally in Java | Code Factory


Index Page : Link

Donate : Link

Medium Link : Link

Applications : Link

The ConcurrentHashMap class is introduced in JDK 1.5 belongs to java.util.concurrent package, which implements ConcurrentMap as well as to Serializable interface also. ConcurrentHashMap is an enhancement of HashMap as we know that while dealing with Threads in our application HashMap is not a good choice because performance-wise HashMap is not up to the mark.

Key points of ConcurrentHashMap:

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

The Hierarchy of ConcurrentHashMap:

Before talking in detail let us review a few concepts below:

  • ConcurrentHashMap: It allows concurrent access to the map. Part of the map called Segment (internal data structure) is only getting locked while adding or updating the map. So ConcurrentHashMap allows concurrent threads to read the value without locking at all. This data structure was introduced to improve performance.
  • Concurrency-Level: It is the number of threads concurrently updating the map. The implementation performs internal sizing to try to accommodate this many threads.
  • Load-Factor: It’s a threshold, used to control resizing.
  • Initial Capacity: Accommodation of a certain number of elements initially provided by the implementation. if the capacity of this map is 10. It means that it can store 10 entries.

A ConcurrentHashMap is divided into number of segments, and the example which I am explaining here used default as 32 on initialization.

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.

The 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];
}

Here, threshold is getting initialized for re-sizing purpose.

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 
   
Since it’s all about concurrency, we need synchronized block on the above Segment as below:

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);

Now let us understand how this works internally. The method remove (Object key) internally calls remove (Object key, Object value) where it passed ‘null’ as a value. Since we are going to remove an element from a Segment, we need a lock on the that Segment.

Object remove(Object key, Object value) {

  Segment seg = segments[(hash & 0x1F)]; //hash we have calculated for key

  synchronized (seg) {
    Entry[] tab = this.table; //table is Entry[] table    
    int index = hash & tab.length - 1; //calculating index with help of hash
    Entry first = tab[index]; //Getting the Entry Object

    Entry e = first;
    while(true) {
      if ((e.hash == hash) && (eq(key, e.key))) {
        break;
      }
      e = e.next;
    }
    Object oldValue = e.value;
    Entry head = e.next;
    for (Entry p = first; p != e; p = p.next) {
      head = new Entry(p.hash, p.key, p.value, head);
    }
    table[index] = head;
    seg.count -= 1;
  }
  return oldValue;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s