KIT | KIT-Bibliothek | Impressum | Datenschutz

Modern Minimal Perfect Hashing: A Survey

Lehmann, Hans-Peter ORCID iD icon 1; Mueller, Thomas; Pagh, Rasmus; Pibiri, Giulio Ermanno; Sanders, Peter ORCID iD icon 1; Vigna, Sebastiano; Walzer, Stefan ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

Given a set S of n keys, a perfect hash function for S maps the keys in S to the first m ≥ n integers without collisions. It may return an arbitrary result for any key not in S and is called minimal if m=n. The most important parameters are its space consumption, construction time, and query time. Years of research now enable modern perfect hash functions to be extremely fast to query, very space-efficient, and scale to billions of keys. Different approaches give different trade-offs between these aspects. For example, the smallest constructions get within 0.1% of the space lower bound of log$_2$ e bits per key. Others are particularly fast to query, requiring only one memory access. Perfect hashing has many applications, for example, to avoid collision resolution in static hash tables, and is used in databases, bioinformatics, and stringology.
Since the last comprehensive survey in 1997, significant progress has been made. This survey covers the latest developments and provides a starting point for getting familiar with the topic. Additionally, our extensive experimental evaluation can serve as a guide to select a perfect hash function for use in applications.


Verlagsausgabe §
DOI: 10.5445/IR/1000194855
Veröffentlicht am 01.07.2026
Originalveröffentlichung
DOI: 10.1145/3797036
Scopus
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsdatum 31.07.2026
Sprache Englisch
Identifikator ISSN: 0360-0300, 0010-4892, 1557-7341
KITopen-ID: 1000194855
Erschienen in ACM Computing Surveys
Verlag Association for Computing Machinery (ACM)
Band 58
Heft 10
Seiten 1–36
Vorab online veröffentlicht am 11.03.2026
Nachgewiesen in Scopus
OpenAlex
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page