Hash function — properties - deterministic, uniform, fast: Worked examples

Before anything: recall the two workhorses we will use over and over.

The scenario matrix

Every worked example below is tagged with the cell of this matrix it covers. Together they fill the whole grid.

Cell	Case class	What could go wrong
A	Positive key, prime $m$	Baseline — should spread well
B	Key $= 0$ (zero input)	Does $0$ hash sensibly?
C	Key $\geq m$ vs key $< m$	What if the key is smaller than the table?
D	Negative key	$mod$ can go negative in real code
E	Bad modulus (power of 10/2)	Clustering — low-digit blindness
F	Degenerate table $m = 1$	Everything collides — limiting case
G	String key (order matters)	Anagrams must differ
H	Huge key / overflow	Keep numbers in range mid-computation
I	Real-world word problem	Phone numbers / usernames
J	Exam twist	Load factor + rehash decision

Worked examples

Example 1 — Cell A: the clean baseline

Worked example Positive keys into a prime table

Keys ${18, 41, 22, 59, 8}$ , table size $m = 7$ (prime). Compute $h (k) = k mod 7$ .

Forecast: guess — will all five land in different buckets, or will some collide? (There are 5 keys and 7 buckets, so collisions are possible but not forced.)

$18 mod 7$ : $7 \cdot 2 = 14$ , remainder $18 - 14 = 4$ . → bucket 4. Why this step? Subtract the largest multiple of $7$ not exceeding $18$ ; what's left is the bucket.
$41 mod 7$ : $7 \cdot 5 = 35$ , $41 - 35 = 6$ . → bucket 6.
$22 mod 7$ : $7 \cdot 3 = 21$ , $22 - 21 = 1$ . → bucket 1.
$59 mod 7$ : $7 \cdot 8 = 56$ , $59 - 56 = 3$ . → bucket 3.
$8 mod 7$ : $7 \cdot 1 = 7$ , $8 - 7 = 1$ . → bucket 1 — collision with key $22$ !

Verify: buckets used ${4, 6, 1, 3, 1}$ . Two keys ( $22, 8$ ) share bucket $1$ ; the rest are unique. Load factor $α = 5/7 \approx 0.71$ , still under the $0.75$ resize line — one short chain is exactly the "rare, evenly distributed" behaviour we want.

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

Example 2 — Cell B & C: zero, and a key smaller than the table

Worked example Degenerate inputs:

$k = 0$ and $k < m$ Table $m = 11$ . Hash the keys $0$ , $3$ , and $11$ .

Forecast: where does $0$ go? And does a key like $3$ (smaller than the table) hash to itself?

$0 mod 11 = 0$ . → bucket 0. Why this step? Zero divided by anything leaves remainder zero. $0$ is a perfectly legal key; it just deterministically lives in bucket $0$ .
$3 mod 11 = 3$ (since $3 < 11$ , the largest multiple of $11$ below $3$ is $0$ ). → bucket 3. Why this step? When $k < m$ , no wrap happens: $h (k) = k$ . This is fine — it's still deterministic and in range.
$11 mod 11 = 0$ . → bucket 0 — collides with the key $0$ . Why this step? $11$ is exactly one full table, so it wraps back to the start.

Verify: buckets ${0, 3, 0}$ . Keys $0$ and $11$ both land in bucket $0$ — a valid collision, not a bug. No index ever falls outside ${0, \dots, 10}$ : every remainder is $\geq 0$ and $< m$ by definition. ✓

Example 3 — Cell D: negative keys (the real-code trap)

Worked example What if the key is negative?

Some languages store hash codes as signed integers, so a key like $- 17$ can appear. Table $m = 5$ . Compute the bucket for $- 17$ .

Forecast: what does $- 17 mod 5$ give? Careful — many programming languages return a negative remainder here.

Mathematically, $mod$ should give a value in ${0, 1, 2, 3, 4}$ . We want the largest multiple of $5$ at or below $- 17$ : that is $- 20$ (since $5 \cdot (- 4) = - 20$ ). Remainder $= - 17 - (- 20) = 3$ . → bucket 3. Why this step? The mathematical modulo always lands in $[0, m)$ by choosing the multiple below the number, even for negatives.
But in C/Java, -17 % 5 returns $- 2$ (they round the quotient toward zero). Index $- 2$ would crash or read out of bounds! Why this step? You must know your language's sign convention — this is the #1 real bug in hashing negatives.
The safe fix: $((k mod m) + m) mod m = ((- 2) + 5) mod 5 = 3$ . → bucket 3. Why this step? Adding $m$ then taking $mod$ again pushes any negative result back into range, giving the true math answer.

