Abstract
We propose a novel algorithm based on random graphs to construct minimal perfect hash functions h. For a set of n keys, our algorithm outputs h in expected time O(n). The evaluation of h(x) requires two memory accesses for any key x and the description of h takes up 1.15n words. This improves the space requirement to 55% of a previous minimal perfect hashing scheme due to Czech, Havas and Majewski. A simple heuristic further reduces the space requirement to 0.93n words, at the expense of a slightly worse constant in the time complexity. Large scale experimental results are presented.
This work was supported in part by GERINDO Project–grant MCT/CNPq/CT-INFO 552.087/02-5, CAPES/PROF Scholarship (Fabiano C. Botelho), FAPESP Proj. Tem. 03/09925-5 and CNPq Grant 30.0334/93-1 (Yoshiharu Kohayakawa), and CNPq Grant 30.5237/02-0 (Nivio Ziviani).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bollobás, B.: Random graphs, 2nd edn. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge University Press, Cambridge (2001)
Bollobás, B., Pikhurko, O.: Integer sets with prescribed pairwise differences being distinct. European Journal of Combinatorics (to appear)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Czech, Z.J., Havas, G., Majewski, B.S.: An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters 43(5), 257–264 (1992)
Czech, Z.J., Havas, G., Majewski, B.S.: Fundamental study perfect hashing. Theoretical Computer Science 182, 1–143 (1997)
Dietzfelbinger, M., Hagerup, T.: Simple minimal perfect hashing in less space. In: Meyer auf der Heide, F. (ed.) ESA 2001, vol. 2161, pp. 109–120. Springer, Heidelberg (2001)
Erdős, P., Rényi, A.: On random graphs I. Pub. Math. Debrecen 6, 290–297 (1959)
Erdős, P., Rényi, A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5, 17–61 (1960)
Fox, E.A., Chen, Q.F., Heath, L.S.: A faster algorithm for constructing minimal perfect hash functions. In: Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 266–273 (1992)
Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a sparse table with O(1) worst case access time. J. ACM 31(3), 538–544 (1984)
Havas, G., Majewski, B.S., Wormald, N.C., Czech, Z.J.: Graphs, hypergraphs and hashing. In: van Leeuwen, J. (ed.) WG 1993, vol. 790, pp. 153–165. Springer, Heidelberg (1994)
Janson, S., Łuczak, T., Ruciński, A.: Random graphs. Wiley-Inter., Chichester (2000)
Erdős, P., Rényi, A.: On the strength of connectedness of a random graph. Acta Mathematica Scientia Hungary 12, 261–267 (1961)
Pagh, R.: Hash and displace: Efficient evaluation of minimal perfect hash functions. In: Workshop on Algorithms and Data Structures, pp. 49–54 (1999)
Pittel, B., Wormald, N.C.: Counting connected graphs inside-out. Journal of Combinatorial Theory (to appear)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Botelho, F.C., Kohayakawa, Y., Ziviani, N. (2005). A Practical Minimal Perfect Hashing Method. In: Nikoletseas, S.E. (eds) Experimental and Efficient Algorithms. WEA 2005. Lecture Notes in Computer Science, vol 3503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11427186_42
Download citation
DOI: https://doi.org/10.1007/11427186_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25920-6
Online ISBN: 978-3-540-32078-4
eBook Packages: Computer ScienceComputer Science (R0)