Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Perfect and minimal perfect hashing

What does fixing the key set buy, and which question does a perfect hash push elsewhere?

Perfect hashing and minimal perfect hashing

The constraint, inverted. Every structure so far reserves capacity for keys it has not yet seen. If the key set is static and known at build time, that reservation is pure waste. You can compute a collision-free function over exactly those keys. A perfect maps each known key to a different slot. A (MPHF) maps n known keys to exactly n slots with no gaps. Lookup is one probe with no key comparison, and the function itself costs 1.44 bits per key at the information-theoretic floor (the proven minimum), and 2 to 3 bits per key in practice, independent of key length.

State the catch precisely

An MPHF maps known keys to distinct slots, and maps unknown keys to arbitrary slots. It is not a membership structure. Ask it about a key that was not in the build set, and it confidently returns someone else's position. So it must be paired with verification (store a short next to each slot and compare), or used where absence is structurally impossible. The question "does this key exist?" was not answered by the structure. It was evicted from it, and someone downstream now owns it. That eviction is what the space saving bought.

Immutability is a resource

This is the reason this item matters more than its obscurity suggests. (). It is a resource that can be spent. A structure that knows its contents are final can drop every mechanism that exists to accommodate change (free-space management, split logic, rebalancing, load-factor headroom) and approach the bound.

A corollary explains a pattern you will keep seeing: structures that need a full rebuild are free-riders on systems that already rebuild. MPHFs, , and all live in segment-based systems, such as Lucene segments, LSM SSTables and Parquet files, because is already paying the rebuild cost for other reasons. The marginal cost of a rebuild-only structure there is zero. Together with the Immutability law you now have both sides of the immutability ledger: it costs a , and it pays a dividend in compactness.