File MinimalPerfectHash.h

↰ Parent directory (ADS/dictionary)

The minimal perfect hash function of Namespace ADS by pilots, the method of PTHash of Pibiri and Trani, beyond the book [see File PerfectHashing.h for the schemes of Fredman, Komlós and Szemerédi and of Czech, Havas and Majewski]: a function that maps the n distinct keys of a static set S onto :math:` { 0 , ldots , n - 1 } ` with no collision, in a few bits per key (about 3 for the default parameters) and with two accesses to memory per evaluation.

Definition (ADS/dictionary/MinimalPerfectHash.h)

Detailed Description

A key with the hashes :math:` ( h , h’ ) ` goes to the bucket b( h ) of about :math:` n / lambda ` buckets, 60 % of the keys into 30 % of the buckets (the skewed buckets of PTHash, so that the large buckets are placed while the table is still empty), and to the place :math:`[

p = lfloor m , g( h’ oplus pi_{b( h )} ) / 2^{64} rfloor

` of a table of :math:` m = lceil n / alpha rceil ` places, where g is a folded product and :math:` pi_b ` is the pilot of the bucket b, a product of the integer :math:` k_b ` (the one stored) by an odd constant. The build places the buckets from the largest to the smallest, trying for each one the integers :math:` k_b = 0 , 1 , 2 , ldots ` until all its keys fall in free places, distinct among them; the expected number of trials of a bucket grows as the table fills, :math:` 1 / ( 1 - text{load} )^s ` for a bucket of s keys, so that the larger buckets go first. The integers :math:` k_b ` are stored in :math:` lceil log_2 ( max_b k_b + 1 ) rceil ` bits each (the compact encoding of PTHash), and a place p >= n of a key is sent to one of the places below n left free, by a table of the m - n places beyond n ( :math:` alpha < 1 ` makes the search of the last buckets much faster, at the cost of this table).

The search of the last buckets, placed when few places are left, is the bottleneck of the build: a large lambda leaves no bucket of one key for the end, and with alpha near 1 some bucket may find no pilot within its limit, so that lambda should stay below about 7 for alpha = 0.99, as in the experiments of PTHash (lambda from 3 to 7).

An evaluation computes the two hashes, the bucket, reads the k of the bucket (one access), computes the place and, for a place beyond n, reads the table of the free places (a second access, for about 1 - alpha of the keys). For a key out of S the result is some place below n.

The keys are hashed by h( k ), taken as it is if H declares is_avalanching [see File FastHash.h] and mixed by hashWord() otherwise; the two hashes of the build are two folded products of that hash XOR the seed. Two keys with the same hash of 64 bits and the same seed cannot be separated, and a build that meets them, or a bucket that tries :math:` 2^{24} ` pilots, draws a new seed.

The contracts [see File Contract.h]: the keys distinct (an audit), fewer than :math:` 2^{32} , :math: lambda ge 1 ` and :math:` 0.5 le alpha le 1 `; after the build the keys are mapped onto { 0 , … , n - 1 }, an audit. A build that draws 100 seeds with no success throws std::runtime_error. The operations are defined in MinimalPerfectHash.tpp.

    1. Pibiri, R. Trani, PTHash: revisiting FCH minimal perfect hashing, Proceedings of SIGIR 2021, 1339-1348, 2021, doi:10.1145/3404835.3462849

    1. Pibiri, R. Trani, Parallel and external-memory construction of minimal perfect hash functions with PTHash, IEEE Transactions on Knowledge and Data Engineering 36(3), 1249-1259, 2024

  1. Hermann, H.-P. Lehmann, G. E. Pibiri, P. Sanders, S. Walzer, PHOBIC: perfect hashing with optimized bucket sizes and interleaved coding, Proceedings of ESA 2024, LIPIcs 308, 69, 2024

    1. Fox, Q. F. Chen, L. S. Heath, A faster algorithm for constructing minimal perfect hash functions, Proceedings of SIGIR 1992, 266-273, 1992 (the buckets and their displacements)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes