CS 10C — Hashing is just finding parking, but with math
Separate Chaining
The Parking Analogy: Forget single parking spots — every index is a valet line.
Your GPS says "go to lane #3." You pull up, and the valet stacks your car behind
any cars already waiting there. Need to find your car? Walk down lane #3 checking each one.
The lane can grow as long as it needs to — no one gets turned away.
But if one lane gets really long, it's basically a slow linked list. So we
resize the lot (double the lanes) when the average lane length exceeds 1.
Each bucket is a linked list. Load factor L = N/M can exceed 1.0.
Resize when L > 1. Search/insert/delete are O(1 + L) on average.
Operation Log
Linear Probing — f(i) = i
The Parking Analogy: Your GPS says "go to spot #3." You drive there — it's taken.
So you inch forward: spot #4? Taken. Spot #5? Taken. Spot #6? Empty! You park.
That's linear probing — you just keep rolling forward one spot at a time.
The downside? Cars start piling up in long rows (primary clustering).
The more cars in a row, the harder it is for the next car to find a spot nearby.
Operation Log
Quadratic Probing — f(i) = i²
The Parking Analogy: Your GPS says spot #3. Taken!
Instead of inching forward, you skip further each try:
try 1 spot ahead, then 4 ahead, then 9 ahead, then 16...
It's like getting increasingly frustrated and driving further away each time.
The upside? You break up clusters by scattering to different parts of the lot.
The catch? You might circle the lot without checking every spot (guaranteed to find one only if table is less than half full and size is prime).
Probe formula:h_i(x) = (hash(x) + i²) mod M
→ offsets: +0, +1, +4, +9, +16, +25, ...
Probe Offsets Visualized
Operation Log
Double Hashing — f(i) = i · h₂(k)
The Parking Analogy: Your GPS says spot #3. Taken!
Now here's the twist — your license plate number determines how far you skip each time.
A Honda might skip by 3 spots, a Tesla by 7, a Jeep by 5.
Every car has its own unique skip pattern, so cars with the same GPS target
spread out in completely different ways. Maximum chaos = minimum clustering.
Probe formula:h_i(x) = (h₁(x) + i · h₂(x)) mod M where h₂(x) = R - (x mod R) and R is a prime < M.
The step size h₂ is different for each key.
Step Sizes by Key
Operation Log
Cuckoo Hashing — Two Tables, One Eviction Policy
The Parking Analogy: Imagine two parking lots side by side.
Your GPS gives you one spot in Lot A and one in Lot B (different formulas).
You try Lot A first. If taken, you kick out the parked car and take its spot.
The evicted car drives to its alternative spot in the other lot.
If that's taken, it kicks that car out, and so on — a chain of evictions
until someone finds an empty spot. Like a game of parking-lot musical chairs.
If the chain goes on too long (a cycle), everyone gets new GPS coordinates (rehash).
Lookup is always O(1) — just check one spot in each table.
Delete is O(1) — remove from whichever table has it.
Insert is amortized O(1) but can trigger eviction chains.
Uses: h₁(x) = x mod M and h₂(x) = ⌊x / M⌋ mod M
Table 1 — h₁(x) = x mod M
Table 2 — h₂(x) = ⌊x/M⌋ mod M
Operation Log
Deletion in Open Addressing — The Rehash Problem
The Parking Analogy: Cars are parked in a row: spots 0, 1, 2, 3.
You know the rule: "drive forward until you find an empty spot — that means the car you're looking for isn't here."
Now a car leaves spot 1. There's a gap.
A friend looking for the car in spot 2 drives past spot 0 (wrong car), sees spot 1 is empty,
and gives up — "must not be here." But it IS here, in spot 2!
The fix: when a car leaves, all the cars after it in the row re-park themselves
from scratch. That way there's never a misleading gap.
Step-by-Step Walkthrough
Probing Showdown — Side-by-Side Comparison
The Parking Analogy: Three drivers arrive at the same lot, each using a different strategy.
Linear driver inches forward. Quadratic driver skips farther each time.
Double-hash driver's skip distance depends on their plate number.
Same cars, same lot, very different parking patterns. Red = cluster of 3+ cars in a row.
Tip: Probing strategies only differ when collisions happen.
If the table is too big relative to the keys, there are few collisions and the results look identical.
Use the presets below, or keep the load factor high (but < 0.5 for quadratic probing to work).
Quadratic probing caveat: it only visits a subset of indices — if the table
is more than half full, it may cycle without finding an empty slot even if one exists.