How Concurrenthashmap works – Its internal implementation

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
 }

Now lets see how put() method works.
It will 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 
}

The above flow is similar to the way hashmap works. You can read about it here

How hashmap works internally

The above Concurrenthashmap implementation is based on Java 7. In Java 7 it has changed and the file size has doubled. Once I understand the flow I will come up with a blog 🙂

Mar Java Mit Java 🙂

Uday Ogra

Connect with me at http://facebook.com/tendulkarogra and lets have some healthy discussion :)

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *