Hash Lookup
Compute where the key lives instead of searching for it — expected O(1) no matter how large the table grows.
Hands on Interactive visualization
Implementation Code
// Idiomatic TS: Map is a hash table.
export function lookup(m: Map<string, number>, key: string) {
return m.get(key); // expected O(1)
}
// Under the hood: linear probing in an open-addressed table.
export function probe(
slots: ({ key: string; value: number } | null)[],
key: string,
hash: (k: string) => number,
): number | undefined {
const n = slots.length;
let i = hash(key) % n; // home slot computed from the key
for (let tries = 0; tries < n; tries++) {
const slot = slots[i];
if (slot === null) return undefined; // never inserted
if (slot.key === key) return slot.value;
i = (i + 1) % n; // collision: step to the next slot
}
return undefined;
}Big-O Complexity
Expected O(1) holds only while the load factor stays bounded and the hash function spreads keys well; heavy collisions (or an adversarial key set) degrade a single bucket to O(n). Tables resize — typically doubling around a 0.5–0.75 load factor — to keep probes short.
In production When to use
Python dict, Go map, Java HashMap, JavaScript Map/objects, Rust HashMap — the default associative container in virtually every language is a hash table, because equality lookup is the dominant query.
In-process caches, LRU layers, and memoized function results key on input → output pairs; hash lookup makes the have we seen this before? check constant time, which is the whole point of caching.
Compilers and interpreters resolve identifiers to declarations through hash-based symbol tables — every variable reference in every function is a hash lookup during compilation.
PostgreSQL hash indexes and in-memory engines use hashing for pure equality predicates (WHERE id = ?), trading away range-scan ability for O(1) point lookups.
Hash sets answer already processed? for stream dedup, visited tracking in graph algorithms, and unique-constraint checks — one lookup and one insert per element, O(n) for the whole stream.
Load balancers and distributed stores hash a key to pick a shard or node (consistent hashing) — the same compute the location instead of searching idea, applied across machines.
Trade-offs Strengths & weaknesses
- Expected O(1) lookup, insert, and delete — independent of table size.
- No ordering precondition: keys can arrive in any order and be any hashable type.
- Not comparison-based, so it sidesteps the O(log n) lower bound that binds ordered search.
- Simple mental contract: same key in, same slot out.
- Backed by battle-hardened stdlib implementations everywhere — you rarely write one yourself.
- Worst case O(n) when many keys collide — bad hash functions or adversarial inputs (hash-flooding DoS) matter.
- No order: range queries, nearest-key, and sorted iteration are impossible without a separate structure.
- O(n) memory with real overhead — empty slots (open addressing) or node pointers (chaining) on top of the data.
- Resizing is an O(n) stop-the-world rehash unless amortized incrementally.
- Performance is sensitive to load factor and hash quality — tuning knobs an array or tree simply doesn't have.
- Keys must be immutable while in the table, or lookups silently break.
Intuition Mental model
The coat-check ticket
A coat check doesn't search racks for your coat — your ticket number IS the rack position. Hashing turns a key into its own ticket: compute the number, walk straight to that hook, done — whether the room holds ten coats or ten thousand.
- Handing over your coat = insert: the attendant computes a ticket number (hash) and hangs the coat on exactly that hook.
- Returning with the ticket = lookup: same number, same hook, one step — no scanning the racks.
- Two coats assigned the same hook = collision: the attendant hangs them together and checks tags (chaining), or uses the next free hook (probing).
- A cramped room where every hook holds five coats = high load factor: time to move to a bigger room and re-hang everything (resize + rehash).
- Swapping your coat for a different one but keeping the old ticket = mutating the key: the ticket now points at the wrong thing.
Prep Interview questions
Design a hash map from scratch. What are the two collision strategies and their trade-offs?
Two Sum in O(n) — how, and why is a hash map the key?
Why does a HashMap lookup break if you mutate a key after inserting it?
What is hash flooding, and how do real implementations defend against it?
When would you pick a balanced BST (TreeMap) over a hash map?
Watch out Common bugs
The entry stays in the slot chosen by its old hash, so future lookups miss it — no error, just a value that has effectively vanished. Use immutable keys, or remove-mutate-reinsert.
Hashing only part of the key, returning constants, or mapping to indexes with a biased modulo piles keys into a few buckets and quietly turns O(1) into O(n). Test bucket distribution on realistic key sets.
Simply emptying a slot breaks every probe chain that passed through it — later keys become unreachable. Mark deleted slots with a tombstone (or re-insert the tail of the cluster) so probes keep walking.
A fixed-capacity table filling toward 100% makes probe sequences (or chains) grow without bound; open addressing at full capacity can even loop forever on a miss. Track load factor and grow-and-rehash past a threshold like 0.7.
One screen Cheat sheet
Hash the key to compute its slot directly — the address is derived, not discovered.
- Not comparison-based — the only search here that beats the O(log n) comparison lower bound.
- O(1) is expected, not guaranteed: it depends on hash quality and a bounded load factor.
- Collisions are handled by chaining (lists per bucket) or open addressing (probe sequences).
- Open-addressing deletion needs tombstones; resize/rehash kicks in around 0.5–0.75 load.
- Keys must be immutable and hashCode/equals must agree.
- No order: reach for a BST or sorted array when you need ranges or sorted iteration.