Run it: Implement a hash map from scratch in code
A working hash map with chaining, its bucket distribution printed before and after a resize. And the tombstone problem demonstrated on a small open-fixing version.
Adding remove, _resize and a bucket-spread helper completes the chaining implementation.
Chaining: the straightforward answer
Each bucket holds a list of key-value pairs. On collision, append.
Exercising get, put and remove on a fixed-size map.
Adding automatic resizing keeps the load factor below 0.75. Insert six keys into a four-bucket map and watch the capacity double.
O(1) average for all three steps, O(n) worst case when every key collides.
Two details are load-bearing:
put must check for an existing key before appending, or updating a value inserts a copy and get returns the stale one.
Resizing rehashes every entry, because the bucket index depends on the capacity. Copying buckets across without rehashing puts keys in the wrong places. And they become unreachable.
Why the load factor matters
The load factor is entries divided by buckets. As it rises, buckets hold longer chains and lookups degrade from O(1) towards O(n).
| Load factor | Average chain length | Behaviour |
|---|
| 0.25 | ~1.1 | Fast, memory-wasteful |
| 0.75 | ~1.4 | The usual threshold |
| 2.0 | ~2.4 | Noticeably slower |
| 10 | ~10 | Effectively a linked list |
Resizing at 0.75 is the common choice (Java's HashMap uses exactly this; CPython uses about 2/3). Doubling the capacity is O(n), and amortised across the insertions that fit in the new space it is O(1) per step. The same argument as list append.
Choosing a power-of-two capacity allows hash & (cap - 1) instead of a modulo, which is faster. It also means only the low bits of the hash are used. So a hash function that varies mainly in its high bits clusters badly. Java's HashMap mixes high bits down before masking to reduce this problem.
Chaining versus open addressing
Separate chaining puts colliding entries in a list per bucket. Simple, deletion is trivial, and it tolerates a high load factor. This is what to implement under time pressure.
Open addressing stores entries in the table array and probes for another slot after a collision. It can improve cache locality and avoid per-entry pointers, but deletion needs tombstones so a lookup does not stop too early.
Why deletion is hard in open addressing
Removing an entry leaves a hole, and a probe sequence that ran through that slot to reach a later entry now stops at the hole and reports the later entry missing.
The fix is a tombstone: mark the slot deleted rather than empty. So probes continue past it but inserts may reuse it. Tombstones build up and in time force a rehash even without growth. Being able to say that is usually what the question is really checking.
The load factor and the resize
Lookup is O(1) only while buckets stay short. Once entries divided by buckets passes roughly 0.75, chains lengthen and every step drifts towards O(n).
So the table doubles and every key is rehashed, because the index is hash(key) % size and the size just changed. That single resize is O(n), and amortised over the insertions that caused it each insert is still O(1). But any single insert can be the expensive one.
Open addressing, the other
Instead of a list per bucket, store entries right in the array and probe for another slot on collision.
| | Chaining | Open addressing |
|---|
| Storage | List per bucket | One flat array |
| Extra memory | Pointers per entry | None |
| Cache behaviour | Poorer — pointer chasing | Better — contiguous |
| Deletion | Straightforward | Needs tombstones |
| Load factor tolerance | Above 1 is workable | Must stay well below 1 |
Deletion is the awkward part. Removing an entry outright breaks probe sequences that passed through that slot. A later lookup would stop at the gap and report the key missing. So deleted slots hold a tombstone marker meaning "empty, but keep probing".
Tombstones build up and degrade speed until a resize clears them. This is why open-addressed tables need periodic rehashing even without growth.
CPython dictionaries use open addressing with a probing sequence. Java's HashMap uses chained bins and, in modern implementations, can treeify a sufficiently long bin. These are implementation choices, not guarantees of the hash-table abstract data type.
The hash function
For an interview, hash(key) % capacity is acceptable. If asked to write one:
Three properties a hash function needs:
Deterministic. The same key must always give the same value, or entries become unreachable.
Uniform. Keys should spread across buckets. A hash returning a constant is valid and turns the table into a linked list.
Fast. It runs on every step.
It does not need to be cryptographic — that is a different requirement, and orders of magnitude slower.
Worth mentioning: Python randomises string hashes per process to prevent deliberate-collision denial-of-service attacks. This is why hash("abc") differs between runs.
Follow-up questions
"What if keys are integers 0 to 1,000,000?" Use direct fixing. An array indexed by the key. No hashing, no collisions, O(1) sure. Only viable when the key space is small and dense.
"How would you make it thread-safe?" A single lock serialises all of it; striped locking. One lock per group of buckets. Allows concurrency. Java's ConcurrentHashMap does this.
"What is the worst case?" O(n) when all keys collide. Java mitigates it by treeifying long chains, giving O(log n).
"How do you iterate in insertion order?" Maintain a doubly linked list of entries alongside the table. Python's OrderedDict uses linked-ordering behavior, while modern dict preserves insertion order through its compact table layout.
"What about memory?" Chaining costs a pointer per entry plus list overhead; open addressing reserves empty slots. Both trade memory for speed.