Loading LLD design...
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.
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
Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.
Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.
Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.
What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.
What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.