Hash Functions

Definition and Role

A hash function $h: U \to \{0, 1, \ldots, m-1\}$ maps keys from the universe $U$ to $m$ slots in a hash table. A good hash function satisfies:

1. Fast to compute: $\Theta(1)$ time per call. If the hash function itself is slow, the $O(1)$ promise of hash tables is hollow (hidden large constant factors).
2. Uniform distribution: each of the $m$ slots is equally likely for a random key. This is the simple uniform hashing assumption, which makes expected-case analysis possible.
3. Deterministic: the same key always maps to the same slot (unless using universal hashing where the function is chosen at random at runtime).

Handling Non-Integer Keys

Hash functions ultimately produce integers. For non-integer keys (strings, objects), the key must first be converted to an integer. A common approach for strings: treat each character as a digit in a large base (e.g. 256 for ASCII), producing a polynomial:

$h(s) = \left( \sum_{i=0}^{|s|-1} s[i] \cdot B^{|s|-1-i} \right) \bmod m$

The choice of base $B$ and modulus $m$ affects distribution quality.

Division Method

$h(k) = k \bmod m$

This is fast (one modular division), but the choice of $m$ is critical:

• Avoid powers of 2 (e.g. $m = 2^p$): then $h(k)$ depends only on the lowest $p$ bits of $k$, ignoring higher-order bits. This produces poor distribution if keys share low-bit patterns.
• Prefer $m$ as a prime number not too close to a power of 2. A prime modulus ensures all bits of $k$ influence the hash value.

Example: For $m = 10$, $h(23) = 3$, $h(47) = 7$, $h(13) = 3$ (collision). For $m = 11$ (prime): $h(23) = 1$, $h(47) = 3$, $h(13) = 2$ (no collision).

Multiplication Method

$h(k) = \lfloor m (kA \bmod 1) \rfloor$

where $A$ is a constant in $(0, 1)$. Knuth recommends $A \approx (\sqrt{5} - 1)/2 \approx 0.6180339887$ (the golden ratio conjugate).

The idea: multiply $k$ by $A$, extract the fractional part $(kA \bmod 1)$, and scale by $m$. The fractional part distributes keys uniformly across $[0, 1)$ regardless of patterns in $k$. The method works for any $m$, which is convenient when resizing tables.

Range Reduction

Modern hash functions typically output a 32-bit or 64-bit unsigned integer (e.g. 0..2^32-1). This raw output is too large to use as a table index. Range reduction converts it:

$\text{index} = h_{\text{raw}}(k) \bmod m$

This is fast but introduces slight bias unless $m$ divides the hash output range. In practice, the bias is negligible for well-designed hash functions.

Cryptographic vs Non-Cryptographic Hashing

Cryptographic hash functions (SHA-256, BLAKE3) provide strong guarantees: collision resistance, preimage resistance. They are slow by design and not needed for hash tables.

Non-cryptographic hash functions (MurmurHash, FNV-1a, xxHash) prioritise speed and reasonable distribution. These are the appropriate choice for in-memory data structures. The Cambridge course focuses on the latter.

Low-Entropy Inputs

If keys have low entropy (e.g. single letters, or words differing by one character like ROT, TOT, POT), even a good hash function cannot produce a uniform distribution: there are only 26 possible inputs, so at most 26 distinct hash values. For such inputs, choose domain-specific hash functions that maximise spread.

Summary

Method	Formula	Pros	Cons
Division	$k \bmod m$	Simple, fast	Need prime $m$
Multiplication	$\lfloor m(kA \bmod 1) \rfloor$	Works for any $m$	Slightly slower
Range reduction	$h_{\text{raw}}(k) \bmod m$	Decouples hash from table size	Minor bias
Polynomial (strings)	$\sum s[i] \cdot B^i \bmod m$	Good for strings	Parameter-sensitive
Desired property	Uniform distribution over $[0, m-1]$