Design Concurrent HashMap — Low-level design | OneNoughtOne

0/105

00:00:00

Design Concurrent HashMap

Advanced

Design a thread-safe hash map using lock striping, inspired by Java's pre-Java 8 ConcurrentHashMap. The map is partitioned into N segments (power of 2), each with its own reentrant lock. Operations on different segments proceed concurrently while operations on the same segment are serialized. A supplementary hash function spreads bits to reduce collisions: high bits select the segment and low bits select the bucket within the segment. Each bucket uses separate chaining (singly linked list with head insertion). When a segment's entry count exceeds its load-factor threshold, only that segment rehashes (doubles buckets and redistributes entries) without blocking other segments. The map provides atomic operations: putIfAbsent, replace (CAS semantics), computeIfAbsent, computeIfPresent, and merge — all atomic within a single segment lock.

Core Use Cases

Put / Get / Remove

Store, retrieve, and delete key-value pairs; get is lock-free (volatile reads), put/remove acquire segment lock

Lock striping (segmented locking)

Map is divided into N segments, each with its own lock; operations on different segments execute concurrently

Hash spreading

Supplementary hash function mixes high bits into low bits to reduce collisions; high bits select segment, low bits select bucket

Per-segment rehashing

When a segment's load exceeds threshold, only that segment doubles its bucket array and redistributes entries

Collision handling (separate chaining)

Each bucket is a singly linked list; new entries inserted at head for O(1) insert

Atomic putIfAbsent

Insert only if key is absent; returns existing value if present — atomic within segment lock

Atomic replace (CAS semantics)

Replace value only if current value matches expected old value — compare-and-swap within segment

computeIfAbsent / computeIfPresent

Compute and cache value from a function atomically; useful for lazy initialization without double-computation

Merge

If key absent, insert value; if present, merge old+new using a merge function — atomic within segment

Constraints

Number of segments must be a power of 2 (enables bitwise mask for segment selection)
Segment bucket array sizes are powers of 2 (enables bitwise index for bucket selection)
Get operations can be lock-free using volatile reads (Java) or acquire read lock
Put/Remove must hold the segment's exclusive lock
Rehashing is localized to a single segment — does not block other segments
Approximate size() is the sum of segment counts (not globally consistent under concurrent modification)

Assumptions

Keys implement proper hashCode() and equals() (or __hash__ and __eq__ in Python)
Null keys are not permitted (None / null)
Null values are not permitted (to distinguish 'absent' from 'stored null')
Load factor defaults to 0.75 (same as Java HashMap)
Concurrency level defaults to 16 segments

In Scope

Core operations: get, put, remove, containsKey, size, isEmpty, clear
Lock striping with configurable concurrency level
Supplementary hash function with bit spreading
Per-segment rehashing when load factor exceeded
Separate chaining (linked list per bucket)
Atomic operations: putIfAbsent, replace (CAS), computeIfAbsent, computeIfPresent, merge
Keys / values / entries snapshot views
Python dunder methods (__getitem__, __setitem__, __contains__, __len__)

Out of Scope

Tree-ified bins (Java 8+ ConcurrentHashMap converts long chains to red-black trees)
Lock-free CAS-based implementation (Java 8+)
Weakly consistent iterators
Bulk parallel operations (forEach, search, reduce)
Serialization / persistence
Distributed hash map

Approach Guide(Click to expand each section)

Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.

List Core Use Cases

Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.

Identify Actors

Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.

Clarify Constraints

What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.

Ask About Edge Cases

What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.

Follow-up Questions(Questions an interviewer might ask)

💡 Draw UML class diagrams, sequence diagrams, or any design visualizations. Submit from the Code tab.

Loading canvas...

00:00:00

Design Concurrent HashMap

Advanced

Design a thread-safe hash map using lock striping, inspired by Java's pre-Java 8 ConcurrentHashMap. The map is partitioned into N segments (power of 2), each with its own reentrant lock. Operations on different segments proceed concurrently while operations on the same segment are serialized. A supplementary hash function spreads bits to reduce collisions: high bits select the segment and low bits select the bucket within the segment. Each bucket uses separate chaining (singly linked list with head insertion). When a segment's entry count exceeds its load-factor threshold, only that segment rehashes (doubles buckets and redistributes entries) without blocking other segments. The map provides atomic operations: putIfAbsent, replace (CAS semantics), computeIfAbsent, computeIfPresent, and merge — all atomic within a single segment lock.

