How ConcurrentHashMap Works Internally

Question- How ConcurrentHashMap Works Internally in java?

public class ConcurrentHashMap<K,V>
extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable

All Implemented Interfaces:
Serializable, ConcurrentMap<K,V>, Map<K,V>

public interface ConcurrentMap<K,V>
extends Map<K,V>

All Known Implementing Classes:
ConcurrentHashMap, ConcurrentSkipListMap

Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values

Internally ConcurrentHashMap has been divided into 16 segments. As mention in below image

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

/**
     * The maximum capacity, used if a higher value is implicitly
     * specified by either of the constructors with arguments.  MUST
     * be a power of two <= 1<<30 to ensure that entries are indexable
     * using ints.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The minimum capacity for per-segment tables.  Must be a power
     * of two, at least two to avoid immediate resizing on next use
     * after lazy construction.
     */
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

/**
     * The maximum number of segments to allow; used to bound
     * constructor arguments. Must be power of two less than 1 << 24.
     */
    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

• ConcurrentHashMap class is introduced in JDK 1.5 belongs to java.util.concurrent package.
• ConcurrentHashMap based on hashing but its performance is improved by using locking strategy. Unlike HashTable or Synchronized.
• ConcurrentHashMap internally divides buckets into segments and each segment has been locked by a thread for writing purpose.
• ConcurrentHashMap use re-entrant lock mechanism for locking segment.
• Segment is locked while adding or updating the map only.
• ConcurrentHashMap allows concurrent threads to read the value without locking.This mechanism was introduced to improve performance.
• ConcurrentHashMap class provide thread-safety by dividing the map into segments, the lock is required not on entire concurrentHashMap object but for one segment, i.e one thread requires a lock of one segment.
• By default ConcurrentHashMap has 16 buckets and segments that means The default concurrency-level of ConcurrentHashMap is 16.
• The internal structure of ConcurrentHashMap is different in Java 8  versions to improve the performance. Instead of an Entry there is a Node class. The major difference is that for a given segment if the Node size increases significantly.  To optimize the performance it changes the structure from a linkedlist to a TreeNode. The TreeNode uses red black tree which is a balancing tree and making sure that operations on the tree is in the order of lg(n)

To Insert Element in ConcurrentHashMap, First it calculate hash of key as below.

int hashVal = hash(key);

private static int hash(int h) {
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

After get the hashVal it calculate the Segment as below:

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

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 
}

Difference between SynchronizedHashMap and ConcurrentHashMap

SynchronizedHashMap	ConcurrentHashMap
By using Synchronization on Hasap, it is Object level locking	Synchronization is at segment level.
ConcurrentModification Exception is thrown if a thread tries to modify an existing SynchronizedMap which is being iterated	ConcurrentModification Exception is thrown if a thread tries to modify an existing ConcurrentHashMap which is being iterated
Only a single Thread can modify the HashMap and block other threads the performance is bad compare to ConcurrentHashMap.	Multiple Threads can modify ConcurrentHashMap on different segment at same time. Hence performance is much better.
By using Synchronization on Hasap, A lock is obtained for read/write operation at object level	Lock is obtained for write/Update operation at segment level.

Q-How ConcurrentHashMap is fail safe?
Q-When should we use ConcurrentHashMap?
Q-How is ConcurrentHashMap thread safe?
Q-Why do we need ConcurrentHashMap?
Q-What is difference between fail fast and fail safe?
Q-Can ConcurrentHashMap throws ConcurrentModificationException?
Q-Does ConcurrentHashMap allow null?
Q-Why is null not allowed in ConcurrentHashMap?
Q-What is the difference between synchronized HashMap and ConcurrentHashMap?
Q-How do you prevent concurrent modification exception?

Related Tutorials 

• Java Collections Interview
• List Interface In Java
• ArrayList
• LinkedList
• Custom Own ArrayList Implementation
• Custom LinkedList implementation in java
• Set Interface In Java
• Map Interface In Java
• HashMap
• TreeMap
• HashMap Vs ConcurrentHashMap
• HashMap Vs HashTable In Java
• HashMap Vs HashSet In Java
• HashMap Vs TreeMap In Java
• HashMap vs LinkedHashMap In Java
• TreeSet Vs TreeMap In Java
• SortedSet Vs TreeSet In Java
• SortedMap Vs TreeMap In Java
• Array Vs ArrayList In Java
• ArrayList Vs LinkedList In Java
• How HashSet Works Internally
• How TreeMap Works Internally
• How HashMap Works Internally
• How ConcurrentHashMap Works Internally
• How To Detect Loop In A LinkedList In Java
• Detect And Remove Loop In A LinkedList