ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
Hans‐Peter Lehmann, Peter W. Sanders, Stefan Walzer · Society for Industrial and Applied Mathematics eBooks · 2024
A minimal perfect hash function (MPHF) maps a set S of n keys to the first n integers without collisions. There is a lower bound of n log2 ℓ — O(log n) bits of space needed to represent an MPHF. A matching upper bound is obtained using the brute-force algorithm that tries random hash functions until stumbling on an MPHF and stores that function's seed. In expectation, enpoly(n) seeds need to be tested. The most space-efficient previous algorithms for constructing MPHFs all use such a brute- force approach as a basic building block.