How ConcurrentHashMap works

ConcurrentHashMap is designed to be more efficient and have better performance in multi-threaded enivorment when compared to hashtable. In hashtable concurrency is achieved by obtaining a lock on the entire object for performing a single operation such as put() or get().

ConcurrentHashMap 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. The allowed concurrency among update operations is guided by the optional concurrencyLevel constructor argument (default 16), which is used as a hint for internal sizing. The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table. Using a significantly higher value than you need can waste space and time, and a significantly lower value can lead to thread contention.

The internal structure of ConcurrentHashMap in Java 8 is different previous java versions. Instead of an Entry there is a Node class. The major difference is that for a given segment if the Node size increases significantly this it changes the structure from a linkedlist to a TreeNode and optimize the performance. 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)

static class Node implements Map.Entry {
	final int hash;
	final K key;
	volatile V val;
	volatile Node next;
	Node(int hash, K key, V val, Node next) {
             this.hash = hash;
             this.key = key;
             this.val = val;
    = next;

put() - By default ConcurrentHashMap maintains 16 segments. During any write/update/modify operation lock is obtained only on the particular segment allowing other threads to access other segments concurrently. It two threads want to update on the same segment then it cannot be done in parallel, since thread will acquire the lock on the particular segment so the other thread has to wait.

get() or any retrieval opertions ConcurrentHashMap generally do not block, so may overlap with update operations (including put and remove). Retrievals reflect the results of the most recently completed update operations holding upon their onset.

size() to get the size of map, iterate over all the segments and sum each segment length. Since the segments are not locked while determining the size, it may not represent the accurate size.

iterator() Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException. There is not gurantee that update of one thread will be seen by the other threads. However, iterators are designed to be used by only one thread at a time.

class TestConcurrentHashMap {
	public static void main(String[] args) {
		ConcurrentHashMap map = new ConcurrentHashMap();
		map.put(1, 1);
		map.put(2, 2);
		map.put(3, 3);
		Iterator keySet = map.keySet().iterator();
		while (keySet.hasNext()) {
			map.put(400, 4);
			map.put(100, 4);
			map.put(101, 4);
//note it doesn't display 400 value as key.