Hash function — properties - deterministic, uniform, fast: Question bank

This bank targets the misconceptions around the three properties — never the arithmetic (that lives in the computation drills). Focus on why the property is what it is and where it quietly breaks.

Definition The symbols used on this page (read first)

Everything below reuses letters from the parent note. Fix their pictures now so no line surprises you:

$h$ — the hash function, the machine/rule that turns a key into a bucket number.
$k$ — a key, the thing you feed in (a string like "cat", a number like a phone number).
$U$ — the universe: the (usually enormous) set of all possible keys you might ever hash.
$m$ — the table size: the number of buckets/slots, small and finite. So $h$ always outputs a number in ${0, 1, \dots, m - 1}$ .
$n$ — the number of keys actually inserted so far.
$j$ — the name we give to one particular bucket, some number in ${0, \dots, m - 1}$ .
$α = n / m$ — the load factor: keys divided by buckets. Picture it as the average height of the pile in each bucket. Its picture is Figure 1.
$L$ — the length of a key when it is a string (how many characters). A string hash's cost grows with $L$ , never with $n$ .
$c_{i}$ — the numeric code of the $i$ -th character of a string (e.g. ASCII, or a=1, b=2, ...). The $i$ runs $0, 1, \dots, L - 1$ .
$p$ — the base of a polynomial string hash, a small prime (often 31). It is the "weight per position" that makes character order matter.

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

True or false — justify

A hash function that spreads keys perfectly evenly but changes its answer between runs is still useful.

False — evenness (uniformity) is worthless without determinism; if insert("cat") and lookup("cat") compute different buckets you can never retrieve the key.

If two keys collide, the hash function is broken.

False — collisions are unavoidable by the Pigeonhole Principle since the universe

U

is far larger than

m

; a good hash makes them rare and evenly spread, it does not eliminate them.

A cryptographically secure hash (like SHA-256) is always the best choice for a hash table.

False — it is deterministic and uniform but slow; hashing's whole point is a tiny constant-time cost, so Cryptographic Hash Functions usually violate the "fast" property for this use.

Simple Uniform Hashing means every bucket ends up with exactly the same number of keys.

False — SUH is about probability (

P (h (k) = j) = 1/ m

for each bucket

j

), not a guarantee; it makes

α

the expected pile height, but real counts fluctuate around it (see Figure 4).

Using

h (k) = k mod 2^{10}

is fine because it always lands in range.

False — a power-of-two modulus keeps only the low-order bits of

k

, so keys sharing those bits cluster; a prime

m

mixes all bits (see Figure 2). Grounded in Modular Arithmetic.

Determinism forbids a hash function from ever using a random seed.

False — a seed fixed once per table is fine and still deterministic; only a fresh random value per call breaks determinism.

Making a hash function faster always costs you uniformity.

False — they are separate goals; a well-designed polynomial string hash is both fast (cost grows with key length

L

, not with

n

) and well-distributed. Speed and spread are not a strict trade-off.

If the load factor

α

is well below 1, collisions cannot happen.

False —

α < 1

only means fewer keys than buckets on average; two keys can still map to the same bucket

j

, so piles of height 2+ still occur.

A hash function is uniform if it uses all

m

buckets at least once.

False — using every bucket says nothing about balance; 90% of keys could still pile into one bucket while the others hold one each.

Spot the error

"I'll call random() inside h() to spread keys better."

The error is per-call randomness — it destroys determinism, so the same key

k

hashes differently each time and lookup fails. Fix: fix any randomness as a per-table seed.

"Phone numbers hash fine with

h (k) = k mod 1000

since 1000 is big."

The error is a power-of-ten modulus: it looks only at the last 3 digits and ignores the rest of

k

. In many real numbering plans those trailing digits are handed out sequentially within an exchange or block, so nearby subscribers share ranges — mild but real clustering. A prime

m

folds in all digits, which is the robust default whatever the data looks like.

"I hash strings by summing their ASCII codes — simple and fast."

The error is losing order information: "abc", "cab", "bca" share the same sum and collide. Positional weights

p^{i}

(polynomial hash,

p

a small prime) distinguish character order.

"To keep search

O (1)

I never resize the table, I just add more keys."

The error is a growing

α = n / m

: as

n

climbs with

m

fixed, the piles lengthen toward

O (n)

search. Fix is Load Factor and Rehashing — grow

m

and rehash once

α

crosses a threshold (see the "Why 0.75" question).

"My hash returns a value in

{0, \dots, m - 1}

but I compute the mod only at the very end of the string loop."

Not always an error mathematically, but the intermediate sum

\sum c_{i} p^{i}

can overflow machine range for long strings; take mod at every Horner step to stay in range and keep the cost proportional to key length

L

(see the Horner "why" question and Figure 5).

"Since collisions are inevitable, the choice of hash function doesn't really matter."

The error is treating all hashes as equal: a bad one dumps keys into few buckets (tall piles), a uniform one keeps expected pile height at

