Implement a map from integer keys to integer values with three operations: put(key, value) inserts or replaces, get(key) returns the value or -1, and remove(key) deletes the key if present. Don't use your language's built-in hash table.
Before you code
Decide your collision strategy first. Chaining (an array of lists) is the easiest to get right. Linear probing is a better exercise: you will have to handle deletion without breaking lookups for keys stored further along.
Hints
- Pick a power-of-two capacity, such as 1,024, and compute the slot with a mask.
- With linear probing, a lookup stops at an empty slot, never at a tombstone.
- Count entries and grow the array when the load factor passes 0.75. Every key has to be inserted again, because its slot depends on the capacity.
Production & complexity notes
When solving Design a hash map on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Collisions: when two keys want the same slot to reinforce the underlying pattern.
What it practices
The whole module in one exercise: slots, collisions and tombstones from Collisions: when two keys want the same slot, and growth from Resizing and load factor.