Verify: both the pure-math path and the fixed-code path give bucket 3, and $0 \leq 3 < 5$ . ✓ Determinism holds: $- 17$ always maps to $3$ .

Example 4 — Cell E & F: the bad modulus and the degenerate table

Worked example Why power-of-10 moduli cluster, and what

$m = 1$ does Part 1 (Cell E): phone-number-style keys ${5550100, 5550120, 5550130, 5550140}$ , hashed with $m = 10$ .

Forecast: these numbers differ a lot — will they spread across the 10 buckets?

$h (k) = k mod 10$ = the last digit of $k$ . Why this step? $10$ divides evenly into the higher place-values, so only the units digit survives the remainder.
Last digits: $0, 0, 0, 0$ . → all four in bucket 0. Why this step? These keys were engineered to share a last digit — exactly what real phone/ID data does. The modulus ignored 6 out of 7 digits.

Part 2 (Cell F): the same four keys with the degenerate table $m = 1$ .

$h (k) = k mod 1 = 0$ for every key. Why this step? A one-bucket table forces $100%$ collisions — the limiting worst case. The table degenerates into a single linked list; lookups become $O (n)$ .

Verify: Part 1 buckets ${0, 0, 0, 0}$ (all collide because $m = 10$ reads only the tail). Part 2 buckets ${0, 0, 0, 0}$ (all collide because there is only one bucket). Both illustrate the Pigeonhole Principle pushed to the edge — but Part 1's clustering is avoidable by choosing a prime $m$ that mixes all digits, while Part 2's is unavoidable given $m = 1$ . ✓

Example 5 — Cell G: strings where order matters

Worked example Anagrams must hash differently

Hash "cat" and "act" with $p = 31$ , $m = 100$ . Use codes $a = 1, c = 3, t = 20$ .

Forecast: these are anagrams (same letters). If we just summed codes they'd tie. Will the polynomial hash separate them?

"cat" = characters c, a, t:

start $= 0$ .
c(3): $0 \cdot 31 + 3 = 3$ . Why? fold the first character in.
a(1): $3 \cdot 31 + 1 = 94$ . Why? multiply by $p$ shifts everything up one "base-31 digit", then add the new code.
t(20): $94 \cdot 31 + 20 = 2914 + 20 = 2934$ . Then $2934 mod 100 = 34$ . → bucket 34.

"act" = characters a, c, t: 5. start $= 0$ . 6. a(1): $0 \cdot 31 + 1 = 1$ . 7. c(3): $1 \cdot 31 + 3 = 34$ . 8. t(20): $34 \cdot 31 + 20 = 1054 + 20 = 1074$ . Then $1074 mod 100 = 74$ . → bucket 74.

Verify: "cat" → $34$ , "act" → $74$ . Different buckets even though the letters match! The plain-sum would give $3 + 1 + 20 = 24$ for both — a guaranteed collision. The positional weights $p^{i}$ are what break the tie. ✓

Example 6 — Cell H: huge key without overflow

Worked example Keeping numbers small mid-computation

Hash "ZZZZ" with $p = 53$ , $m = 97$ . Use $Z = 26$ . Show that taking $mod$ every step gives the same answer as computing the giant number first.

Forecast: the full number is $26 (5 3^{3} + 5 3^{2} + 53 + 1)$ — will step-by-step $mod$ match it?

Full number first:

$5 3^{3} = 148877, 5 3^{2} = 2809, 5 3^{1} = 53, 5 3^{0} = 1$ . Sum $= 151740$ .
$\times 26 = 3945240$ . Then $3945240 mod 97 = 3945240 - 97 \cdot 40672 = 3945240 - 3945184 = 56$ . → bucket 56.

Step-by-step, reducing $mod 97$ each fold: 3. start $0$ . 4. Z: $(0 \cdot 53 + 26) mod 97 = 26$ . 5. Z: $(26 \cdot 53 + 26) mod 97 = 1404 mod 97 = 1404 - 14 \cdot 97 = 1404 - 1358 = 46$ . 6. Z: $(46 \cdot 53 + 26) mod 97 = 2464 mod 97 = 2464 - 25 \cdot 97 = 2464 - 2425 = 39$ . 7. Z: $(39 \cdot 53 + 26) mod 97 = 2093 mod 97 = 2093 - 21 \cdot 97 = 2093 - 2037 = 56$ . → bucket 56. Why this step? Modular arithmetic obeys $(a \cdot b + c) mod m$ can be reduced at any stage — the result is unchanged. This is what keeps the running number tiny and the hash $O (L)$ and overflow-proof.

