2026-08-25T18:47:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27156 2026-08-25T13:18:16Z ddc:004 open_access

Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables Groot Koerkamp, Ragnar Hermann, Stefan Sanders, Peter Walzer, Stefan Compressed Data Structures k-Perfect Hashing Hash Table Space Lower Bound A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of n keys to n bins without collisions. Two natural generalizations are minimal k-PHFs where n keys are mapped to n/k bins of capacity k each, and (non-minimal) PHFs with load factor α < 1 where the number of bins is increased by a factor of 1/α, resulting in spare capacity. While there has been a recent surge of interest in perfect hashing generally, non-minimal k-PHFs have not been systematically studied despite a natural use case of speeding up static hash tables: The idea is that a small cache-resident k-PHF maps each key x to a cache-line-sized bin of capacity k where x resides. Ideally, this yields a branchless lookup operation with a single cache miss working at high load factors for positive and negative queries alike. Our main theoretical contribution is to determine tight space lower bounds for k-PHFs for all pairs of α ∈ (0,1] and k ≥ 1. It turns out that combining α < 1 and k ≥ 2 drastically reduces the space of k-PHFs, e.g. for (k,α) = (16,0.8) the space lower bound is 0.027 bits per key while for (k,α) = (16,1.0) and (k,α) = (1,0.8) the lower bounds are higher by factors of ≈ 8 and ≈ 32, respectively. On the practical side, we develop a k-PHF based on PtrHash and tune it for use in static hash tables. Empirically, our implementation produces k-PHFs of size roughly 50% above the lower bound. A static hash set based on this k-PHF is consistently at least as fast as other hash sets for negative and mixed queries. On two of the three tested architectures it achieves up to 1.5× speedup for large n ≥ 30M where a 1-PHF does not fit in cache. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ragnar Groot Koerkamp and Stefan Hermann and Peter Sanders and Stefan Walzer 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.20 urn:nbn:de:0030-drops-271565 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode