Implement a hash map from scratch

Interview QuestionsBy Ashish JangraUpdated 30 August 2026

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

The requirement

Implement put, get and remove with O(1) average time, without using the language's built-in dictionary.

The design has three parts, and stating them upfront is the expected opening:

An array of buckets — the storage. A hash function mapping keys to bucket indices. A collision strategy for when two keys land in the same bucket.

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

class HashMap: def __init__(self, buckets=8): self.buckets = [[] for _ in range(buckets)] self.count = 0 self.resizes = 0 def _index(self, key): return hash(key) % len(self.buckets) # hash picks the bucket def put(self, key, value): bucket = self.buckets[self._index(key)] for i, (k, _) in enumerate(bucket): if k == key: # compare KEYS, not hashes bucket[i] = (key, value) return bucket.append((key, value)) self.count += 1 if self.count / len(self.buckets) > 0.75: self._resize() def get(self, key, default=None): for k, v in self.buckets[self._index(key)]: if k == key: return v return default def remove(self, key): bucket = self.buckets[self._index(key)] for i, (k, _) in enumerate(bucket): if k == key: bucket.pop(i) # trivial with chaining self.count -= 1 return True return False def _resize(self): old = self.buckets self.buckets = [[] for _ in range(len(old) * 2)] for bucket in old: for k, v in bucket: # every key moves self.buckets[self._index(k)].append((k, v)) self.resizes += 1 def spread(self): sizes = [len(b) for b in self.buckets] return f"{len(self.buckets)} buckets, longest chain {max(sizes)}, empty {sizes.count(0)}" m = HashMap() for i, w in enumerate("a b c d".split()): m.put(w, i) print("HashMap ->", m.get("c"), "| missing:", m.get("z"))

class NaiveOpenAddressing: """Deletes by blanking the slot. Watch what that does to a probe.""" def __init__(self, size=8): self.slots = [None] * size def _probe(self, key): i = hash(key) % len(self.slots) while self.slots[i] is not None and self.slots[i][0] != key: i = (i + 1) % len(self.slots) # linear probing return i def put(self, key, value): self.slots[self._probe(key)] = (key, value) def get(self, key): i = hash(key) % len(self.slots) while self.slots[i] is not None: if self.slots[i][0] == key: return self.slots[i][1] i = (i + 1) % len(self.slots) return "NOT FOUND" def delete(self, key): self.slots[self._probe(key)] = None # a hole, not a tombstone m = NaiveOpenAddressing() m.put("a", 1); m.put("b", 2) print("naive open addressing ->", m.get("a"), m.get("b"))

class Fixed: def __init__(self, name, h): self.name, self.h = name, h def __hash__(self): return self.h def __eq__(self, other): return isinstance(other, Fixed) and self.name == other.name def __repr__(self): return self.name a, b = Fixed("a", 7), Fixed("b", 7) # same hash, different keys d = {a: 1, b: 2} print("colliding keys:", d, "- equality separates them, not the hash")

class MyHashMap: def __init__(self, capacity=16): self.cap = capacity self.size = 0 self.buckets = [[] for _ in range(capacity)] def _index(self, key): return hash(key) % self.cap def get(self, key): for k, v in self.buckets[self._index(key)]: if k == key: return v return None def put(self, key, value): bucket = self.buckets[self._index(key)] for i, (k, _) in enumerate(bucket): if k == key: bucket[i] = (key, value) # update in place return bucket.append((key, value)) self.size += 1 if self.size / self.cap > 0.75: self._resize() def remove(self, key): bucket = self.buckets[self._index(key)] for i, (k, _) in enumerate(bucket): if k == key: bucket.pop(i) self.size -= 1 return True return False def _resize(self): old = self.buckets self.cap *= 2 self.buckets = [[] for _ in range(self.cap)] self.size = 0 for bucket in old: for k, v in bucket: self.put(k, v) # rehash everything m = MyHashMap(capacity=4) for i, word in enumerate("vectors norms basis rank trace det".split()): m.put(word, i) print("size :", m.size, "buckets:", m.cap, "<- it resized") print("get basis :", m.get("basis")) print("get missing:", m.get("nope")) print("remove :", m.remove("norms"), "| now:", m.get("norms"))

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

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

Effectively a linked list

	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

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

def string_hash(s, cap): h = 0 for ch in s: h = (h * 31 + ord(ch)) % cap # 31: a common odd prime multiplier return h for word in ["basis", "rank", "trace"]: print("%-6s -> %d" % (word, string_hash(word, 16)))

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

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.

Implement a hash map from scratch

Overview

The requirement

Step through it

What to watch

Say this out loud