vizlearn

Implement a hash map from scratch

Interview QuestionsBy Updated

An array of buckets, each a small list of (key, value) pairs. The key's hash picks the bucket; collisions append to that bucket's list and lookups compare keys along it. Grow and rehash once the average bucket stops being short — that is what keeps operations O(1).

Overview

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 everything in the array itself and probes for the next free slot on a collision. Better cache behaviour and less pointer chasing — it is what CPython actually uses — but deletion is genuinely hard.

Dicts, sets & hashingCoding problemMedium

Step through it

What to watch

  • A collision is normal, not an error — both entries share a bucket.
  • Lookups compare keys, never just hashes.
  • A resize invalidates every bucket index at once.

Say this out loud

"Array of buckets with separate chaining. hash(key) % size picks the bucket, and I compare keys within it because collisions are expected. Resize when the load factor passes about 0.75, rehashing everything - the index depends on the size, so it all moves."

Implement a hash map from scratch

Implement a hash map with put, get and remove, without using a dict.

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 accumulate and eventually 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 operation 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 individual insert can be the expensive one.

Run it in Python

A working hash map with chaining, its bucket distribution printed before and after a resize, and the tombstone problem demonstrated on a small open-addressing version.

hashmap.pyPython 3
Output
How the code works
  1. hash(key) % len(self.buckets)Two jobs. The hash turns a key into a number; the modulo folds it into a valid index. Change the bucket count and every index changes, which is why a resize rehashes.
  2. if k == keyKeys are compared, not hashes. Two different keys can share a bucket, so this comparison is what makes the answer correct rather than merely probable.
  3. if self.count / len(self.buckets) > 0.75The load factor. O(1) holds only while chains stay short, so the table grows before they lengthen rather than after.
  4. self.slots[...] = None in the naive versionDeleting by blanking breaks the probe chain: the lookup for b stops at the hole left by a and reports it missing. That is what tombstones exist to prevent.
Change one thing
  • Print spread() after every put. The longest chain creeps up and drops back to 1 at each resize.
  • Add a tombstone marker to the open-addressing version so probes continue past deletions. Then count how many accumulate before a rehash is needed anyway.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. In separate chaining, a collision means:
  2. Why does a resize have to rehash every key?
  3. Why is deletion harder in open addressing than in chaining?





 Cheat sheet
Implement a hash map from scratch
An array of buckets, each a small list of (key, value) pairs. The key's hash picks the bucket; collisions append to that bucket's list and lookups compare keys along it. Grow and rehash once the average bucket stops being short — that is what keeps operations O(1).
INTERVIEW · vizlearn.in/interview/design-a-hashmap.html
More in Interview
InterviewGroup records and invert a dictionaryInterviewWhy are Python strings immutable?InterviewWhat does slicing a string cost?InterviewDoes len() count characters or bytes?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact