Piotr Beling

The paper introduces PHast, (minimal) perfect hash function that combines the fastest available queries, very fast construction (especially PHast+ variant), and good space consumption (below 2 bits per key).

Perfect hash functions give unique “names” to arbitrary keys requiring only a few bits per key. This is an essential building block in applications like static hash tables, databases, or bioinformatics. This paper introduces the PHast approach that combines the fastest available queries, very fast construction, and good space consumption (below 2 bits per key). PHast improves bucket-placement which first hashes each key \(k\) to a bucket, and then looks for the bucket seed \(s\) such that a placement function maps pairs \((s,\, k)\) in a collision-free way. PHast can use smallrange hash functions with linear mapping, fixed-width encoding of seeds, and parallel construction. This is achieved using small overlapping slices of allowed values and bumping to handle unsuccessful seed assignment. A variant we called PHast+ uses additive placement, which enables bit-parallel seed searching, speeding up the construction by an order of magnitude. This paper has been awarded the “Code and Data Available” and “Results Reproduced” badges as recognition that the author(s) have followed reproducibility principles. Code and data that allow readers to reproduce the results in this paper are available at https://doi.org/10.6084/m9.figshare.30272380.v6. Participation in the ALENEX artifact evaluation phase was optional and performed at the request of the author(s).

@inbook{doi:10.1137/1.9781611978957.1, author = {Piotr Beling and Peter Sanders}, title = {PHast – Perfect Hashing made fast}, booktitle = {2026 Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)}, chapter = {}, pages = {1-14}, doi = {10.1137/1.9781611978957.1}, URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611978957.1}, eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611978957.1}, abstract = { Perfect hash functions give unique “names” to arbitrary keys requiring only a few bits per key. This is an essential building block in applications like static hash tables, databases, or bioinformatics. This paper introduces the PHast approach that combines the fastest available queries, very fast construction, and good space consumption (below 2 bits per key). PHast improves bucket-placement which first hashes each key \(k\) to a bucket, and then looks for the bucket seed \(s\) such that a placement function maps pairs \((s,\, k)\) in a collision-free way. PHast can use smallrange hash functions with linear mapping, fixed-width encoding of seeds, and parallel construction. This is achieved using small overlapping slices of allowed values and bumping to handle unsuccessful seed assignment. A variant we called PHast+ uses additive placement, which enables bit-parallel seed searching, speeding up the construction by an order of magnitude. This paper has been awarded the “Code and Data Available” and “Results Reproduced” badges as recognition that the author(s) have followed reproducibility principles. Code and data that allow readers to reproduce the results in this paper are available at https://doi.org/10.6084/m9.figshare.30272380.v6. Participation in the ALENEX artifact evaluation phase was optional and performed at the request of the author(s). } }