DROPS

Artifact

Software

Engineering Minimal k-Perfect Hash Functions

Authors: Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, and Stefan Walzer

Abstract

Cite as

Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Stefan Walzer. Engineering Minimal k-Perfect Hash Functions (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{sourceCodekPHF,
   title = {{Engineering Minimal k-Perfect Hash Functions}}, 
   author = {Hermann, Stefan and Kirmayer, Sebastian and Lehmann, Hans-Peter and Walzer, Stefan},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:e6756f018691a80adc68d839fd3617d8f5e2d0b0;origin=https://github.com/stefanfred/engineering-k-perfect-hashing;visit=swh:1:snp:8b568d1c8fe1e13f6ef95d3b2774fc59c259d6b5;anchor=swh:1:rev:2c269037dad34b69a68b56fed38c98656f02c133}{\texttt{swh:1:dir:e6756f018691a80adc68d839fd3617d8f5e2d0b0}} (visited on 2025-10-01)},
   url = {https://github.com/stefanfred/engineering-k-perfect-hashing},
   doi = {10.4230/artifacts.24698},
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.99

Engineering Minimal k-Perfect Hash Functions

Authors: Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

Given a set S of n keys, a k-perfect hash function (kPHF) is a data structure that maps the keys to the first m integers, where each output integer can be hit by at most k input keys. When m = ⌈n/k⌉, the resulting function is called a minimal k-perfect hash function (MkPHF). Applications of kPHFs can be found in external memory data structures or to create efficient 1-perfect hash functions, which in turn have a wide range of applications from databases to bioinformatics. Several papers from the 1980s look at external memory data structures with small internal memory indexes. However, actual k-perfect hash functions are surprisingly rare, and the area has not seen a lot of research recently. At the same time, recent research in 1-perfect hashing shows that there is a lack of efficient kPHFs. In this paper, we revive the area of k-perfect hashing, presenting four new constructions. Our implementations simultaneously dominate older approaches in space consumption, construction time, and query time. We see this paper as a possible starting point of an active line of research, similar to the area of 1-perfect hashing.

Cite as

Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Peter Sanders, and Stefan Walzer. Engineering Minimal k-Perfect Hash Functions. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 99:1-99:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hermann_et_al:LIPIcs.ESA.2025.99,
  author =	{Hermann, Stefan and Kirmayer, Sebastian and Lehmann, Hans-Peter and Sanders, Peter and Walzer, Stefan},
  title =	{{Engineering Minimal k-Perfect Hash Functions}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{99:1--99:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.99},
  URN =		{urn:nbn:de:0030-drops-245685},
  doi =		{10.4230/LIPIcs.ESA.2025.99},
  annote =	{Keywords: Compressed Data Structures, Perfect Hashing}
}

Search Results

Documents authored by Kirmayer, Sebastian

Engineering Minimal k-Perfect Hash Functions

Abstract

Cite as

Engineering Minimal k-Perfect Hash Functions

Abstract

Cite as

Thanks for your feedback!

Could not send message