Hash Function Fundamentals

A hash table maps keys to values via a hash function $h(k)$ that produces an integer in $[0, m)$, where $m$ is the table size. The key/value pair is stored at bucket $h(k)$. Lookups, inserts, and deletes are all expected $O(1)$ when the hash function distributes keys uniformly.

What makes a good hash function

Three properties: deterministic (same input always gives the same output), uniform (output distributes evenly across buckets), and fast (constant time independent of key value). The classic example for strings is polynomial hashing: $h(s) = \sum_i s[i] \cdot p^i \mod m$, where $p$ is a small prime.

Load factor

Define $\alpha = n / m$ — the ratio of stored elements to table size. Performance degrades as $\alpha$ grows. Most implementations resize (rehash all elements into a doubled table) when $\alpha$ exceeds a threshold like 0.75. Rehashing is $O(n)$, but it's amortized $O(1)$ per insert across the table's lifetime.

Why expected, not worst-case

Adversarial inputs can force every key into the same bucket, degrading to $O(n)$ per operation. Practical defenses: salted hashing (Python, Rust, Go since 1.x), where the seed is randomized at process start so an attacker can't precompute collisions. Java's HashMap converts long collision chains into balanced trees ($O(\log n)$) rather than degrading further.

Hashing user-defined types

To use a struct as a key, you must implement both `hash` and `equality`. The contract: equal keys must hash to the same value. Violating this is the most common source of "I put it in the map but I can't find it" bugs.