HashingData structureaka collision resolution, hash collision

Collision Handling

Strategies for storing two keys whose hashes map to the same bucket without losing either.

▶ Visualize Pattern: Hashing Practice (1)

Progress

Definition

A hash function maps an unbounded key space into m buckets, so by the pigeonhole principle collisions are inevitable: with just 23 random keys in 365 buckets the probability of a collision already exceeds 50% (the birthday paradox). A hash table is therefore defined as much by its collision strategy as by its hash function.

The two families are separate [[chaining]] — each bucket holds a secondary container (linked list, dynamic array, or tree) of all keys that hash there — and [[open-addressing]] — all keys live in the bucket array itself and a collision triggers a probe sequence to find another free slot.

Secondary techniques reduce how often collisions happen: better hash functions (multiplicative, FNV, SipHash), prime or power-of-two capacities with bit mixing, random seeds against hash flooding, and keeping the load factor below a threshold via resizing.

hash tablechainingopen addressingload factorpigeonhole

Intuition

A mental model before the formal terms.

Two people are assigned the same locker. Chaining: they share it, and each hangs a name tag on their bag so you know whose is whose. Open addressing: the second person is told "try the next locker, and the one after that, until you find an empty one" — and everyone looking for them must follow the same trail.

The load factor is how crowded the locker room is. At 50% occupancy the trail is short; at 95% almost every locker is taken and every search wanders far.

How it works

Compute idx = hash(key) mod m.
Chaining: append (key, value) to the list at buckets[idx]; lookups scan that list comparing keys.
Open addressing: if slot[idx] is occupied by a different key, compute the next probe index — linear (idx + 1), quadratic (idx + i²), or double hashing (idx + i · h2(key)) — until an empty slot or the key is found.
Deletion under open addressing leaves a tombstone so probe chains passing through the slot remain intact.
Both families resize when n / m exceeds a threshold, rehashing every entry into a larger array; open addressing must resize earlier (≈0.5–0.7) than chaining (≈0.75–1.0).

Why it works

Under simple uniform hashing the expected number of keys sharing a bucket is α = n / m. Chaining then costs O(1 + α) per operation; linear probing costs roughly (1 + 1/(1-α)²)/2 probes for an unsuccessful search, which is small for α ≤ 0.5 and explodes as α → 1.

Resizing keeps α bounded by a constant, so both strategies achieve expected O(1) per operation.

Operations

Operation	Description	Cost
insert on collision	Chain: append to bucket list. Open: probe to the next free slot.	O(1 + α) expected
lookup on collision	Chain: scan bucket list. Open: follow the probe sequence.	O(1 + α) expected
delete on collision	Chain: unlink node. Open: mark tombstone.	O(1 + α) expected
rehash	Rebuild into a larger table when α exceeds the threshold.	O(n)

Recognition

How to tell a problem wants this.

The interviewer asks "what happens when two keys hash to the same index?" or "how would you implement a hash map?".
Design questions mention load factor, rehashing, or worst-case behaviour of a hash table.
System design questions about cache locality or memory footprint of a dictionary.

“have you seen this before” → Hashing

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Hash Table visualization.

Commands — insert N, search N, delete N — m = 7 buckets, hash = key % 7

∅

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

bucket 4

∅

bucket 5

∅

bucket 6

∅

1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.

Hashed bucketChain node comparedMatchInserted / removed

PseudocodeLearn Hash Table →

1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node

Variables

size0

load0.00

Complexity

access O(1)

search O(1)

insert O(1)

delete O(1)

Speed

Pseudocode

1insert(key, value):
2  idx = hash(key) mod m
3  if strategy == CHAINING: buckets[idx].append((key, value))
4  else:  # open addressing
5    i = 0
6    while slots[probe(idx, i)] is occupied and slots[probe(idx, i)].key != key: i++
7    slots[probe(idx, i)] = (key, value)
8  if n / m > maxLoad: rehash into 2m slots

Implementation