α

. The distribution is exactly what matters. See Collision Resolution — Separate Chaining.

Why questions

Why is "fast" really "uniform in disguise's partner", i.e. why does uniformity protect speed?

Because search cost is

O (1 + α)

and uniformity guarantees

α

is the average pile height; without it, some buckets grow to

O (n)

and destroy the speed guarantee.

Why must the same seed give the same output for determinism to hold?

Determinism is defined given the fixed seed; retrieval recomputes

h (k)

with that same seed, so as long as it never changes between insert and lookup, the bucket is reproducible.

Why does a prime table size mix all the bits of a key?

Look at Figure 2. With

m = 2^{b}

, computing

k mod m

literally keeps the last $b$ bits and throws the rest away — two keys agreeing in those bits always collide, no matter how their high bits differ. A prime

m

has no factor in common with the place-values

2^{0}, 2^{1}, 2^{2}, \dots

, so each successive bit's contribution wraps around the bucket range by a different offset instead of vanishing. That coupling forces the remainder to depend on the whole key, not a fixed tail. Grounded in Modular Arithmetic.

Why is the resize threshold traditionally around

0.75

and not, say,

0.99

With separate chaining, expected work is

O (1 + α)

, so cost rises linearly with

α

— waiting longer just means longer piles. With open addressing the cost is far more brutal: the expected probes for an unsuccessful search behave like

\frac{1}{1 - α}

. Plug in

α = 0.75 \Rightarrow \frac{1}{0.25} = 4

probes;

α = 0.9 \Rightarrow 10

probes;

α = 0.99 \Rightarrow 100

probes. The curve knees upward sharply near

1

, so

0.75

is a pragmatic point before the blow-up while still using memory reasonably. Figure 3 plots this. See Collision Resolution — Open Addressing and Load Factor and Rehashing.

Why is

O (1 + α)

written with the "

1 +

" instead of just

O (α)

The

1

is the always-present cost of computing the hash and reaching the bucket; the

α

is the pile walk. When

α \to 0

the cost is still 1, not 0.

Why does Horner's method let a string hash stay in machine range, so you never see the full

\sum c_{i} p^{i}

Follow Figure 5. Horner rewrites

c_{0} + c_{1} p + c_{2} p^{2}

((c_{0}) \cdot p + c_{1}) \cdot p + c_{2}

— one multiply-add per character. Take a two-step toy with

p = 31

m = 1000

on codes

c_{0} = 3, c_{1} = 1

: start at

0

; step 1 gives

(0 \cdot 31 + 3) mod 1000 = 3

; step 2 gives

(3 \cdot 31 + 1) mod 1000 = 94

. The running value never climbs past about

p \cdot m

, because the mod at every step chops it back into range before the next multiply — so the giant number

\sum c_{i} p^{i}

is never actually formed.

Why does hashing cost grow with

L

and not with

n

A string hash touches each of the

L

characters exactly once (one multiply-add per character), so its work is

O (L)

; it never looks at the other keys already in the table, so

n

does not enter — which is exactly what the "fast" property demands.

Why do we accept collisions instead of designing a perfect one-to-one hash?

For an arbitrary huge universe

U

, no fixed-size table can be collision-free (pigeonhole); a perfect hash needs the key set known in advance, which general Hash Table use does not have.

Edge cases

What is the expected pile height when

n = 0

(empty table)?

α = 0/ m = 0

, so expected pile height is 0 and search cost is just the

O (1)

hash computation — the degenerate but consistent case.

What happens to the load factor and search cost when

n = m

α = 1

, so expected pile height is 1; search stays

O (1)

on average with chaining, which is why

m \approx n

is a sweet spot before rehashing.

Is a constant hash

h (k) = 0

for all keys deterministic? Is it useful?

It is perfectly deterministic (same key → bucket 0 always) but maximally non-uniform — every key piles into bucket 0, degrading search to

O (n)

. Determinism alone is not enough.

What does hashing an empty string "" produce under the polynomial method?

The loop never runs (there are no

c_{i}

L = 0

), so the hash stays at its initial value

0

(then

0 mod m = 0

) — a valid, deterministic bucket, not an error.

If two identical keys are inserted, do they collide?

They are the same key

k

, so by determinism they map to the same bucket — but this is intended duplicate handling, not a "collision" in the distinct-keys sense.

With

m = 1

(single bucket), what happens to uniformity and search?

P (h (k) = 0) = 1

, trivially "uniform" over one bucket, but

α = n

so every operation degenerates to a linear scan — the boundary where a table becomes a list.

Connections

Parent topic — the three properties in full.
Pigeonhole Principle — why collisions are inevitable.
Load Factor and Rehashing — the $α$ threshold behind the edge cases.
Collision Resolution — Separate Chaining · Collision Resolution — Open Addressing — what happens after a collision.
Cryptographic Hash Functions — deterministic and uniform but too slow for table use.