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).

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."

Overview

A hash map stores key–value pairs by mapping each key’s hash to a bucket. A complete design must handle collisions, resize as it fills, and preserve the equality and hashing contract for keys.

In this guide
  1. Run it: Implement a hash map from scratch in code
  2. Chaining: the straightforward answer
  3. Why the load factor matters
  4. Chaining versus open addressing
  5. Why deletion is hard in open addressing
  6. The load factor and the resize
  7. Open addressing, the other
  8. The hash function
  9. Follow-up questions
  10. Sources and next steps

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.

1Python
Output

Adding remove, _resize and a bucket-spread helper completes the chaining implementation.

2Python
Output
3Python
Output
4Python
Output

Chaining: the straightforward answer

Each bucket holds a list of key-value pairs. On collision, append.

5Python
Output

Exercising get, put and remove on a fixed-size map.

6Python
Output

Adding automatic resizing keeps the load factor below 0.75. Insert six keys into a four-bucket map and watch the capacity double.

7Python
Output

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 factorAverage chain lengthBehaviour
0.25~1.1Fast, memory-wasteful
0.75~1.4The usual threshold
2.0~2.4Noticeably slower
10~10Effectively 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.

 ChainingOpen addressing
StorageList per bucketOne flat array
Extra memoryPointers per entryNone
Cache behaviourPoorer — pointer chasingBetter — contiguous
DeletionStraightforwardNeeds tombstones
Load factor toleranceAbove 1 is workableMust 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:

8Python
Output

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.

Sources and next steps

How the code works

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.

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

Build a hash map from scratch with put, get and remove. Choose a hash function, handle collisions with chaining, and test it against edge cases.

INTERVIEW · vizlearn.in/interview/design-a-hashmap.html

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.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.