Hash function — properties - deterministic, uniform, fast: Visual walkthrough

This is the picture-by-picture derivation behind the parent topic. If a word here is unfamiliar, it gets a figure before it gets a formula.

Step 1 — What a hash function physically does

WHAT. Imagine a long shelf of numbered boxes: box $0$ , box $1$ , up to box $m - 1$ . A key is any thing you want to store — a word, a number, a name. A hash function is just a rule that reads the key and points at exactly one box.

WHY. Before we can talk about "even spreading", we need a picture of the machine doing the placing. Everything later is about how full each box gets.

PICTURE. In the figure below, three keys ("cat", "dog", "fox") enter the machine $h$ and each comes out pointing at one box. The machine is a black box for now — we only care that each key gets one box.

Figure — Hash function — properties - deterministic, uniform, fast

Step 2 — "Uniform" means every box is equally likely

WHAT. We now name the good behaviour. A hash is uniform when a key is just as likely to land in box $0$ as box $1$ as any other box. No box is a favourite.

WHY. The whole speed argument collapses if some box is a magnet that swallows most keys. Uniformity is the assumption that makes "the average box" actually representative.

PICTURE. The bar chart below compares a bad hash (one tall bar — a magnet box) against a uniform hash (all bars roughly level). We will only be able to prove fast lookups for the level picture.

Step 3 — Focus on ONE box and ask "how many keys landed here?"

WHAT. Pick a single box, say box $j$ . We want to count how many of our $n$ keys fell into it.

WHY. A lookup that lands in box $j$ must walk through everything sitting in box $j$ . So the cost of a lookup is decided by how crowded a single box is — not by the whole table. That is why we zoom in on one box.

PICTURE. Below, box $j$ is highlighted. Each of the $n$ incoming keys either falls in box $j$ (arrow into the box) or misses it (arrow elsewhere). We are about to count only the "in" arrows.

Step 4 — Turn the counting into a switch (the indicator)

WHAT. For each key $i$ (numbered $1$ to $n$ ) we invent a tiny switch $X_{i}$ : $X_{i} = {10 if key i landed in box j if it did not$

WHY. Counting "how many landed in box $j$ " is awkward. But if each key carries a switch that is $1$ when it's in the box and $0$ otherwise, then adding up all the switches gives the count automatically. This trick — turning a yes/no question into a $1/0$ number — is why the algebra becomes easy.

PICTURE. Each incoming key gets a little tag: green tag $= 1$ (it's in box $j$ ), grey tag $= 0$ (it missed). The total inside box $j$ is just the sum of the green tags.

So each switch has average value: $E [X_{i}] = P (h (k_{i}) = j) = \frac{1}{m}$

$E [X_{i}]$ = the average value of key $i$ 's switch.
$\frac{1}{m}$ = comes straight from Step 2's uniformity — that's why we needed uniform.

Step 5 — Add the switches: linearity of expectation

WHAT. The number of keys in box $j$ is the sum of all switches, and its average is: $E [\sum_{i = 1}^{n} X_{i}] = \sum_{i = 1}^{n} E [X_{i}] = \sum_{i = 1}^{n} \frac{1}{m} = \frac{n}{m}$

WHY. There is a beautiful rule called linearity of expectation: the average of a sum is the sum of the averages — always, even when the switches influence each other. That is what lets us slide the $E$ inside the sum. We add $\frac{1}{m}$ a total of $n$ times, giving $\frac{n}{m}$ .

PICTURE. The figure stacks $n$ copies of the value $\frac{1}{m}$ into one bar of height $\frac{n}{m}$ — the average crowd size of a box.

Step 6 — From crowd size to lookup cost

WHAT. A lookup does two things: (1) run $h (k)$ once to find the box, then (2) walk through the keys inside that box comparing them. Step 5 says the box holds about $α$ keys on average. So: $search cost = O (1 + α)$

WHY each piece.

The $1$ = computing $h (k)$ — a single fast calculation (this is the fast property from the parent).
The $α$ = walking the average chain of $α$ keys (this is the separate-chaining list inside the box).

PICTURE. A lookup arrow jumps instantly to box $j$ (cost $1$ ), then hops down a short chain of $\approx α$ links (cost $α$ ).

Step 7 — The edge cases (where the story could break)

WHAT & WHY. A derivation you can trust must survive its extremes. Below every limiting case is checked against the same formula $cost = O (1 + α)$ .

PICTURE. Three shelves side by side: empty, balanced, and the disaster case.

The one-picture summary

This single figure compresses the whole walkthrough: $n$ keys enter a uniform machine, spread across $m$ boxes so each box averages $α = n / m$ keys, making a lookup jump ( $1$ ) + short walk ( $α$ ) $= O (1 + α)$ .

Recall Feynman retelling — explain it to a friend

Picture a wall of mailboxes. You throw letters at it with a rule that scatters them evenly — no box is a magnet. If you have as many letters as boxes, each box ends up with about one letter. So when you go to fetch a letter, you jump straight to its box (instant) and flick through the tiny pile there (also instant). That's why hashing feels like magic: even spreading keeps every pile short. But two things can ruin it — cramming way too many letters in (piles grow, so you make more boxes and re-throw), or a lazy rule that dumps everything in box 7 (one giant pile, back to slow searching). The maths is just: average pile size $= \frac{letters}{boxes} = α$ , and fetch time $=$ jump $+$ pile $= O (1 + α)$ .

Connections

Parent: 3.3.01 Hash function — properties - deterministic, uniform, fast (Hinglish)
Hash Table — the structure this cost analysis powers.
Collision Resolution — Separate Chaining — the chain we walk in Step 6.
Collision Resolution — Open Addressing — an alternative to chains.
Load Factor and Rehashing — controlling $α$ (Cases B).
Modular Arithmetic — how $h$ maps into $0.. m - 1$ .
Pigeonhole Principle — why collisions are unavoidable.