A hash map is one of the most used data structures in real systems, and making it work correctly under concurrency is harder than it looks.

Multiple threads can insert, remove, and resize at the same time, and a naive lock around the whole map quickly becomes a bottleneck. The goal of a concurrent hash map is to provide safe, scalable access with high throughput under contention.

In this chapter, we will design a concurrent hash map step by step. We will start with a simple coarse-grained lock, then evolve toward finer-grained locking and CAS based approach.

Problem Statement

What We're Building

A thread-safe HashMap that allows multiple threads to read and write concurrently without corrupting data or losing updates. The goal is to maximize throughput by allowing independent operations to proceed in parallel while maintaining correctness guarantees.

Required Operations

Thread-Safety Requirements

Data Structure Fundamentals

Before adding concurrency, let's understand how a single-threaded HashMap works. This baseline is essential because concurrent solutions must preserve these mechanics while adding thread safety.

Core Concepts

Single-Threaded Implementation

Internal Structure

The diagram shows a HashMap with 8 buckets. Keys A and I both hash to bucket 2 (hash % 8 = 2), forming a chain. Keys G and O share bucket 7. Empty buckets (0, 1, 3, 4, 6) contain null. This chaining approach handles collisions but creates the first concurrency challenge: two threads modifying the same chain can corrupt it.

Concurrency Challenges

Before diving into solutions, let's understand what makes HashMap challenging to parallelize. These challenges will guide our design decisions.

Challenge 1: Race Condition on Put

Consider two threads inserting keys that hash to the same bucket.

Both threads read the same head pointer (X). Thread 1 inserts A pointing to X. Thread 2 then overwrites the bucket head with B pointing to X. Node A is orphaned, and its entry is silently lost. This is a classic lost update problem.

Challenge 2: Read-Modify-Write Without Atomicity

The put operation is inherently a read-modify-write sequence:

Without atomicity, another thread can interleave between steps 1 and 3, causing:

Challenge 3: Resize Hazards

When the load factor threshold is exceeded, the table must double in capacity and rehash all entries. This is dangerous during concurrent access:

A reader using the old table reference might access entries that are being moved or have already been moved to the new table. The reader could return null for a key that actually exists.

Challenge 4: Compound Operations

putIfAbsent(key, value) must atomically:

Without atomicity:

Both threads see the key as absent and both insert. One value is silently lost, and both callers believe their insert succeeded.

Consistency Model Requirements

Approach 1: Coarse-Grained Locking

The simplest approach: wrap the entire HashMap with a single lock. Every operation acquires this lock, serializing all access.

Implementation

Analysis

Single Lock Bottleneck

The diagram shows the fundamental problem: all four threads must wait for a single lock, even though they're accessing completely independent keys. Threads 1 and 3 are both reading (could run in parallel) and accessing different keys (definitely could run in parallel). But the coarse-grained lock forces them to wait.

When to Use:

Approach 2: Fine-Grained Locking (Lock Striping)

The key insight: most HashMap operations only touch one bucket. If we lock individual buckets (or groups of buckets), operations on different buckets can proceed in parallel. This is the approach used by Java 7's ConcurrentHashMap.

Strategy: Segment-Based Locking

Divide the hash table into segments, each with its own lock. The default is 16 segments. To access a key:

Threads 1, 2, and 3 access different segments and proceed in parallel. Thread 4 hashes to the same segment as Thread 1, so it waits. But overall concurrency is much higher than with a single lock.

Implementation

Handling Cross-Segment Operations

The size() method demonstrates the challenge of operations spanning multiple segments. We must lock all segments to get an accurate count. Without locking all, entries could be added or removed during counting, giving an inconsistent result.

Weakly Consistent Iteration

Iterating over a striped map can't guarantee a point-in-time snapshot without locking everything. Instead, we provide "weakly consistent" iteration:

This is acceptable for most use cases (logging, monitoring, debugging) where an approximate view is sufficient.

Analysis

Approach 3: CAS-Based

Java 8 redesigned ConcurrentHashMap to eliminate segment locks for most operations. The key innovations:

Key Insight

Most HashMap buckets are either empty or have very few entries. Java 8's approach optimizes for this:

CAS Insertion for Empty Buckets

Incremental Resize with Forwarding Nodes

When resizing, Java 8's ConcurrentHashMap doesn't stop the world. Instead:

Buckets 2, 3, and 7 are marked with forwarding nodes (FWD). Their entries have been moved to the new table. Buckets 1, 4, and 6 are still in the old table. A get(key) that hashes to bucket 2 sees the forwarding node and looks in the new table instead.

Atomic Compound Operations

putIfAbsent and computeIfAbsent must be atomic. In the CAS-based approach:

The synchronized block ensures the check-then-insert happens atomically. Between the existence check and the insert, no other thread can modify the bucket.

Analysis

Solution Comparison

Decision Tree for Choosing Approach

Recommendation:

Complete Implementation

This section provides the production-ready lock striping implementation, which is most relevant for interviews. The code is complete, tested, and includes all methods discussed.