Engineering / Mathematics — Discrete Probability
Hash Tables
Hash tables analysed with universal families: expected chain length, load factor and collision resolution.
Executive summary
A hash table stores items in buckets indexed by a hash of the key. With a universal family the expected number of items sharing a bucket is bounded by the load factor, giving constant expected lookup time.
The guarantee is over the choice of hash function, which is what makes it robust against adversarially chosen keys.
Learning objectives
- Analyse expected chain length under a universal family.
- Relate load factor to performance.
- Compare chaining with open addressing.
01The chaining analysis
Suppose n items are stored in m buckets using a universal family. Fix a query key x and count the items colliding with it.
Expected chain length
The expected number of stored items hashing to the same bucket as x is at most n/m, the load factor.
Proof. Sum indicators over stored items. Each collides with probability at most 1/m by universality, and linearity of expectation gives the bound with no independence between items required.
Keeping the load factor bounded by a constant, typically by doubling the table when it is exceeded, gives constant expected lookup cost.
02Load factor and resizing
| Load factor | Expected chain | Behaviour |
|---|---|---|
| 0.5 | 0.5 | Fast; memory-hungry |
| 0.75 | 0.75 | Common default for chaining |
| 1.0 | 1.0 | Acceptable for chaining, poor for open addressing |
| > 2 | > 2 | Degrading; resize overdue |
Doubling the table on exceeding a threshold gives amortised constant insertion: each resize costs linear time but occurs after linearly many insertions, so the cost per insertion is constant when averaged.
03Chaining versus open addressing
Chaining
Each bucket holds a list. Tolerates load factors near or above one, needs pointer storage, and degrades gracefully.
Open addressing
Items are placed in the table itself following a probe sequence. Better cache behaviour, no pointers, but degrades sharply as the load factor approaches one and deletion requires tombstones.
04Frequently asked questions
Does the analysis need the stored keys to be random?
No, and this is the point of using a family. The keys may be adversarial; the randomness is in the choice of hash function, so the expectation holds for every fixed key set.
Why is worst-case lookup still linear?
Because an unlucky key choice can put every item in one bucket. The guarantee is on the expectation, not the worst case. Perfect hashing achieves worst-case constant lookup for a static key set at the cost of construction time.
How large should the table be relative to the item count?
Enough to keep the load factor below the chosen threshold. For chaining, thresholds near one work well; for open addressing, staying below about 0.7 avoids sharp degradation in probe counts.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 127-128.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.