Skip to main content

Universal Hashing, Load Factor, and Resizing

What This Concept Is​

Three knobs control hash-table performance in practice:

  • Hash function quality -- how well does (h) mimic uniform mapping on realistic keys?
  • Load factor (\alpha = n / m) -- how full is the table?
  • Resize policy -- when and how do we grow or shrink the underlying array?

Universal hashing is a technique for picking the hash function at random from a family so that no adversary can force many collisions. A family (H) is universal if, for any two distinct keys (x \neq y), [ \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m}. ] A classic example is the Carter-Wegman family (h_{a,b}(x) = ((a x + b) \bmod p) \bmod m), with (p) a large prime and (a \in [1, p-1]), (b \in [0, p-1]) chosen uniformly.

A stronger property, 2-independence (pairwise independence), requires the joint distribution of any two hash outputs to look uniform. Tabulation hashing (Thorup-Patrascu) is a practical scheme that reaches 3-independence with a single table lookup per byte. MurmurHash3, FarmHash, xxHash, and SipHash are the non-cryptographic workhorses for modern hash tables; SipHash specifically was introduced as a keyed hash resistant to HashDoS.

Cryptographic hashing (SHA-256, BLAKE3) is a different beast: collision-resistant, preimage-resistant, second-preimage-resistant. Used for integrity, fingerprinting, and commitments -- not for dictionary buckets, because they are 50-100x slower than non-cryptographic hashes and solve a problem you do not have inside a hash table.

Load factor controls expected cost. Typical targets: (\alpha = 0.75) for chaining, (\alpha = 0.5) for open addressing, lower still for tombstone-heavy workloads. SwissTable targets (\alpha = 7/8) thanks to SIMD group-probes.

Resizing doubles (m) (or quadruples it, like Python), re-hashes every existing entry, and amortizes to (O(1)) per operation via the doubling charge. Without resizing, insertion degrades to (\Theta(n)) per operation as (n) grows past (m).

Why It Matters Here​

A large share of performance incidents and CVEs trace back to a weak hash, ignored load factor, or absent resize policy:

  • The 2011 28C3 HashDoS class of attacks exploited deterministic string hashes in PHP, Java, Python, Ruby, Node, and ASP.NET -- a single POST with a few thousand carefully chosen keys could freeze a server. The universal fix was per-process randomized seeds feeding into a keyed hash (SipHash in Rust, Python, Node, Redis; MurmurHash with random seed in Java).
  • Poorly tuned load factors cause periodic p99 latency spikes -- the "every 10,000 operations we allocate 4x the current table and stall" pattern.
  • Missing shrink-on-delete turns a spiky workload into a slow memory leak; missing resize-on-grow turns a long-running process into a (\Theta(n)) insert per step.

Universal hashing converts the shaky "expected (O(1))" guarantee -- which assumes the keys are random -- into a provable bound: you randomize the function instead of assuming randomness of the input. This is the same idea as randomized quicksort: move the randomness from the adversary into your code.

Concrete Examples​

Example 1 -- the Carter-Wegman family. Pick (h_{a,b}(x) = ((a x + b) \bmod p) \bmod m) with (p = 2^{31} - 1), (m = 1024), and (a, b) uniform random.

For any two distinct keys (x \neq y), fix them and count over the choice of ((a, b)). The map ((a, b) \mapsto (a x + b \bmod p, a y + b \bmod p)) is a bijection on ([0, p)^2), so ((a x + b) \bmod p) and ((a y + b) \bmod p) are uniform and distinct. Taking (\bmod m) collides two distinct values with probability at most (\lceil p / m \rceil / (p - 1) \leq 1/m). Therefore the family is universal.

Consequence: for (n = 1000) inserted keys into (m = 1024) buckets, the expected collision pairs is at most (\binom{1000}{2} / 1024 \approx 488). The expected chain length containing any given key is (1 + (n - 1)/m \approx 1.98) -- short regardless of what the input looks like.

