ConcurrentHashMap vs Hashtable vs synchronizedMap

ConcurrentHashMap is what you should reach for whenever a map is shared between threads, and the interview question is almost always "how is it different from Hashtable and from Collections.synchronizedMap?" The answer is about lock granularity, and it has changed once.

Three ways to share a map#

Hashtable is a Java 1.0 class kept for compatibility; every method is synchronized, including get. There is no reason to use it in new code.

Collections.synchronizedMap(new HashMap<>()) wraps each method in a synchronized block on a shared mutex. It is marginally more flexible — you choose the underlying map — and has exactly the same throughput problem. Worse, it has a trap:

Map<String, Integer> m = Collections.synchronizedMap(new HashMap<>());
 
// Each call is atomic. The SEQUENCE is not — two threads can both read absent
// and both write, losing one increment.
if (!m.containsKey(k)) {
    m.put(k, 1);
}
 
// Iteration is not synchronised at all. The javadoc requires this:
synchronized (m) {
    for (String key : m.keySet()) { ... }
}

That second point catches people out constantly: synchronizedMap synchronises the methods, not the iterator, so iterating without an explicit synchronized block on the map risks ConcurrentModificationException.

How ConcurrentHashMap works#

Three mechanisms combine:

Compare-and-swap for empty bins. Most bins in a well-distributed map are empty or hold one entry. Inserting into an empty bin is a single atomic CPU instruction with no lock acquisition, no contention and no blocking.

Per-bin locking for occupied bins. When a bin already has a head node, the writer synchronises on that node object. Two threads writing to different bins never interact. With a 1024-slot table you effectively have 1024 independent locks, which is why concurrency scales with the map rather than being capped.

Volatile reads. Node.val and Node.next are volatile, so a reader always sees a consistent, recently written value without acquiring anything. Reads never block, never contend, and never prevent a writer from proceeding.

Java 7's design was different: the map was split into 16 (configurable) Segment objects, each a small independent hash table with its own ReentrantLock. The concurrencyLevel constructor parameter set that number, and it was a hard ceiling on write parallelism. Java 8 deleted the whole mechanism; the constructor parameter still exists and is now only a sizing hint.

The atomic operations#

This is the part that matters most in day-to-day code, and it is what synchronizedMap cannot give you.

ConcurrentHashMap<String, AtomicLong> counters = new ConcurrentHashMap<>();
 
// Insert only if absent — atomic, returns the existing value if there was one.
counters.putIfAbsent(key, new AtomicLong());
 
// Compute the value only if absent. The function runs at most once per key
// even under contention, which putIfAbsent cannot promise (it constructs
// the value eagerly, then throws it away on a race).
counters.computeIfAbsent(key, k -> new AtomicLong()).incrementAndGet();
 
// Read-modify-write in one atomic step.
ConcurrentHashMap<String, Long> totals = new ConcurrentHashMap<>();
totals.merge(key, 1L, Long::sum);
 
// Conditional replace — the CAS of the map world.
totals.replace(key, expectedOld, newValue);
 
// Remove only if the value matches.
totals.remove(key, expectedValue);

computeIfAbsent versus putIfAbsent is a good interview distinction. putIfAbsent(k, new Expensive()) constructs the value before the call regardless — the same evaluation trap as Optional.orElse. computeIfAbsent defers construction and guarantees the function runs at most once for a given key.

The same rule applies to compute, merge and forEach with a mutating action. Long-running work inside any of them blocks every other writer to that bin.

Weakly consistent iteration#

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(...);
 
for (Map.Entry<String, Integer> e : map.entrySet()) {
    map.put("new-" + e.getKey(), 0);   // legal — no ConcurrentModificationException
}

A ConcurrentHashMap iterator reflects the state of the map at some point at or after creation. It never throws ConcurrentModificationException, will traverse each element at most once, and may or may not observe modifications made after it started.

That is a genuinely different contract from HashMap's fail-fast iterator, and both are defensible: fail-fast catches a programming error in single-threaded code, while weak consistency is the only thing that can be offered without locking the whole map for the duration of a traversal. The cost is that you cannot iterate a ConcurrentHashMap and assume a coherent view — computing a total by iterating may include entries added mid-traversal and miss others.

size(), and why it lies#

The map does not keep one counter, because a single shared counter would be the contention point the whole design exists to avoid. Instead it uses striped counters — an array of cells, each updated by a different thread, summed on demand. That is the same technique as LongAdder.

size() returns an int and is documented as an estimate. mappingCount() returns a long and is the preferred method — the map can genuinely hold more than Integer.MAX_VALUE entries.

In practice the distinction rarely matters, because in a concurrent map any size is out of date the moment it is returned. Code that reads size() and then acts on it is racy regardless of accuracy.

Bulk parallel operations#

Java 8 added parallel bulk methods that use the common ForkJoinPool:

// The first argument is a parallelism threshold: below this many elements,
// run sequentially. Long.MAX_VALUE means "always sequential".
map.forEach(1000, (k, v) -> process(k, v));
 
String found = map.search(1000, (k, v) -> v.isExpired() ? k : null);
 
long total = map.reduceValues(1000, Order::amount, 0L, Long::sum);

They are rarely the right tool — the same caveats as parallel streams apply, plus the risk of running application code while holding bin locks — but knowing they exist, and that the first parameter is a parallelism threshold rather than a thread count, is a good detail to have.

What gets asked#

"How does ConcurrentHashMap achieve thread safety without locking the whole map?" is the core question, and the complete answer is: CAS for empty bins, synchronise on the bin's head node otherwise, volatile reads so readers never block. Then: what changed in Java 8 (segments removed); why nulls are disallowed (ambiguity between absent and null); and why you would choose it over synchronizedMap (throughput, plus atomic compound operations). If you can add the computeIfAbsent recursion hazard unprompted, the question is usually over.