CHM Algorithm


The Algorithm

The algorithm is presented in [1,2,3].


Memory Consumption

Now we detail the memory consumption to generate and to store minimal perfect hash functions using the CHM algorithm. The structures responsible for memory consumption are in the following:

Thus, the total memory consumption of CHM algorithm for generating a minimal perfect hash function (MPHF) is: (8.125c + 16)n + O(1) bytes. As the value of constant c must be at least 2.09 we have:

c Memory consumption to generate a MPHF
2.09 33.00n + O(1)
Table 1: Memory consumption to generate a MPHF using the CHM algorithm.

Now we present the memory consumption to store the resulting function. We only need to store the g function. Thus, we need 4cn bytes. Again we have:

c Memory consumption to store a MPHF
2.09 8.36n
Table 2: Memory consumption to store a MPHF generated by the CHM algorithm.

Experimental Results

CHM x BMZ


Papers

  1. Z.J. Czech, G. Havas, and B.S. Majewski. An optimal algorithm for generating minimal perfect hash functions., Information Processing Letters, 43(5):257-264, 1992.

  2. Z.J. Czech, G. Havas, and B.S. Majewski. Fundamental study perfect hashing. Theoretical Computer Science, 182:1-143, 1997.

  3. B.S. Majewski, N.C. Wormald, G. Havas, and Z.J. Czech. A family of perfect hashing methods. The Computer Journal, 39(6):547--554, 1996.

Home CHD BDZ BMZ CHM BRZ FCH

Enjoy!

Davi de Castro Reis

Djamel Belazzougui

Fabiano Cupertino Botelho

Nivio Ziviani

VigLink badge