How ConcurrentHashMap Achieves Thread Safety Without Global Synchronized Blocks

ConcurrentHashMap avoids the performance penalty of global synchronization by using fine-grained locking strategies—segment locks in JDK 1.7 and CAS-based atomic operations with bucket-level locking in JDK 1.8—allowing concurrent threads to operate on different map segments simultaneously.

The java.util.concurrent.ConcurrentHashMap class is the cornerstone of high-performance concurrent Java applications, designed to eliminate the throughput bottleneck caused by Collections.synchronizedMap()'s single global lock. According to the CyC2018/CS-Notes repository, the implementation achieves thread safety through an evolutionary approach that minimizes lock contention while maintaining memory visibility guarantees.

Segment Locks: The JDK 1.7 Foundation

In Java 7 and earlier versions, ConcurrentHashMap divided the hash table into multiple independent segments to avoid monolithic locking.

Segment Array Architecture

As documented in notes/Java 容器.md, the map maintains an array of segments (Segment<K,V>[] segments), where each segment extends ReentrantLock and protects a distinct subset of hash buckets. This design ensures that threads operating on entries mapped to different segments can proceed concurrently without blocking each other.

• Each segment acts as a mini hash table with its own lock
• Hashing strategy: The high bits of the key's hash determine the segment index, while lower bits select the specific bucket within that segment
• Concurrency level: The default of 16 segments allows up to 16 threads to write simultaneously without contention

CAS Operations: The JDK 1.8 Lock-Free Revolution

Java 8 removed the segment array entirely, replacing it with a lock-free fast path using sun.misc.Unsafe CAS operations, falling back to synchronized blocks only when necessary.

Atomic Bucket Updates

The notes/Java 容器.md file explains that JDK 1.8 stores entries in a volatile Node<K,V>[] table array. Update operations follow this protocol:

1. CAS attempt: Threads first attempt to modify a bucket using Unsafe.compareAndSwapObject (CAS) on the volatile reference
2. Spin/fallback: If CAS fails due to contention, the thread briefly spins before acquiring a bucket-level synchronized lock on the specific Node instance
3. Visibility guarantee: The volatile keyword ensures that successful CAS writes are immediately visible to other threads without requiring full synchronization

This approach eliminates the memory overhead of segment objects while providing finer granularity than the previous segment-based design.

Lock-Free Size Calculation and Reads

Read operations and size calculations minimize blocking through optimistic algorithms that avoid locks entirely unless the map is undergoing rapid concurrent modification.

The Unsynchronized Size Algorithm

As detailed in notes/Java 容器.md, the size() method implements a multi-pass convergence strategy:

1. Initial scan: Sum the count fields across all segments (or bins in JDK 8) without acquiring locks
2. Consistency check: Capture modCount values; if they remain stable across two consecutive passes, return the result immediately
3. Lock fallback: Only after a configurable number of failed attempts (default 3 retries) does the method acquire all segment locks to compute an exact snapshot

For containsValue() and similar queries, the implementation similarly attempts lock-free traversal first, acquiring locks only when encountering a bin currently being modified.

Bucket-Level Synchronization for Structural Changes

When hash collisions cause bucket chains to exceed length thresholds, ConcurrentHashMap performs structural modifications using minimal locking scopes.

Red-Black Tree Conversion

According to notes/Java 容器.md, when a linked list in a bucket grows beyond 8 entries (TREEIFY_THRESHOLD), the implementation:

• Acquires a synchronized block on the specific bucket node (not the entire map)
• Converts the linked list to a red-black tree to maintain O(log N) lookup performance
• Releases the lock immediately after tree construction

This bucket-level synchronization ensures that resizing or treeification affects only the threads operating on that specific hash collision chain, leaving thousands of other buckets accessible without contention.

Practical Implementation Examples

The following patterns demonstrate the high-concurrency capabilities of these mechanisms:

Concurrent Counter Updates

import java.util.concurrent.*;

public class ConcurrentCounter {
    private static final ConcurrentHashMap<String, Long> metrics = new ConcurrentHashMap<>();

    public static void increment(String key) {
        // Uses CAS-based merge, no synchronized blocks for most operations
        metrics.merge(key, 1L, Long::sum);
    }

    public static void main(String[] args) throws InterruptedException {
        ExecutorService executor = Executors.newFixedThreadPool(16);
        
        // 16 threads updating concurrently without global lock contention
        for (int i = 0; i < 16; i++) {
            executor.submit(() -> {
                for (int j = 0; j < 1_000_000; j++) {
                    increment("requests");
                }
            });
        }
        
        executor.shutdown();
        executor.awaitTermination(1, TimeUnit.MINUTES);
        System.out.println("Total: " + metrics.get("requests")); // 16,000,000
    }
}

Lock-Free Size Estimation

public class SizeEstimation {
    public static void main(String[] args) {
        ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();
        
        // Parallel population
        IntStream.range(0, 1_000_000).parallel().forEach(i -> 
            map.put(i, "value-" + i)
        );
        
        // Mostly lock-free size calculation
        int size = map.size();
        System.out.println("Entries: " + size);
    }
}

Summary

• JDK 1.7 architecture used an array of 16 segments (Segment<K,V>[]), each acting as an independent ReentrantLock to allow concurrent writes to different map regions.
• JDK 1.8 optimization removed segments in favor of CAS-based atomic updates on volatile bucket references, using Unsafe.compareAndSwapObject for lock-free modifications and falling back to bucket-level synchronized blocks only during contention.
• Read operations leverage optimistic scanning algorithms that avoid locks entirely unless the map is rapidly changing, as implemented in the size() and containsValue() methods described in notes/Java 容器.md.
• Structural modifications such as red-black tree conversion use bucket-level synchronization, ensuring that hash table maintenance never blocks unrelated concurrent operations.

Frequently Asked Questions

What is the difference between ConcurrentHashMap's segment locks and Hashtable's global lock?

Hashtable synchronizes every public method on the instance itself (this), creating a single global lock that serializes all read and write operations. In contrast, ConcurrentHashMap (JDK 1.7) divides the table into 16 segments, each with its own lock, allowing 16 threads to write to different segments simultaneously. JDK 8 eliminates segments entirely, using CAS operations for lock-free updates and synchronizing only on individual hash buckets when necessary.

Does ConcurrentHashMap use synchronized blocks at all?

Yes, but minimally and locally. According to the source analysis in notes/Java 容器.md, JDK 8 uses synchronized blocks only as a fallback when CAS operations fail repeatedly, and the lock is acquired on the specific bucket node (synchronized (f) where f is the first node in the bin) rather than the map instance. This ensures that a resizing or tree conversion in one bucket never blocks access to other keys.

Why did Java 8 remove the segment array from ConcurrentHashMap?

The segment array imposed a memory overhead (16 separate hash tables) and limited concurrency to the number of segments (default 16). By replacing segments with a single volatile node array and CAS operations, Java 8 achieved higher throughput (unbounded concurrency for disjoint keys), lower memory footprint, and finer granularity of locking, while maintaining the same thread-safety guarantees through hardware-level atomic primitives.

How does ConcurrentHashMap prevent memory visibility issues without synchronized blocks?

The implementation relies on volatile variables and happens-before ordering guaranteed by CAS operations. When a thread successfully updates a bucket using Unsafe.compareAndSwapObject, the volatile write establishes a happens-before relationship with subsequent reads by other threads. For operations that do require locking, the synchronized block's entry and exit semantics provide the necessary memory barriers, but these are scoped to individual buckets rather than the entire map.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}