Hash tables with chaining
A hash table maps keys to buckets and stores colliding keys in a chain.
Key knowledge
A hash table maps keys to buckets and stores colliding keys in a chain. With load factor α=n/m and a suitably randomized universal hash family, lookup takes expected O(1+α); an adversarial collision pattern can instead require O(n).
Conditions and scope
- The expectation is over the hash choice, with the stored keys and queried key fixed independently of that random choice. Universality alone does not guarantee this bound for keys chosen adaptively after observing the hash.
- Keep α bounded through resizing for expected constant operation cost.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture 4 chaining, universal hashing and collision-bound analysis for fixed key pairs, pages 3–5.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-hash-chaining
- Revision
- university-core.1
- Structured reference record
- University core expansion