Example 2 -- the amortized cost of doubling. Assume a chaining table. Each insert costs (1) for the write plus possibly (n) for a resize.

Charge each insert (3) tokens: (1) for itself, (1) for moving itself on the next resize, (1) for moving an earlier element on the next resize. When the table is full at size (m) and we double to (2m), we need to move (m) elements. The (m) inserts since the last resize each contributed (1) "move itself" token (covers their own move) and (1) "move an earlier element" token (covers one of the (m) earlier elements). Total token balance: (\geq m + m = 2m), which covers the (m) moves with slack.

So amortized cost per insert is (O(1)). The same argument works for any constant growth factor (> 1); Python's dict uses 2x, C++'s std::unordered_map 2x (to next prime), Go's 2x with incremental rehash spread over subsequent inserts.

Example 3 -- load factor versus expected probe cost (open addressing). With linear probing and load factor (\alpha), the expected number of probes for a successful lookup is (\tfrac{1}{2}\left(1 + \tfrac{1}{1-\alpha}\right)) and for an unsuccessful lookup (\tfrac{1}{2}\left(1 + \tfrac{1}{(1-\alpha)^2}\right)) (Knuth TAOCP Vol 3). Plug in (\alpha = 0.5): successful (\approx 1.5) probes, unsuccessful (\approx 2.5). At (\alpha = 0.875) (SwissTable target): successful (\approx 4.5) probes, unsuccessful (\approx 32.5) -- tolerable only because SwissTable probes 16 slots per cache line via SIMD, reducing the effective probe count to (\lceil 32.5 / 16 \rceil \approx 2) cache-line reads. This is why "raise (\alpha) and parallelize the probes" beats "keep (\alpha) low and serialize" on modern CPUs.

Common Confusion / Misconceptions​

"Hash mod m with a fixed good hash is enough." Only for non-adversarial keys. As long as the hash is deterministic and known, the attacker can enumerate keys colliding into one bucket. The fix is keyed hashing with a secret seed refreshed per process (or per table, for the paranoid). SipHash-1-3 is the standard choice; tabulation hashing is another.

"Cryptographic hashes are the safe default." SHA-256 is (~100\times) slower than SipHash and gives you properties (collision resistance, preimage resistance) that dictionaries do not need. Use crypto hashes only for integrity, fingerprinting, or commitment -- not for bucket selection.

"Resize doubles cost; therefore hash tables are not real-time." Each operation's amortized cost is (O(1)), but individual resizes cost (\Theta(n)) -- a real-time system cannot tolerate that single-operation stall. Real-time alternatives incrementally rehash: Go's map moves one old bucket per access, Java ConcurrentHashMap uses a resize helper thread, Redis keeps both tables alive during rehashidx progress.

"Never shrink." Many implementations never shrink, holding onto memory long after a mass delete. If memory pressure matters, shrink below a hysteresis band (e.g., shrink to half when (\alpha < 1/8), grow to double when (\alpha > 3/4)). Hysteresis prevents oscillation on boundary workloads.

How To Use It​

For a dictionary-style hash table:

  1. Use the language's built-in; verify it randomizes the hash seed (Python yes since 3.3; Java yes since 8 for HashMap; Go yes with per-map random seed; Rust std::collections::HashMap uses SipHash-1-3).
  2. If writing your own, pick a universal or keyed non-cryptographic hash (SipHash, xxHash, FNV-1a for tiny cases).
  3. Choose a target load factor matching your scheme (chaining (\approx 0.75), open addressing (\approx 0.5), SwissTable (\approx 0.875)).
  4. Resize with a constant growth factor (2x is standard; 1.5x reduces peak memory at the cost of more resizes).
  5. Add hysteresis on shrink to avoid thrashing.
  6. If you cannot tolerate resize stalls, use incremental rehashing.