Verify: both routes give bucket 56. ✓ Reducing early never changes the answer; it only prevents the number from growing past machine limits.

Example 7 — Cell I: real-world word problem

Worked example Usernames into buckets, then check the spread

A site hashes usernames with the polynomial hash ( $p = 31$ ), table $m = 13$ . It has already placed 4 users and wants to know if the table is still healthy. Suppose their computed hashes gave buckets ${2, 5, 5, 11}$ . A new user "eve" arrives ( $e = 5, v = 22$ ).

Forecast: which bucket does "eve" land in, and is the table getting crowded?

"eve" = e, v, e. start $0$ ; e(5): $0 \cdot 31 + 5 = 5$ ; v(22): $5 \cdot 31 + 22 = 177$ ; e(5): $177 \cdot 31 + 5 = 5492$ . Why this step? Fold every character so order matters ("eve" is a palindrome but the weights still count each position).
$5492 mod 13$ : $13 \cdot 422 = 5486$ , remainder $5492 - 5486 = 6$ . → bucket 6. Why this step? Reduce into the table's index range ${0, \dots, 12}$ .
Bucket $6$ is currently empty → no collision; "eve" sits alone. Why this step? Uniformity paying off: existing keys clustered a bit at bucket $5$ , but the new key spread elsewhere.

Verify: "eve" → bucket 6, and $0 \leq 6 < 13$ . After insertion, 5 keys in 13 buckets: $α = 5/13 \approx 0.385$ — well below $0.75$ , so no resize needed. ✓ See Load Factor and Rehashing.

Example 8 — Cell J: the exam twist (load factor → rehash decision)

Worked example Should we double the table?

A hash table with separate chaining has $m = 8$ buckets and currently holds $n = 7$ keys. Policy: resize (double $m$ , rehash all keys) whenever $α > 0.75$ . A new key "k" ( $k = 11$ ) is about to be inserted, hashed by division on its numeric code with the current $m$ .

Forecast: after inserting, will $α$ cross the threshold? If so, what is the new expected chain length?

Current $α = 7/8 = 0.875$ . Already above $0.75$ ? Yes — but resize is checked before/at insertion. Insert makes $n = 8$ , so $α = 8/8 = 1.0$ . Why this step? Load factor is $n / m$ ; adding a key raises $n$ and therefore $α$ .
$1.0 > 0.75$ → trigger a resize: new $m = 16$ . Why this step? Long chains threaten the $O (1)$ promise; doubling restores headroom.
After rehashing all 8 keys into 16 buckets: new $α = 8/16 = 0.5$ . Expected chain length $= α = 0.5$ ; expected successful-search probes $\approx 1 + α /2 = 1 + 0.25 = 1.25$ . Why this step? Under Simple Uniform Hashing, expected keys per bucket equals $α$ (linearity of expectation) — halving $α$ nearly halves chain work.

Verify: before resize $α = 1.0$ ; after resize $α = 0.5$ and expected probes $= 1.25$ . Both computed directly from $α = n / m$ . ✓ The bucket for "k" (numeric $11$ ) in the new table is $11 mod 16 = 11$ .

Case-coverage recap

Recall Which example covered which cell?

A (positive, prime $m$ ) ::: Example 1 B (zero key) ::: Example 2 C (key smaller than table) ::: Example 2 D (negative key + language sign trap) ::: Example 3 E (power-of-10 modulus clustering) ::: Example 4 Part 1 F (degenerate $m = 1$ , all collide) ::: Example 4 Part 2 G (anagram strings, order matters) ::: Example 5 H (huge key, overflow-safe mod) ::: Example 6 I (real-world username word problem) ::: Example 7 J (exam twist: load factor + rehash) ::: Example 8

Connections

Parent topic — the three properties DUF.
Modular Arithmetic — why the $mod$ steps above are valid to reduce early.
Pigeonhole Principle — why cells E and F force collisions.
Hash Table · Collision Resolution — Separate Chaining · Collision Resolution — Open Addressing — where these buckets live.
Load Factor and Rehashing — the $α$ machinery behind Example 8.
Cryptographic Hash Functions — a different goal (security), not raw speed.