Collision Handling
A collision occurs when two different keys hash to the same bucket index. No matter how good your hash function is, collisions are mathematically inevitable once the number of keys exceeds the number of buckets.
Understanding how to handle collisions efficiently is what separates a toy hash table from a production-grade one.
Why Collisions Are Inevitable — The Birthday Paradox
The birthday paradox says that in a group of just 23 people, there is a greater-than-50% chance that two people share a birthday — even though there are 365 possible birthdays.
The math: if you insert n keys into a table with m buckets, the probability of at
least one collision is approximately:
P(collision) ≈ 1 - e^(-n²/(2m))
For m = 1000 buckets:
- n = 50 keys → ~71% chance of at least one collision.
- n = 100 keys → ~99% chance.
The takeaway: collisions happen frequently even with a great hash function. Your collision-handling strategy determines the real-world performance of your hash table.
Strategy 1 — Separate Chaining
Each bucket holds a linked list (or small dynamic array) of all key-value pairs that hash to that bucket.
- Insert: hash the key, append to the bucket's list.
- Lookup: hash the key, scan the bucket's list for the matching key.
- Delete: hash the key, remove the matching node from the list.
When the load factor α = n/m is low (< ~1.0), each bucket's list has O(1) entries on average, so all operations are O(1) amortised.
class HashMap {
constructor(capacity = 16) {
this.capacity = capacity;
this.buckets = Array.from({ length: capacity }, () => []);
this.size = 0;
}
_hash(key) {
// Simple polynomial hash for string keys
let h = 0;
for (let i = 0; i < key.length; i++) {
h = (h * 31 + key.charCodeAt(i)) % this.capacity;
}
return h;
}
set(key, value) {
const idx = this._hash(key);
const bucket = this.buckets[idx];
for (const entry of bucket) {
if (entry[0] === key) { entry[1] = value; return; } // update
}
bucket.push([key, value]); // new entry
this.size++;
if (this.size / this.capacity > 0.75) this._rehash();
}
get(key) {
const bucket = this.buckets[this._hash(key)];
for (const [k, v] of bucket) if (k === key) return v;
return undefined;
}
has(key) { return this.get(key) !== undefined; }
delete(key) {
const idx = this._hash(key);
const bucket = this.buckets[idx];
const i = bucket.findIndex(([k]) => k === key);
if (i === -1) return false;
bucket.splice(i, 1);
this.size--;
return true;
}
_rehash() {
const old = this.buckets;
this.capacity *= 2;
this.buckets = Array.from({ length: this.capacity }, () => []);
this.size = 0;
for (const bucket of old) {
for (const [k, v] of bucket) this.set(k, v);
}
}
}
const map = new HashMap();
map.set('hello', 1);
map.set('world', 2);
console.log(map.get('hello')); // 1
map.delete('hello');
console.log(map.has('hello')); // falseStrategy 2 — Open Addressing
Instead of a linked list, all entries live inside the bucket array itself. On collision, a probe sequence finds the next available slot.
There are three common probe strategies:
Linear Probing
On collision at index i, try i+1, i+2, i+3, … (wrapping around).
Simple to implement, excellent cache performance, but suffers from primary clustering —
long runs of occupied buckets form, making future insertions slower.
class HashMapLinear {
constructor(capacity = 16) {
this.cap = capacity;
this.keys = new Array(capacity).fill(null);
this.vals = new Array(capacity).fill(null);
this.size = 0;
this.TOMB = Symbol('TOMBSTONE'); // marks deleted slots
}
_hash(key) {
let h = 0;
for (let i = 0; i < key.length; i++) h = (h * 31 + key.charCodeAt(i)) % this.cap;
return h;
}
set(key, value) {
if (this.size / this.cap > 0.5) this._rehash();
let i = this._hash(key);
while (this.keys[i] !== null && this.keys[i] !== this.TOMB) {
if (this.keys[i] === key) { this.vals[i] = value; return; }
i = (i + 1) % this.cap; // linear probe
}
this.keys[i] = key;
this.vals[i] = value;
this.size++;
}
get(key) {
let i = this._hash(key);
while (this.keys[i] !== null) {
if (this.keys[i] === key) return this.vals[i];
i = (i + 1) % this.cap;
}
return undefined;
}
delete(key) {
let i = this._hash(key);
while (this.keys[i] !== null) {
if (this.keys[i] === key) {
this.keys[i] = this.TOMB; // tombstone, don't break probe chains
this.size--;
return true;
}
i = (i + 1) % this.cap;
}
return false;
}
_rehash() {
const oldKeys = this.keys, oldVals = this.vals;
this.cap *= 2;
this.keys = new Array(this.cap).fill(null);
this.vals = new Array(this.cap).fill(null);
this.size = 0;
for (let i = 0; i < oldKeys.length; i++) {
if (oldKeys[i] !== null && oldKeys[i] !== this.TOMB) {
this.set(oldKeys[i], oldVals[i]);
}
}
}
}Quadratic Probing
Probe at i + 1², i + 2², i + 3², …
This reduces primary clustering (the long consecutive runs that plague linear probing) but can cause secondary clustering — all keys that hash to the same initial index follow the same probe sequence.
For quadratic probing to visit every slot, the capacity must be a prime number and the load factor must stay below 0.5.
// Quadratic probe function (inside the set/get loops)
// Replace the linear probe line with:
// i = (startIdx + step * step) % cap; ++step;
function quadraticProbe(startIdx, step, capacity) {
return (startIdx + step * step) % capacity;
}
// Example walk for key hashing to slot 3, capacity = 11
// step=0: slot 3
// step=1: (3 + 1) % 11 = 4
// step=2: (3 + 4) % 11 = 7
// step=3: (3 + 9) % 11 = 1
// step=4: (3 + 16) % 11 = 8 ...Double Hashing
Use a second hash function to determine the step size:
probe(i, step) = (h1(key) + step * h2(key)) % capacity
where h2(key) must never return 0. A common choice: h2(key) = prime - (h1(key) % prime).
Double hashing eliminates both primary and secondary clustering — each key gets its own unique probe sequence. It is the most sophisticated open-addressing scheme and performs closest to theoretical optimum.
function h1(key, cap) {
let h = 0;
for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % cap;
return h;
}
// h2 must be coprime to cap; cap should be prime
function h2(key, cap) {
const PRIME = cap - 1; // works when cap is prime
let h = 0;
for (const ch of key) h = (h * 37 + ch.charCodeAt(0)) % PRIME;
return h + 1; // ensure h2 > 0
}
function doubleHashProbe(key, step, cap) {
return (h1(key, cap) + step * h2(key, cap)) % cap;
}
// For key "hello", cap = 11:
// step 0: h1("hello", 11)
// step 1: h1("hello", 11) + h2("hello", 11)
// step 2: h1("hello", 11) + 2 * h2("hello", 11)
// ...each key follows a uniquely-spaced sequenceLoad Factor and Rehashing
The load factor α = n / m (entries / buckets) governs performance:
- Separate chaining: best kept below 1.0; above 2–3 lookup degrades noticeably.
- Open addressing: must stay below 0.5–0.7; at 1.0 the table is full and insert loops forever.
When α exceeds the threshold, allocate a new array (usually 2× size), pick a prime near 2× old size, and re-insert every existing entry. This is O(n) but happens at most O(log n) times as the table grows, giving O(1) amortised per insert.
Comparison Table
Property | Separate Chaining | Linear Probing | Quadratic Probing | Double Hashing |
|---|---|---|---|---|
Memory layout | Scattered (linked list) | Contiguous | Contiguous | Contiguous |
Cache friendliness | Poor | Excellent | Good | Good |
Clustering | None | Primary clustering | Secondary clustering | None |
Load factor limit | < 1.0–2.0 | < 0.5–0.7 | < 0.5 (prime cap) | < 0.7 (prime cap) |
Delete complexity | Simple list removal | Tombstone required | Tombstone required | Tombstone required |
Implementation | Easy | Easy | Medium | Harder |
Practical speed | Good | Best (cache wins) | Medium | Best (no clustering) |
Practice Problems
LeetCode 706 — Design HashMap (implement from scratch)
LeetCode 705 — Design HashSet (implement from scratch)
LeetCode 380 — Insert Delete GetRandom O(1) (HashMap + array)
LeetCode 381 — Insert Delete GetRandom O(1) — Duplicates allowed