HashMap vs ConcurrentHashMap — Thread-Safety, Locking Strategies, Iteration

HashMap is not thread-safe; ConcurrentHashMap is.

HashMap hazards under concurrency

• Lost updates: two threads putting same key, one wins
• Resize race: pre-Java 8 could create infinite loops (CPU pinned at 100%)
• CME on iteration: fail-fast iterator throws if modified outside
• Unsafe even for reads during resize

ConcurrentHashMap — Java 8 redesign

Reads are lock-free

• get uses volatile reads of table and bucket
• Zero contention for reads

Writes use CAS then synchronized

• Empty bucket: CAS-insert the node (lock-free fast path)
• Occupied bucket: synchronized on the bucket's first node
• Only threads hitting the same bucket contend

Treeification

• Bucket with 8+ entries becomes red-black tree
• Worst case per-bucket: O(log n)

Incremental resize

• Multiple threads can help rehash
• Doesn't block all other operations

Pre-Java 8 CHM

• Used segment locking (16 segments, each a mini-HashMap)
• Threads hitting different segments didn't contend
• Java 8 went finer-grained: per-bucket

Null handling — a key difference

HashMap allows nulls

• One null key
• Any number of null values

CHM forbids nulls — throws NPE

• Rationale: disambiguation under concurrency
• map.get(key) == null could mean 'not present' OR 'present but null'
• In concurrent code, you can't safely use containsKey to disambiguate (races)
• CHM removes the ambiguity: null always means 'not present'

Iterator semantics

HashMap — fail-fast

• Throws ConcurrentModificationException on concurrent modification
• Even within single thread: for (k : map.keySet()) map.remove(k) throws
• Fix: use Iterator.remove() or keySet().removeIf()

CHM — weakly consistent

• No CME, ever
• Sees elements that existed when iterator was created
• May or may not see concurrent modifications
• For a true snapshot: copy the map

Atomic compound operations — CHM's superpower

`computeIfAbsent` — thread-safe memoization

• cache.computeIfAbsent(key, k -> expensiveCompute(k))
• If key present: return existing value (no lambda call)
• If absent: call lambda, store result, return it
• Two threads racing with same key → lambda called ONCE

`compute` — atomic read-modify-write

• cmap.compute("counter", (k, v) -> v == null ? 1 : v + 1)

`merge` — combine new with existing

• cmap.merge(word, 1, Integer::sum) — thread-safe word count

`putIfAbsent` — put only if absent; atomic

Warnings

• Functions inside compute/merge/computeIfAbsent run while bucket is locked
• Don't do I/O or block
• Don't call other CHM methods on same map (deadlock risk)

Parallel bulk operations (Java 8+)

• forEach(parallelismThreshold, action) — parallelizes if size exceeds threshold
• reduce, search also available
• Useful for bulk processing with minimum overhead

size() approximation

• CHM's size() returns an approximation
• Maintained as sum of per-bucket counters
• For exact long-valued count: mappingCount()

Collections.synchronizedMap(hashMap)

• Single-lock wrapper around HashMap
• Every op acquires the one monitor — serialized
• Iteration requires external sync: synchronized (map) { for (... ) }
• Compound ops NOT atomic: if (!m.containsKey(k)) m.put(k, v) has race
• Slower than CHM under contention
• Only for legacy / low-contention scenarios

Hashtable — legacy

• Same semantics as synchronizedMap
• Ancient API
• Never use in new code; use CHM

When to use which

Single-threaded: HashMap

Multi-threaded: ConcurrentHashMap (default choice)

Legacy / simple / low-contention: Collections.synchronizedMap is fine

Very specific patterns: ConcurrentSkipListMap for sorted concurrent, EnumMap synchronized for enum keys

Migration tip

• HashMap → CHM: replace null keys/values with sentinels
• Iterate-modify patterns work in CHM without CME
• Compound ops (check-then-put) become atomic via compute/merge

Recommendation: Default to `ConcurrentHashMap` for any multi-threaded scenario — lock-free reads via volatile, CAS fast path for empty buckets, per-bucket synchronized only for collision chains, and a rich set of atomic compound operations (computeIfAbsent, compute, merge, putIfAbsent). These atomic ops are the main reason to prefer CHM over external synchronization — they're the only way to do thread-safe memoization or counter updates without hand-rolled locks. Remember CHM forbids null keys and values — the ambiguity between 'absent' and 'present but null' can't be safely resolved under concurrency; use sentinels when migrating from HashMap. The iterator is weakly consistent — no CME, but you may or may not see concurrent changes; for a snapshot, copy the map. Avoid `Collections.synchronizedMap` and `Hashtable` — both use a single lock that serializes all operations; use them only for legacy code migration. Use HashMap only when you know access is single-threaded (e.g., method-local, request-scoped). Don't do I/O or block inside the functions you pass to compute/merge — the bucket is locked during execution. For parallel bulk operations, use CHM's `forEach(parallelismThreshold, ...)` with a sensible threshold; it only parallelizes when worthwhile. The mental model: HashMap = fast, single-thread; CHM = near-HashMap reads, bucket-scoped writes, safe for anything; synchronizedMap = legacy single-lock fallback.