Design HashMap

Hash Table Implementation

Build a key-value store with put, get and remove in O(1) average time: a bucket array, a hash function, chaining for collisions, and a resize when the table fills up.

Overview

A hash map stores values by key and finds them again without scanning. It turns the key into a number (the hash), turns that number into an array index (the bucket), and looks only in that bucket. Two keys that land in the same bucket are a collision, and handling collisions is most of the design.

The interview version asks for put(key, value), get(key) and remove(key), each in O(1) time on average. You are expected to write the bucket array and the collision handling yourself, not to wrap the language's built-in map. The problem is short, so interviewers use it to watch details: how you map a hash to an index, how you update an existing key without adding a duplicate, when you resize, and why every entry has to be rehashed when you do.

A strong answer names the three parts in the first minute (hash function, bucket array, chains), states the load factor rule before writing code, and mentions what the real libraries do: Java's HashMap starts with 16 buckets and resizes at a load factor of 0.75; CPython's dict uses open addressing and resizes when it is two thirds full.

Scoping the problem

What are the keys? — The map only needs keys that can be hashed and compared for equality — Any hashable object
What does get return for a missing key? — None, a default, or -1 as in the LeetCode version — The code below takes a default
Should remove report whether the key existed? — Decides the return type — Returns True or False
Fixed size or growing? — A fixed table degrades to long chains; a growing one needs resize logic — Grows by doubling
Chaining or open addressing? — Two different collision designs with different code — Chaining, unless asked otherwise
Shared by many threads? — Adds a lock, and decides how fine-grained it is — Follow-up, not the core

From key to bucket

The hash function turns a key into an integer. The bucket index is that integer reduced to the range of the array. In Python, hash(key) % capacity is enough because % with a positive divisor never returns a negative number, even for a negative hash.

Two library details are worth knowing here, because interviewers ask about them.

Reducing the hash to an index — (n - 1) & hash, which works because the table size n is always a power of two — hash % capacity; a negative hash still gives a non-negative index
Spreading the bits first — hash = h ^ (h >>> 16) folds the high bits into the low ones, so the masking step sees them — Not needed for the modulo approach
Equal keys — equals must agree with hashCode — Objects that compare equal must have the same hash; 1 and 1.0 hash the same
Hash of a string — Deterministic — Randomized per process by default (PYTHONHASHSEED), to stop attackers from forcing every key into one bucket

Collisions: chaining

With chaining, each bucket holds a linked list of entries. A collision adds one node to that list. Lookup walks the chain and compares keys with ==, so a chain of length k costs k comparisons.

The other family of designs is open addressing: every entry lives in the array itself, and a collision probes for another free slot. Both are used in practice.

Where entries live — Linked nodes hung off each bucket — In the array itself
On a collision — Add a node to the chain — Probe other slots until one is free
Delete — Unlink the node — Leave a marker, or the probe chain breaks
Load factor — Can pass 1.0; chains just grow — Must stay below 1.0; performance falls sharply near full
Who uses it — Java HashMap, which turns a chain into a red-black tree when a new entry is added to a chain that already holds 8 and the table has at least 64 buckets — CPython dict, which probes with a perturbed sequence and resizes at two thirds full

Load factor and resize

The load factor is size / capacity: the average chain length. Keeping it below a threshold keeps chains short. When a put pushes the load factor over the threshold, the map doubles the bucket array and moves every entry into its new bucket. The index depends on the capacity, so nothing can stay where it was without being recomputed.

The trace below runs the code on a map with 4 buckets and a load factor of 0.75, so the fourth new key forces a resize. Small integers hash to themselves in CPython, which makes the indexes easy to follow.

1 — put(1, 'a') — 1 — 1 — 0.25 — new chain in bucket 1
2 — put(5, 'b') — 1 — 2 — 0.50 — collision; added at the head of bucket 1
3 — put(9, 'c') — 1 — 3 — 0.75 — collision; chain is now 9, 5, 1
4 — put(5, 'B') — 1 — 3 — 0.75 — update in place; no resize
5 — put(2, 'd') — 2 — 4 — 1.00 — over 0.75, so capacity doubles to 8
after — rehash — 1 to 1, 5 to 5, 9 to 1, 2 to 2 — 4 — 0.50 — the old chain of three is split

Java's documentation says the default load factor of 0.75 is a good trade between time and space: a higher value saves memory but makes get and put slower.

Complexity

get — O(1) — O(n) — Every key in one chain: a bad hash function, or an attacker who chose the keys
put (no resize) — O(1) — O(n) — Same chain walk to check for an existing key
put (with resize) — O(n) once, O(1) amortized — O(n) — Doubling means each entry is moved at most log n times in total
remove — O(1) — O(n) — Chain walk to find the node and its predecessor
Memory — O(n + capacity) — One node per entry plus the bucket array

Thread safety

The code below is not safe for concurrent writers, and neither are java.util.HashMap or a plain Python class. A resize that runs while another thread inserts can lose entries. Say this before the interviewer asks, then offer the options.

One lock — Every public method takes the same lock — Simple and correct; all threads serialize
Striped locks — An array of locks; hash % stripes picks one, so different buckets proceed in parallel — Resize must take every stripe; more code
Java ConcurrentHashMap — Reads do not lock at all and may overlap with writes; writers lock as little as needed — The library answer; it refuses null keys and values

What you will be able to do

Explain the three parts (hash function, bucket array, chains) and trace a put from key to bucket.
Write chaining with head insertion, in-place update and a correct remove, and test it with forced collisions.
State the load factor rule, show why every entry is rehashed on resize, and argue that resizing is O(1) amortized.
Compare chaining with open addressing and name which real maps use each.
Describe how to make the map thread-safe, from one lock to striped locks to ConcurrentHashMap.

Functional requirements

put(key, value) inserts a new entry or replaces the value of an existing key without creating a duplicate
get(key, default) returns the value, or the default when the key is absent
remove(key) deletes the entry and returns True, or returns False when the key is absent
The map grows: when size / capacity passes the load factor, capacity doubles and every entry is rehashed
Collisions are handled by chaining: each bucket is a linked list of entries
Any hashable key is accepted; an unhashable key raises TypeError

Non-functional requirements

get, put and remove run in O(1) time on average, with resize O(1) amortized
Worst case O(n) when every key lands in one chain
Memory is O(n + capacity): one entry node per key plus the bucket array
Initial capacity and load factor are constructor arguments with sensible defaults (16 and 0.75)

Interview questions

Why did you choose chaining over open addressing?
Why does resize have to rehash every entry, and why is it still O(1) amortized?
How would you make this map safe for many threads?
What makes a key a good key, and what goes wrong with a bad one?
What bugs do people write in this problem, and how do you catch them?