Universal Hashing, Load Factor, and Resizing
What This Concept Is
A universal family guarantees that for any two fixed distinct keys x,y, a hash function chosen randomly from the family has collision probability at most 1/m. The quantifiers matter: choose keys independently of the random function for this statement. It is not a claim that one chosen function separates every pair.
For integer keys in a bounded universe below prime p, a standard family is
h(x)=((a*x+b) mod p) mod m, choosing a uniformly from 1 through p-1 and b
from 0 through p-1, with m<=p. Encoding larger keys by simply reducing modulo p
can make distinct keys identical before this guarantee applies.
Why It Matters Here
Hash randomization and capacity management solve different problems. Randomization controls expected collisions under a model. Geometric capacity growth controls the total volume of capacity changes across insertions. Neither alone certifies constant-time dictionary operations.
Concrete Examples
If capacities double, the previous capacities form a geometric series, so the sum of allocated slots across growth to size n is O(n), starting from a fixed capacity. If redistribution costs expected O(number of entries + capacity), growth rebuilding contributes O(1) expected amortized work per insertion. A single growth still touches Theta(n) entries. Under a deterministic colliding linear-probing hash, reinserting n entries may take Theta(n²) probes; the geometric array-allocation argument does not make those probes constant.
Repeatedly deleting and inserting can accumulate tombstones while live size stays small. The lab map tracks both quantities and either cleans at the same capacity or doubles. Its deterministic hash demonstrates correctness and policy, not a universal-hashing or expected-constant-time theorem.
Common Confusion / Misconceptions
Cryptographic collision resistance and universal hashing have different definitions and use cases. A fixed public function can permit deliberately bad key sets. Adaptive attackers observing the chosen function require an analysis beyond the fixed-input universal-family argument. Choosing a prime capacity does not replace randomized function selection.
Amortized is an average over an operation sequence under a stated analysis; expected is an average over a random experiment. "Expected amortized" requires both pieces, with resizing, initialization, and rehash probes accounted for.
How To Use It
Specify a growth threshold, tombstone cleanup rule, and whether shrinking is supported. If shrinking, leave a gap between grow and shrink thresholds so alternating insert/delete operations do not trigger a full rebuild each time. The reference does not shrink; retained capacity follows historical peak usage. For each performance claim identify which implementation mechanism supports it.
Check Yourself
- What is random in universal hashing?
- Why does reducing arbitrary keys modulo p need care?
- Why can one resize be expensive despite an amortized bound?
- What cost does the geometric capacity sum fail to bound by itself?
Mini Drill or Application
Construct alternating updates that make identical grow/shrink thresholds thrash. Propose separated thresholds and derive the minimum intervening operations needed to pay for a rebuild. Then explain why this capacity argument alone does not bound collision probes. See P11; randomized-family implementation is optional.
Read This Only If Stuck
Use CLRS, Skiena, or Sedgewick and Wayne for universal hashing, geometric resizing, and expected amortized analysis. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.