1from typing import Optional
2 
3# Representative example: the same three keys inserted into a table with
4# chaining and a table with linear probing, to show how each resolves collisions.
5 
6 
71 · Deliberately weak hash (first character) to force collisions
8def weak_hash(key: str, cap: int) -> int:
9    return ord(key[0]) % cap if key else 0
10 
11 
122 · Chaining: each bucket is a list
13class Chained:
14    def __init__(self, cap: int) -> None:
15        self.buckets: list[list[str]] = [[] for _ in range(cap)]
16 
17    def insert(self, k: str) -> None:
18        self.buckets[weak_hash(k, len(self.buckets))].append(k)
19 
20    def contains(self, k: str) -> bool:
21        return k in self.buckets[weak_hash(k, len(self.buckets))]
22 
23 
243 · Open addressing: probe the next slot on collision
25class Probing:
26    def __init__(self, cap: int) -> None:
27        self.slots: list[Optional[str]] = [None] * cap
28 
29    def insert(self, k: str) -> None:
30        i = weak_hash(k, len(self.slots))
31        while self.slots[i] is not None and self.slots[i] != k:
32            i = (i + 1) % len(self.slots)
33        self.slots[i] = k
34 
35    def contains(self, k: str) -> bool:
36        i = weak_hash(k, len(self.slots))
37        for _ in range(len(self.slots)):
38            if self.slots[i] is None:
39                return False
40            if self.slots[i] == k:
41                return True
42            i = (i + 1) % len(self.slots)
43        return False
44 
45 
464 · Drive both with colliding keys
47c, p = Chained(8), Probing(8)
48for k in ["apple", "avocado", "apricot"]:
49    c.insert(k)
50    p.insert(k)
51print(len(c.buckets[weak_hash("apple", 8)]), "keys in one chain")
52print(c.contains("avocado"), p.contains("avocado"), p.contains("banana"))

Walkthrough

Conceptual topic: one representative example where weak_hash collides on the first character.
Chained.contains uses in on the bucket list — a linear scan of the chain.
Probing.insert advances with modulo wraparound until it finds None or the same key.
Probing.contains is bounded by len(self.slots) and stops at the first None.
The driver prints 3 keys in one chain and the membership results.

Complexity (this implementation)

time O(1 + α) average per operation · space O(n + capacity)

Language notes

CPython dict uses open addressing with a pseudo-random probe sequence (i = 5*i + perturb + 1), not linear probing.
[None] * cap is fine for immutable fillers; [[]] * cap would alias one list.
Dict resizes at 2/3 load to keep probe sequences short.

Common mistakes in this language

Using [[]] * cap for chained buckets.
Testing if self.slots[i] — an empty-string key would look like an empty slot; use is None.
Deleting from the probing table by setting None.

Language differences that matter here

Built-in strategy: C++ unordered_map uses chaining; CPython dict and V8 Map use open addressing.
Empty-slot markers: C++ needs a sentinel or std::optional; JS/TS use null; Python uses None with is comparison.
Bucket introspection: C++ exposes bucket_count/bucket_size; Python and JS hide their tables entirely.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(n)
Search	O(1 + α)	O(n)	α = n / m is the load factor.
Insert	O(1 + α)	O(n)
Delete	O(1 + α)	O(n)
Update	O(1 + α)	O(n)
Rehash	O(n)	O(n)
Space	O(n + m)		Chaining adds a pointer per entry; open addressing adds empty slots to keep α low.

Advantages & disadvantages

Advantages

A good strategy keeps the expected cost O(1) even though collisions are guaranteed.
Chaining is simple and robust at high load; open addressing is compact and cache-friendly.
Resizing policies make the bounds hold amortized without user intervention.

Disadvantages

Worst case remains O(n) when many keys collide (bad hash, adversarial input).
Chaining costs pointer memory; open addressing suffers clustering and needs tombstone cleanup.
Choosing the load-factor threshold trades memory against probe length.

Use cases

Every hash table implementation: HashMap, dict, unordered_map, Go map.
Choosing between chaining (Java, C++) and open addressing (Python, Go, Rust, Swiss tables) for a custom high-performance map.
Understanding why hash tables degrade under hash-flooding attacks and how seeded hashes prevent it.

Use it when

Always — every hash table needs one; the decision is which strategy.
Use chaining when deletions are frequent, load may exceed 1, or keys/values are large objects.
Use open addressing when memory locality matters and entries are small (integers, pointers).

Avoid it when

If keys are a small dense integer range, direct addressing needs no collision handling at all.
If the key set is static and known up front, a perfect hash function eliminates collisions.

Alternatives

Separate Chaining Open Addressing Array Trie

Common mistakes

Ignoring collisions entirely and overwriting the slot, silently losing data.
Deleting under open addressing by clearing the slot, which breaks every probe chain that passed through it.
Using hash % m with m a power of two and a hash whose low bits are poorly mixed (e.g. pointer addresses), so most keys share a few buckets.
Letting the load factor grow past ~0.9 with linear probing; probe lengths become quadratic in practice.

Interview patterns

"Design a hash map" follow-ups: explain chaining vs. open addressing, load factor, and rehashing.
"What is the worst case of a hash map lookup and how does Java mitigate it?" — treeified bins at chain length 8.
"Why does Python resize at 2/3 full?" — open addressing probe cost grows quickly past that.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Average case versus worst caseIntermediate

Mock interviews

Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate
Subarray Sum Equals KIntermediate

Interview problems

Design HashMapeasy

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related