Hash function

To map a large Universe (U) of possible keys (e.g., all student IDs) into a small, manageable array of size m.

$$ h : U → \{0, 1, ..., m − 1\} $$

Collision

• A collision occurs when two different inputs produce the exact same output hash value.
• Our fast O(1) array lookup (the hash table) degrades into a slow O(n) linked list search. It defeats the entire purpose!

Modern hash function

$$ h(x)=(ax+b)(\text{mod} ~p) $$

• $p$: A large prime number (larger than any possible input value $x$)
• $a$: A random number from $1$ to $p-1$
• $b$: A random number from $0$ to $p-1$

For inputs in $\{0, ..., p − 1\}$, if $x1 \ne x2$, then $h(x1) \ne h(x2)$

• The total number of permutations of $p$ items is $p!$, a gigantic number.