Part 1 · Concepts · Hash tables
Hash map
Stores key to value pairs with O(1) average lookup, insert and delete.
How it works
A hash function turns the key into a number, and modulo the array size picks a bucket. Two keys can land in the same bucket (a collision), so each bucket holds a short list (chaining). When the table gets more than about 75% full, it doubles and rehashes everything, so chains stay short. That resize is O(n), but it happens rarely, so the average cost per insert stays O(1) (amortized).
| get / set / delete | O(1) average, O(n) worst (everything collides) |
| resize | O(n), rare, amortized O(1) |
| iterate | O(n) |
Reach for it when
- Have I seen this before?
- Count things
- Look up by id
- Group by a key
- Cache results (memoize)
Implementation (JavaScript, tested)
class HashMap {
buckets;
size = 0;
constructor(capacity = 8) {
this.buckets = Array.from({ length: capacity }, () => []);
}
index(key, cap = this.buckets.length) {
let h = 2166136261; // FNV-1a: mix every char into the hash
for (let i = 0; i < key.length; i++) {
h ^= key.charCodeAt(i);
h = Math.imul(h, 16777619);
}
return (h >>> 0) % cap;
}
set(key, value) {
const bucket = this.buckets[this.index(key)];
const hit = bucket.find(e => e[0] === key);
if (hit) {
hit[1] = value;
return;
}
bucket.push([key, value]);
if (++this.size / this.buckets.length > 0.75) this.resize(); // keep chains short
}
get(key) {
return this.buckets[this.index(key)].find(e => e[0] === key)?.[1];
}
delete(key) {
const bucket = this.buckets[this.index(key)];
const i = bucket.findIndex(e => e[0] === key);
if (i < 0) return false;
bucket.splice(i, 1);
this.size--;
return true;
}
resize() {
const old = this.buckets.flat();
this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);
for (const [k, v] of old) this.buckets[this.index(k)].push([k, v]); // rehash everything
}
get capacity() {
return this.buckets.length;
}
}Traps
- Plain objects as maps: keys become strings, and there are prototype keys. Use Map.
- Map compares object keys by reference, not by value. Use a string key like `${r},${c}`.
- Worst case O(n) is real: attackers can force collisions (hash flooding), which is why languages use seeded hashes.
In real systems: JS Map and Set. Redis is one big hash table, and Redis hashes (HSET) are maps inside it. Databases use hash joins and hash indexes.
Say out loud: Average O(1) because the hash spreads keys across buckets and the table resizes to keep chains short. Worst case O(n) if everything collides.