Requirements & Concurrency Challenges

Let's define what our Concurrent HashMap must do. Each requirement is specific enough to drive a class, method, or synchronization decision in the final design.

R1: Put Operation. The map shall support put(key, value) which inserts a new key-value pair or updates the value if the key already exists. Returns the previous value associated with the key, or None/null if the key was new.

R2: Get Operation. The map shall support get(key) which returns the value associated with the given key, or None/null if the key is not present. Get must never block other get operations — concurrent reads should proceed in parallel without contention.

R3: Remove Operation. The map shall support remove(key) which deletes the key-value pair and returns the removed value, or None/null if the key was not present.

R4: Contains Operation. The map shall support contains_key(key) which returns True/true if the key exists, False/false otherwise.

R5: Size Tracking. The map shall support size() which returns the current number of key-value pairs. The size must be accurate to the extent possible under concurrent access — exact accuracy requires global synchronization, so a "close enough" count is acceptable during concurrent modifications (this is the same trade-off Java's ConcurrentHashMap.size() makes).

R6: Automatic Resizing. When the load factor (entries / capacity) exceeds 0.75, the map shall automatically double its internal capacity and rehash all existing entries. Resizing must not lose any entries or corrupt the data structure, even if other threads are concurrently reading or writing.

R7: Configurable Initial Capacity. The map shall accept an initial capacity at construction time. The capacity must be a power of 2 (to enable bitwise modular arithmetic for bucket indexing).

R8: Null Key and Value Handling. The map shall not accept None/null as keys or values. This simplifies the implementation — null return values from get() and remove() unambiguously mean "key not found" rather than "key maps to null."

R9: Hash Distribution. The map shall apply a secondary hash function (hash spreading) to reduce clustering when the caller's hash function produces poor distributions. Java's ConcurrentHashMap uses (h ^ (h >>> 16)) to spread high bits into low bits.

Every operation on the Concurrent HashMap touches shared mutable state — the bucket array, the linked lists in each bucket, and the entry count. These requirements define the thread-safety guarantees:

C1: Thread-Safe Reads. Multiple threads calling get() and contains_key() simultaneously must never see corrupted data, partially constructed entries, or stale bucket pointers. Ideally, reads should be lock-free (no locks acquired) for maximum throughput.

C2: Thread-Safe Writes. Multiple threads calling put() and remove() must produce a consistent final state. No entries should be lost, duplicated, or point to freed/invalid memory. Two threads writing to the same bucket must be serialized; two threads writing to different buckets should proceed in parallel.

C3: Linearizability for Single-Key Operations. Each individual put, get, remove must appear to take effect at a single instant in time. If Thread A calls put("x", 1) and Thread B later calls get("x"), Thread B must see 1 (assuming no intervening writes). This is the standard correctness guarantee for concurrent data structures.

C4: Safe Concurrent Resizing. Resizing (rehashing) involves allocating a new, larger array and transferring all entries from the old array to the new one. During this process, other threads must still be able to read (and ideally write) without blocking for the entire duration of the resize. This is the hardest concurrency challenge in the design.

C5: No Deadlocks. The design must be deadlock-free. This is straightforward for single-lock-per-operation designs but requires careful lock ordering if multiple locks are involved (e.g., during resizing with segment locking, we must acquire segment locks in a consistent order).

C6: Memory Visibility. Writes made by one thread must be visible to other threads within a bounded time. In Java, this requires volatile fields or lock-protected access. In Python, the GIL provides implicit visibility for bytecode-level operations, but compound operations still need explicit synchronization.

C7: Progress Guarantee. The system must guarantee that at least one thread makes progress in any concurrent execution. With segment locking, this means no livelock. With CAS, this means the retry loop eventually succeeds (lock-free guarantee).

To understand why each concurrency requirement exists, let's trace the specific race conditions that occur when two threads access an unsynchronized HashMap simultaneously. These races directly motivate the segment locking and CAS designs.

Race 1: Lost Update on Same Bucket

Thread A calls put("alice", 1), Thread B calls put("bob", 2), and both hash to bucket 5.

1. Thread A reads bucket[5] → null (empty)
2. Thread B reads bucket[5] → null (empty)
3. Thread A writes bucket[5] = Node("alice", 1)
4. Thread B writes bucket[5] = Node("bob", 2) — overwrites Alice's entry

Alice's entry is permanently lost. Both threads saw an empty bucket and wrote without checking if someone else wrote first.

Race 2: Corrupted Linked List

Thread A inserts at the head of a non-empty bucket (prepend). Thread B simultaneously inserts at the head of the same bucket.

1. Both threads read head = bucket[5] → same existing node
2. Thread A creates Node("x", 1, next=head), writes to bucket[5]
3. Thread B creates Node("y", 2, next=head), writes to bucket[5]

Thread A's node is lost — bucket[5] now points to Thread B's node, whose next skips Thread A's node entirely.

Race 3: Infinite Loop During Resize

This is the most dangerous race. When a HashMap resizes, it creates a new array and transfers entries. If two threads trigger resize simultaneously:

1. Both create new arrays (different objects)
2. Both iterate the old array, transferring entries
3. Thread A completes and publishes its new array
4. Thread B overwrites it with a partially different new array

The result can be circular references in bucket chains (node A's next points to node B, and node B's next points back to A), causing get() to loop forever. This exact bug was documented in Java's HashMap and was a major motivation for ConcurrentHashMap.

Race 4: Stale Read During Resize

Thread A starts get("alice"), hashes to bucket 3, and begins traversing the chain. Meanwhile, Thread B triggers a resize that moves all entries to a new array. Thread A is still traversing the old array — it might find "alice" (reading stale but consistent data) or it might follow a dangling pointer if the old array's nodes were modified during transfer.

Several critical decisions shape our design. Let's justify each one:

D1: Separate Chaining vs. Open Addressing

We chose separate chaining (linked list per bucket). Open addressing (linear/quadratic probing) is harder to make concurrent because probe sequences create dependencies between distant array slots — a thread probing for an empty slot might conflict with another thread's probe sequence. Chaining confines conflicts to a single bucket, making fine-grained locking practical.

D2: Two Implementation Strategies

We build two complete implementations instead of one:

• Segment Locking (T4): Divide the array into segments, each with its own lock. Simple, correct, and easy to reason about. Represents the JDK 5-7 approach.
• CAS Operations (T5): Use atomic compare-and-swap for lock-free reads and per-bucket CAS writes. More complex but higher performance under contention. Represents the JDK 8+ approach.

Teaching both shows the full concurrency spectrum — from locks to lock-free — and gives you vocabulary for any concurrency interview.

D3: Load Factor 0.75

We use 0.75 as the resize threshold, matching Java's ConcurrentHashMap and HashMap. This is a well-studied balance: lower factors waste memory, higher factors increase collision chain lengths and degrade O(1) access to O(n).

D4: Power-of-2 Capacities

Capacity is always a power of 2. This lets us replace the expensive modulo operation (hash % capacity) with a fast bitwise AND (hash & (capacity - 1)). When capacity is 16, hash & 15 gives the same result as hash % 16 but executes in a single CPU cycle.

D5: No Null Keys or Values

We disallow null keys and values. Java's ConcurrentHashMap does the same (unlike HashMap which allows one null key). The reason: when get(key) returns null, it must unambiguously mean "key not found." If null values were allowed, there's no way to distinguish "key maps to null" from "key doesn't exist" without an additional containsKey() call — which introduces a race condition between the two calls.

D6: Secondary Hash Spreading

We apply hash ^ (hash >>> 16) to mix high bits into low bits. Without this, if the caller's hash function clusters values in a narrow range, many keys hash to the same bucket despite having different hash codes. Spreading distributes entries more evenly across segments and buckets.

In Scope:

• Thread-safe put(key, value), get(key), remove(key), contains_key(key), size()
• Two complete implementations: segment locking and CAS-based
• Automatic resizing when load factor exceeds 0.75
• Separate chaining (linked list per bucket) for collision resolution
• Secondary hash function for distribution
• Performance benchmarking to compare both strategies

Out of Scope:

• Compound atomic operations (putIfAbsent, computeIfAbsent, merge) — interesting extensions but not part of the core design
• Concurrent iterators (weakly consistent iteration) — a complex topic on its own
• Open addressing (Robin Hood hashing, Cuckoo hashing) — different concurrency challenges
• Distributed hash maps, consistent hashing, or sharding across nodes
• Treeification of long bucket chains (JDK 8 converts chains to red-black trees at length 8) — an optimization we'll mention but not implement

Each requirement maps directly to a class or method in our final design:

Requirement	Class / Method	Concurrency Concern
R1: Put	ConcurrentHashMap.put(key, value)	Must lock the correct segment (or CAS the bucket head)
R2: Get	ConcurrentHashMap.get(key)	Lock-free in CAS version; read-lock in segment version
R3: Remove	ConcurrentHashMap.remove(key)	Must lock the correct segment (or CAS to unlink node)
R4: Contains	ConcurrentHashMap.contains_key(key)	Delegates to get() — same concurrency model
R5: Size	ConcurrentHashMap.size()	Sum of per-segment counts (may be approximate)
R6: Resize	ConcurrentHashMap._resize()	Most complex: must rehash while other threads operate
R7: Capacity	ConcurrentHashMap.__init__(capacity)	Power-of-2 enforcement
R8: Null check	put() / get() entry validation	Fail-fast at method entry
R9: Hash spread	ConcurrentHashMap._spread_hash(h)	Pure function, no concurrency concern
C1: Safe reads	volatile reads / lock-free traversal	Must see complete nodes, never partial
C2: Safe writes	Segment lock or per-bucket CAS	Only same-bucket writes serialize
C4: Safe resize	Lock all segments (segment version) or cooperative transfer (CAS version)	The hardest part of the design

In a concurrency interview, clarify the scope before designing:

• "Should I design for reads-heavy or writes-heavy workloads?" — This determines whether segment locking or CAS is the better fit. Reads-heavy favors CAS (lock-free reads); writes-heavy favors segment locking (simpler write path).
• "Do we need compound atomic operations like putIfAbsent?" — If yes, CAS-only approaches need retry loops. Segment locking makes compound operations easier since you already hold the lock.
• "What's the expected contention level?" — Low contention makes the difference between strategies negligible. High contention is where CAS shines.
• "Is resizing required, or can we assume a fixed capacity?" — Fixed capacity dramatically simplifies the design. If the interviewer says "assume fixed," you can skip the hardest part.
• "Do I need to support iteration?" — Weakly consistent iterators add a layer of complexity. If not needed, the design is cleaner.

Asking these questions shows the interviewer you understand the design space and can navigate trade-offs — which is the entire point of a concurrency interview.