ConcurrentHashMap Implementation

ConcurrentHashMap is the “gold standard” for high-performance concurrent collections in Java. It provides thread-safety with almost no overhead for reads and minimal locking for writes.

Source Code #

View Source on GitHub

Evolution of Architecture #

• JDK 7 and earlier: Used a Segment-based locking approach (also known as lock striping).
• JDK 8 and later: Uses a more granular, bin-based locking approach. It uses CAS (Compare-And-Swap) for empty bins and synchronized only for the head of a bin during updates.

Implementation Mechanism #

• Wait-Free Reads: get() and other retrieval operations are almost entirely wait-free (no locking).
• Treeification: When a bin grows beyond 8 elements, it is converted from a linked list into a red-black tree.
• Lazy Initialization: The table itself is only initialized when the first entry is put.

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    // ... CAS for empty bins, synchronized for bin heads ...
}

Canonical Usage #

When to use: Use ConcurrentHashMap whenever you need a thread-safe hash map with high scalability. It is almost always better than a synchronized HashMap or Hashtable.

Common Patterns:

• Atomic Updates: Using computeIfAbsent, merge, and compute for complex atomic logic.
• Frequency Counting: Using LongAdder as the value and initializing via computeIfAbsent.

ConcurrentMap<String, LongAdder> counters = new ConcurrentHashMap<>();

// Atomic frequency count
counters.computeIfAbsent("event-type", k -> new LongAdder()).increment();

Performance Trade-offs #

• Pros: Outstanding read performance. Scalability on write-heavy workloads.
• Cons: size() and isEmpty() provide estimates rather than exact counts.