For fingerprinting (deduplication, Merkle trees, content-addressing):

  1. Use a cryptographic hash (SHA-256, BLAKE3).
  2. Keep the full digest, not a truncated mod m.

For random-oracle-style analyses in algorithms:

  1. Prove the bound against a universal family, not against "assume uniform hashing."

Transfer / Where This Shows Up Later​

  • S2 M2 (this module). Concepts 11 and 12 lean on the load-factor arithmetic established here; concept 16's bucketed priority queues use (\alpha)-aware sizing too.
  • S2 M3 (graphs). Any graph algorithm using a hash set for "visited" inherits HashDoS risk if the input vertices are attacker-controlled (e.g., URLs in a crawler).
  • S2 M4 (DP and greedy). Memoization tables are hash-backed; resize policy affects solver tail-latency.
  • S3 (software design). API contracts that accept user strings as hash keys are a latent HashDoS surface -- the reviewer checklist item "is this hash keyed?" lives here.
  • S4 (systems programming). Linux's dst_cache, kernel tcp_hashinfo, and eBPF hash maps all use jhash or SipHash with per-boot random seed -- examples you will re-encounter.
  • S5 (OS). Page cache, dentry cache, inode cache all implement incremental resize or pre-sized tables -- the "never stall" requirement from above.
  • S6 (databases). PostgreSQL's dynahash, MySQL's innodb buffer pool hash table, Redis's dict with incremental rehash, RocksDB's memtable -- all implement the grow/shrink/seed pattern you learn here. Bloom filters further extend universal hashing to probabilistic set membership.
  • S7 (architecture). Cache stampedes, thundering herds, and resize storms are architectural risks that link back to load factor choices; ADRs for cache layers often specify the target (\alpha) and shrink behavior.
  • S8 (system design). Consistent hashing, jump hash, rendezvous hashing -- all use universal/cryptographic hashes as primitives for load balancing and sharding. HashDoS lessons apply equally to sharding keys.

Check Yourself​

  1. State the inequality that defines a universal family of hash functions.
  2. Why does amortized (O(1)) insert hold despite individual (\Theta(n)) resizes?
  3. What concrete attack does keyed hashing prevent, and why does a fixed-seed hash fail?
  4. When should you use a cryptographic hash, and when is that choice wasteful or wrong?
  5. Why do production hash tables use hysteresis on shrink?
  6. Linear probing's expected probe count blows up near (\alpha = 1); derive the (\tfrac{1}{2}(1 + 1/(1-\alpha))) formula for successful lookup and explain why this curve justifies SwissTable's aggressive target load.
  7. Under the accounting argument, what amortized charge per insert is sufficient for a growth factor of (1.5) instead of (2)? Show the algebra.

Mini Drill or Application​

  1. Prove that (h_{a,b}(x) = ((a x + b) \bmod p) \bmod m) is universal (the argument from Example 1 in detail).
  2. Given (n = 4096), pick (m) and target (\alpha) for (a) a chaining table, (b) an open-addressed SwissTable; justify both.
  3. Describe a concrete HashDoS attack against a web server that parses form fields into a dict; then describe how keyed SipHash fixes it.
  4. Implement a toy dict with incremental rehash: each access moves at most one old bucket. Measure p99 latency against batch rehash on 10M inserts.
  5. Compare empirical chain-length distribution on 1M random strings for MurmurHash3 vs. SipHash vs. SHA-256; report mean, p99, and throughput.
  6. Production scenario. A Redis-backed session cache shows periodic 300 ms stalls on a service with a 50 ms p99 SLA. Profiling shows the stalls align with Redis dict resize events at (2^{24})-entry boundaries. Diagnose: is the right fix (a) pre-sizing via CONFIG SET, (b) switching to incremental rehash (already on by default), (c) sharding into (k) smaller dicts, or (d) moving to a different datatype? Defend your answer using the load-factor / amortization arithmetic from this concept.

Read This Only If Stuck​