All topics
3 / 101
collections
advanced

ConcurrentHashMap

A thread-safe Map with concurrent reads and finely-grained writes — without locking the entire map.

A ConcurrentHashMap is a map that many threads can use at the same time without breaking it. A plain HashMap cannot do that: two threads writing together can lose entries and corrupt the size.

A library with one lock per shelf instead of one lock for the whole building. Many readers and writers can work in parallel as long as they're not at the same shelf.

Key Concepts

1
How it avoids one big lock. A HashMap is an array of buckets. ConcurrentHashMap uses the same layout, and locks one bucket at a time rather than the whole map.
HashMapConcurrentHashMap
2
Two threads writing keys that land in different buckets never wait for each other. Only two threads writing to the same bucket contend, and that is rare when keys are spread out.
3
Reads take no lock at all. The buckets are marked volatile, which guarantees a reading thread sees the latest value written by another thread.
volatile
4
Compare that with Collections.synchronizedMap, which puts one lock around everything. Every operation waits for every other, including reads. Under load the difference is large.
Collections.synchronizedMap
5
Each operation is safe. A sequence of them is not.This is the mistake that matters:
6
    if (!map.containsKey(k)) {     // thread A checks: absent
        map.put(k, compute(k));    // thread B checks too, also absent
    }                              // both compute, both write
7
Both threads checked before either wrote. Both did the work. One result is thrown away, and if compute has side effects, both happened.
compute
8
The map provides combined operations that close the gap, each done under the bucket's lock:
9
  putIfAbsent(k, v)         writes only if the key is absent
  computeIfAbsent(k, fn)    runs fn at most once per key, ever
  merge(k, v, fn)           combines with whatever is there
  compute(k, fn)            update or insert in one step
10
The counter idiom is the common example:
11
    map.put(k, map.getOrDefault(k, 0) + 1);   // loses updates
    map.merge(k, 1, Integer::sum);            // correct
12
Do not do slow work inside those functions. The function you pass to computeIfAbsent runs while that bucket is locked. A network call in there blocks every other thread that needs the same bucket.
computeIfAbsent
13
Worse, calling back into the same map from inside the function can hang, because you are trying to take a lock you are already holding.
14
size() is an estimate while writes are happening. Producing an exact count would mean stopping every writer. The map gives you a close answer instead, and the same reasoning explains why looping over it never throws ConcurrentModificationException: you see a valid snapshot in progress, not a frozen one.
size()ConcurrentModificationException
15
Nulls are rejected on purpose. map.get(k) returning null would be ambiguous — key absent, or key present with a null value? In a single-threaded HashMap you can settle that with containsKey. With several threads, the answer can change between the two calls, so the ambiguity cannot be resolved at all.
map.get(k)nullHashMapcontainsKey
16
What the interviewer is probing.1. "How is it thread-safe?" Probing: the mechanism. Stalls: "It is synchronised." Moves up: lock-free reads and one lock per bucket, so unrelated writers never meet.
17
2. "This or Collections.synchronizedMap?" Probing: the cost. Stalls: "Either works." Moves up: one lock for the entire map versus one per bucket, and that synchronizedMap still needs external locking to iterate safely.
Collections.synchronizedMapsynchronizedMap
18
3. "Is check-then-put safe?" Probing: atomic sequences. Stalls: "Yes, both operations are atomic." Moves up: each is, the pair is not; use putIfAbsent or computeIfAbsent.
putIfAbsentcomputeIfAbsent
19
4. "Why can it not hold nulls?" Probing: the reasoning. Stalls: "It just cannot." Moves up: a null answer would be ambiguous, and with concurrency you cannot check afterwards.
20
5. "What does size() return during writes?" Probing: weak guarantees. Stalls: "The size." *Moves up:* an estimate, because an exact one would require stopping the world.
size()
21
  Choosing a concurrent map
22
                        ConcurrentHashMap   synchronizedMap   HashMap
  ------------------------------------------------------------------
  Read locking          none                whole map         none
  Write locking         per bin             whole map         none
  Iteration safety      weakly consistent   caller must lock  fails fast
  CME on iterate        never               yes, if unlocked  yes
  null key / value      neither             allowed           allowed
  size()                estimate            exact (locked)    exact
  Throughput, 8 threads high                low               unsafe
23
  Atomic compound operations (use these, not get-then-put)
24
    putIfAbsent(k, v)          write only when absent
    computeIfAbsent(k, fn)     fn runs at most once per key
    computeIfPresent(k, fn)    update only when present
    compute(k, fn)             update or insert
    merge(k, v, fn)            combine with an existing value
    getOrDefault(k, d)         read with a fallback, no write
25
  The counter idiom
    // wrong: lost updates
    map.put(k, map.getOrDefault(k, 0) + 1);
26
    // right
    map.merge(k, 1, Integer::sum);
27
  The deadlock to avoid
    map.computeIfAbsent(k, key -> {
        return map.get(otherKey);   // re-entrant call while the
    });                             // bin lock is held - can hang
                                    // or corrupt internal state
Use cases:ConcurrencyCachingAtomic Ops