Design a HashMap from Scratch

Problem Implement a hash map from scratch — an array of buckets with collisions resolved by chaining — supporting put, get, and remove with average-case O(1).

Requirements

• put(key, value) -> void — insert or overwrite an existing key
• get(key) -> value? — null/absent on miss
• remove(key) -> bool — whether a key was present
• size() -> int and containsKey(key) -> bool
• Average O(1) for all three core operations under a bounded load factor

Core design

• Backing array of N buckets. index = hash(key) % N (in practice hash & (N-1) with a power-of-two N, which is why real implementations size that way).
• Each bucket is a chain — a linked list or dynamic array of Entry(key, value, next). On collision, append to that bucket; lookup walks the chain comparing keys with equals, not just the hash.
• Hash and equality must agree: two keys that are equal must hash identically, or the map loses entries. Mutable keys mutated after insertion are unfindable — worth stating.
• Load factor = size / N. Once it exceeds a threshold (0.75 is the usual choice), resize: allocate a larger array, rehash every entry into it. Resizing is O(n) but rare, so put stays O(1) amortized.
• Without resizing, chains grow linearly and every operation degrades toward O(n) — resizing is what keeps the O(1) claim honest.

Discussion points

• Chaining vs. open addressing (linear probing): chaining is simple and degrades gracefully; open addressing has better cache locality and no per-entry node, but needs tombstones on delete and suffers clustering. Name the trade-off explicitly.
• Adversarial or poor hash functions collapse everything into one bucket, making lookups O(n). Mitigations: hash mixing/spreading, and converting an over-long chain into a balanced tree (O(log n) worst case) as modern JDK HashMap does.
• Contrast with an ordered map backed by a balanced BST: O(log n) operations but sorted iteration and range queries. Hash maps buy average O(1) by giving up all ordering — the iteration order is not merely unspecified, it can change on resize.
• Edge cases: null keys, overwriting an existing key (size must not increment), and removing the head of a chain.
• Concurrency: read-during-resize can see a half-migrated table. Discuss a global lock, lock striping, or a copy-on-write table.
• Extension: incremental/rehash-on-access resizing to avoid the latency spike of a stop-the-world rehash on a large table.