Search tools and guides ⌘K
III · Hashing & lookup

Perfect hashing

Zero collisions, by design.

1984 · Fredman, Komlós & Szemerédi
The story

For static sets — keys known in advance — you can do better than "average O(1)" — you can guarantee worst-case O(1). Fredman et al's "FKS" scheme uses a two-level hash; later constructions (CHD, BBHash, FCH) use only O(n) bits beyond the keys themselves, with O(1) guaranteed lookup.

How it works

Top-level hash function maps n keys to n buckets, with O(1) expected collisions per bucket. Each non-empty bucket gets its own perfect hash function for its 2–3 keys. Construction is randomised; expected O(n) time.

Where it lives

Compiled language keyword lookup (CPython, V8). gperf-generated tables. Static dictionaries in scientific software. Python's "frozen" dicts in some contexts.

The key insight

Perfect hashing trades update flexibility for worst-case guarantees. Used wherever a set is built once and queried billions of times — the keyword tables in every compiler, for instance.

More in Hashing & lookup
Hash table O(1), almost always. Cuckoo hashing Two slots, no chains. Robin Hood hashing Steal from the rich, give to the poor. Consistent hashing Hashing that survives node changes.
Across the cabinet
IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor. VI Adjacency list Each node, its neighbours. VI Disjoint Set / Union-Find Track connected components, in a forest.
← All data structures