Core Use Cases

Put / Get / Remove

Store, retrieve, and delete key-value pairs; get is lock-free (volatile reads), put/remove acquire segment lock

Lock striping (segmented locking)

Map is divided into N segments, each with its own lock; operations on different segments execute concurrently

Hash spreading

Supplementary hash function mixes high bits into low bits to reduce collisions; high bits select segment, low bits select bucket

Per-segment rehashing

When a segment's load exceeds threshold, only that segment doubles its bucket array and redistributes entries

Collision handling (separate chaining)

Each bucket is a singly linked list; new entries inserted at head for O(1) insert

Atomic putIfAbsent

Insert only if key is absent; returns existing value if present — atomic within segment lock

Atomic replace (CAS semantics)

Replace value only if current value matches expected old value — compare-and-swap within segment

computeIfAbsent / computeIfPresent

Compute and cache value from a function atomically; useful for lazy initialization without double-computation

Merge

If key absent, insert value; if present, merge old+new using a merge function — atomic within segment

Constraints

Number of segments must be a power of 2 (enables bitwise mask for segment selection)
Segment bucket array sizes are powers of 2 (enables bitwise index for bucket selection)
Get operations can be lock-free using volatile reads (Java) or acquire read lock
Put/Remove must hold the segment's exclusive lock
Rehashing is localized to a single segment — does not block other segments
Approximate size() is the sum of segment counts (not globally consistent under concurrent modification)

Assumptions

Keys implement proper hashCode() and equals() (or __hash__ and __eq__ in Python)
Null keys are not permitted (None / null)
Null values are not permitted (to distinguish 'absent' from 'stored null')
Load factor defaults to 0.75 (same as Java HashMap)
Concurrency level defaults to 16 segments

In Scope

Core operations: get, put, remove, containsKey, size, isEmpty, clear
Lock striping with configurable concurrency level
Supplementary hash function with bit spreading
Per-segment rehashing when load factor exceeded
Separate chaining (linked list per bucket)
Atomic operations: putIfAbsent, replace (CAS), computeIfAbsent, computeIfPresent, merge
Keys / values / entries snapshot views
Python dunder methods (__getitem__, __setitem__, __contains__, __len__)

Out of Scope

Tree-ified bins (Java 8+ ConcurrentHashMap converts long chains to red-black trees)
Lock-free CAS-based implementation (Java 8+)
Weakly consistent iterators
Bulk parallel operations (forEach, search, reduce)
Serialization / persistence
Distributed hash map

Approach Guide(Click to expand each section)

Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.

List Core Use Cases

Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.

Identify Actors

Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.

Clarify Constraints

What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.

Ask About Edge Cases

What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.

Follow-up Questions(Questions an interviewer might ask)

💡 Draw UML class diagrams, sequence diagrams, or any design visualizations. Submit from the Code tab.

Loading canvas...

Design Concurrent HashMap

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Follow-up Questions(Questions an interviewer might ask)

Explore the full editorial.

Sign in to view submissions

Design Concurrent HashMap

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Follow-up Questions(Questions an interviewer might ask)

Explore the full editorial.

Sign in to view submissions

Design Concurrent HashMap

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Gather Requirements~3 min

Identify Classes & Entities~4 min

Define Relationships~3 min

Apply Design Patterns~4 min

Apply SOLID Principles~3 min

Code Organization~2 min

Follow-up Questions(Questions an interviewer might ask)

1How does Java 8+ ConcurrentHashMap differ from this segment-based design?

2How would you make get() truly lock-free?

3How would you handle long chains and improve worst-case lookup from O(n) to O(log n)?

4How would you implement a size() that is globally consistent?

5How would you extend this to a distributed hash map (like Memcached)?

Key Topics

Asked At

Explore the full editorial.

Sign in to view submissions

Design Concurrent HashMap

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Gather Requirements~3 min

Identify Classes & Entities~4 min

Define Relationships~3 min

Apply Design Patterns~4 min

Apply SOLID Principles~3 min

Code Organization~2 min

Follow-up Questions(Questions an interviewer might ask)

1How does Java 8+ ConcurrentHashMap differ from this segment-based design?

2How would you make get() truly lock-free?

3How would you handle long chains and improve worst-case lookup from O(n) to O(log n)?

4How would you implement a size() that is globally consistent?

5How would you extend this to a distributed hash map (like Memcached)?

Key Topics

Asked At

Explore the full editorial.

Sign in to view submissions