Lesson 14
Hash Tables: O(1) Lookup by Magic Math
Turn any key into an array index — and handle the collisions that follow.
01Why it matters & the intuition
Hash tables (JS Map/Set, Python dict) are the single most common tool for turning an O(n²) solution into O(n). Caches, database indexes and compilers all rely on them.
Think of it like…
A library where the shelf for each book is computed from its title: add up the letters, take the remainder by the number of shelves. You walk straight to the shelf. Two titles landing on the same shelf is a collision — so each shelf holds a short list.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- target bucket
- found / inserted
- missing
03Key ideas
Hash function
Maps a key to an integer, then % capacity to a bucket index. Good hashes spread keys evenly and are deterministic.
Collisions: chaining
Each bucket holds a small list of [key, value] pairs. Lookup hashes to the bucket, then scans that short list.
Load factor
size / capacity. When it passes ~0.75, double the capacity and re-insert everything (rehash) to keep chains short.
Worst case
If every key collides, one bucket holds everything and operations degrade to O(n). Good hashing makes that astronomically unlikely.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class HashMap<V> {
private buckets: [string, V][][];
private count = 0;
constructor(private capacity = 8) {
this.buckets = Array.from({ length: capacity }, () => []);
}
// djb2-style string hash
private hash(key: string): number {
let h = 5381;
for (let i = 0; i < key.length; i++) h = (h * 33 + key.charCodeAt(i)) >>> 0;
return h % this.capacity;
}
set(key: string, value: V): void {
const bucket = this.buckets[this.hash(key)];
const entry = bucket.find(([k]) => k === key);
if (entry) { entry[1] = value; return; }
bucket.push([key, value]);
this.count++;
if (this.count / this.capacity > 0.75) this.rehash();
}
get(key: string): V | undefined {
return this.buckets[this.hash(key)].find(([k]) => k === key)?.[1];
}
delete(key: string): boolean {
const bucket = this.buckets[this.hash(key)];
const i = bucket.findIndex(([k]) => k === key);
if (i === -1) return false;
bucket.splice(i, 1);
this.count--;
return true;
}
private rehash(): void {
const old = this.buckets.flat();
this.capacity *= 2;
this.buckets = Array.from({ length: this.capacity }, () => []);
this.count = 0;
for (const [k, v] of old) this.set(k, v);
}
}05Complexity
| Operation | Time | Space |
|---|---|---|
| get / set / delete (average) | O(1) | — |
| get / set / delete (worst) | O(n) | — |
| Rehash | O(n) | O(n) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Two Sum
Write two_sum(nums, target) returning the indices [i, j] (i < j) of the two numbers that add up to target. Exactly one answer exists. Aim for O(n).