hesela.devMinimal perfect hash function
A minimal perfect hash function maps a fixed set of n distinct keys bijectively to n consecutive indices without identifying every key outside that set.
Minimality concerns the output range: n keys occupy exactly n indices. It does not mean that the representation uses the least possible memory. The collision-free guarantee applies to the construction set, not every possible query. [1]
Membership: A valid index is not proof that a key exists. An exact dictionary can keep the full key at each assigned index and compare it with the query before returning its value. A short fingerprint permits false matches and is a different contract. [3]
BBHash assigns noncolliding keys at successive bit-vector levels and uses rank to obtain dense indices. Colliding construction keys continue to later levels. Its lookup can return ULLONG_MAX for an absent key, but can also return another key's index; checking only that sentinel is insufficient. [2] [3]
Storage use: The function plus an indexed value array implements retrieval for a static key set. Values may change without changing the key set, but adding keys needs a construction or update strategy. Function-size figures exclude the separate values and membership evidence. [1]
Relations
Citations
- Lehmann et al. Modern Minimal Perfect Hashing: A Survey. arXiv:2506.06536v3, sections 1-2.
- Limasset, Rizk, Chikhi and Peterlongo. Fast and Scalable Minimal Perfect Hashing for Massive Key Sets. SEA 2017, section 2.
- BBHash README: querying keys outside the input set, commit be4220c8f8580299b212a0c6c6c867528a0f07ac.
- Hesela: pinned BBHash membership replay, source, method and receipt.
Sources & caveats
- The survey sections 1-2 and SEA 2017 method section support the scope distinction; historical benchmark rankings are not repeated.
- Pinned BBHash lookup code and an executable finite synthetic-key replay check membership behavior, not throughput or a population false-positive rate. [4]