Hash function — properties - deterministic, uniform, fast: Foundations

This page assumes you have seen nothing. Before you read the parent note, you need every symbol it throws at you. We build them one at a time, each on top of the last.

0. The mailbox picture that everything hangs on

Picture a wall of numbered mailboxes. You get a letter with a name on it. You need a rule that reads the name and points at exactly one box. That rule is the hash function. Hold this picture — every symbol below is a label on some part of it.

1. What is a "key"?

Picture: the name written on the front of the letter.

Why the topic needs it: hashing is about finding things by their key without searching everything. No key, nothing to look up.

2. The set-builder braces ${\dots}$ and "element of" $\in$

The parent writes ${0, 1, \dots, m - 1}$ and $j \in {0, \dots, m - 1}$ . These are just two pieces of shorthand.

Picture: ${0, \dots, m - 1}$ is the list of box numbers written under each mailbox. $\in$ points at one of them.

3. Table size $m$ and the universe $U$

Picture: $m$ is the handful of boxes on the wall. $U$ is the whole city of every possible name that could ever be mailed.

Why the topic needs it: because there are more keys than boxes, two keys must eventually share a box. That forced sharing has a name — the Pigeonhole Principle — and the whole idea of collision resolution exists only because of it.

4. What a function $h : U \to {0, \dots, m - 1}$ actually says

This one line is the heart of the parent note. Let's earn every piece.

Picture: an arrow leaving a name in the city and landing on exactly one box on the wall.

Why the topic needs it: every property in the parent — deterministic, uniform, fast — is a sentence about $h$ . You cannot read those sentences until $h (k)$ means something concrete.

\in

means

"is one of / is a member of".

{0, 1, \dots, m - 1}

lists which things

the

m

box numbers, from 0 up to

m - 1

(there are

m

of them).

h : U \to {0, \dots, m - 1}

, what is

U

the universe — every key that could ever possibly appear.

Why is

∣ U ∣ ≫ m

important

far more possible keys than boxes, so collisions are forced (pigeonhole).

h (k)

evaluates to

the box number the rule assigns to key

k

k_{1} = k_{2} ⟹ h (k_{1}) = h (k_{2})

states which property

deterministic — same key always lands in the same box.

P (h (k) = j) = \frac{1}{m}

means

every box is equally likely — a perfectly uniform (fair) rule.

The load factor

α = \frac{n}{m}

measures

average fullness — expected number of keys per box.

\sum_{i = 1}^{n} \frac{1}{m}

equals

\frac{n}{m} = α

(add

\frac{1}{m}

to itself

n

times).

50 mod 7

equals

1

(remainder after dividing 50 by 7).

Why use weights

p^{i}

in a string hash

so letter order matters — "abc" and "cab" get different hashes.

Connections

Parent: the three properties DUF
Pigeonhole Principle — why $∣ U ∣ ≫ m$ forces collisions.
Modular Arithmetic — the machinery behind $mod m$ .
Load Factor and Rehashing — what to do when $α$ grows.
Hash Table — the structure all this powers.
Collision Resolution — Separate Chaining · Collision Resolution — Open Addressing — handling the forced collisions.
Cryptographic Hash Functions — a stricter cousin (deliberately slow and unpredictable-looking).

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

0. The mailbox picture that everything hangs on

1. What is a "key"?

2. The set-builder braces ${\dots}$ and "element of" $\in$

3. Table size $m$ and the universe $U$

4. What a function $h : U \to {0, \dots, m - 1}$ actually says

5. The equals / implies chain: $k_{1} = k_{2} ⟹ h (k_{1}) = h (k_{2})$

6. Probability $P (\cdot)$ and the fraction $\frac{1}{m}$

7. Counting keys: $n$ , and the load factor $α = \frac{n}{m}$

8. The summation sign $\sum$ and "expected value" $E [\cdot]$

9. The mod operator $k mod m$

10. Base- $p$ / powers $p^{i}$ (for string hashing)

The prerequisite map

Equipment checklist

Connections