File PerfectHashing.h

↰ Parent directory (ADS/dictionary)

Perfect hashing of a static set, beyond the book: a function is perfect on a set S of n keys if it has no collision on S, minimal if its range is :math:` { 0 , ldots , n - 1 } , and order preserving if it maps the keys in their order; a table built on it searches in O( 1 ) time in the worst case, as the table with direct access [see :ref:`file_ADS_dictionary_DirectTable.h], but in O( n ) space instead of the size of the universe.

Definition (ADS/dictionary/PerfectHashing.h)

Detailed Description

  • PerfectHashTable is the two-level scheme of Fredman, Komlós and Szemerédi: the n keys are hashed into n lists by a function h of the class of Carter and Wegman [see CarterWegmanHash], drawn again until :math:` L = sum_j n_j^2 < 2 n , :math: n_j ` being the keys of the list j (the expected L is below 2 n, since :math:` sum_j binom{n_j}{2} ` counts the collisions of h); the list j becomes a table of :math:` n_j^2 ` places with a function :math:` h_j ` of its own, drawn again until it has no collision, which happens with probability at least 1 / 2 since the expected collisions of :math:` n_j ` keys in :math:` n_j^2 ` places are below 1 / 2. A search computes h and :math:` h_j ` and compares one key: two accesses in the worst case, :math:` O( n ) ` expected time to build, below 3 n places in all. Its dynamic version, by Dietzfelbinger et al., also inserts and removes in O( 1 ) amortized expected time; the compressed schemes of today (CHD of Belazzougui, Botelho and Dietzfelbinger, RecSplit of Esposito, Mueller Graf and Vigna) need about 2 and 1.6 bits per key instead of words.

  • OrderedMinimalPerfectHash is the scheme of Czech, Havas and Majewski: r = 2 functions map each key t to the edge :math:` ( h_1( t ) , h_2( t ) ) ` of a random graph of :math:` m’ = c n ` vertices, labelled by the value wanted for t (its place in the input, i.e., its rank if the input is sorted); if the graph is acyclic, a visit of each tree from a root with :math:` g = 0 ` solves :math:` g( u ) + g( v ) = h( t ) bmod n ` on each edge (Algorithms 8.1 and 8.2 of the notes, labelAcyclicGraph()), and :math:` h( t ) = ( g( h_1( t ) ) + g( h_2( t ) ) ) bmod n ` is the function. For :math:` c > 2 ` the graph is acyclic with probability about :math:` sqrt{( c - 2 ) / c} , i.e., about two graphs for c = 3; with r = 3 functions into three blocks of vertices the edges are triples, the hypergraph is solved in the reverse order of its peeling (the removal of the vertices of degree 1, labelByPeeling()), and :math: c > 1.23 ` is enough, i.e., :math:` 1.23 n ` values instead of :math:` 3 n . It stores no key: O( m’ ) words, O( 1 ) time to evaluate, O( n ) expected time to build; unlike a trie [see :ref:`file_ADS_dictionary_PatriciaTrie.h] it gives nothing meaningful for a key out of S, but its space does not depend on the length of the keys.

The keys of PerfectHashTable are integers below :math:` 2^{61} - 1 , the prime of its functions; those of OrderedMinimalPerfectHash are integers or strings, turned into integers by StringHash [see :ref:`file_ADS_dictionary_UniversalHashing.h] or splitmix64() before the functions of Carter and Wegman.

The contracts [see File Contract.h]: the keys distinct (an audit), below :math:` 2^{61} - 1 ` for PerfectHashTable and fewer than :math:` 2^{32} ` for OrderedMinimalPerfectHash, r = 2 with c > 2 or r = 3 with c > 1.23, the vertices of an edge distinct for labelByPeeling(); after a build each key is found, or mapped to its value, an audit; a labelling satisfies every edge, a postcondition. A build that draws 1000 functions of the first level, or 1000 graphs, with no success throws std::runtime_error, which for distinct keys has a probability below :math:` 2^{-100} `. The functions are defined in PerfectHashing.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 8 (sections 8.4 and 8.5)

    1. Fredman, J. Komlós, E. Szemerédi, Storing a sparse table with O(1) worst case access time, Journal of the ACM 31(3), 538-544, 1984, doi:10.1145/828.1884

    1. Czech, G. Havas, B. S. Majewski, An optimal algorithm for generating minimal perfect hash functions, Information Processing Letters 43(5), 257-264, 1992, doi:10.1016/0020-0190(92)90220-P

    1. Majewski, N. C. Wormald, G. Havas, Z. J. Czech, A family of perfect hashing methods, The Computer Journal 39(6), 547-554, 1996, doi:10.1093/comjnl/39.6.547

  1. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. E. Tarjan, Dynamic perfect hashing: upper and lower bounds, SIAM Journal on Computing 23(4), 738-761, 1994, doi:10.1137/S0097539791194094

  1. Belazzougui, F. C. Botelho, M. Dietzfelbinger, Hash, displace, and compress, Proceedings of ESA 2009, LNCS 5757, 682-693, 2009, doi:10.1007/978-3-642-04128-0_61

  2. Esposito, T. Mueller Graf, S. Vigna, RecSplit: minimal perfect hashing via recursive splitting, Proceedings of ALENEX 2020, 175-185, 2020, doi:10.1137/1.9781611976007.14

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes