A Practical Minimal Perfect Hashing Method (2005) 计算机科学

A Practical Minimal Perfect Hashing Method�Fabiano C. Botelho1, Yoshiharu Kohayakawa2, and Nivio Ziviani11 Dept. of Computer Science, Federal Univ. of Minas Gerais, Belo Horizonte, Brazil {fbotelho, nivio}@dcc.ufmg.br2 Dept. of Computer Science, Univ. of São Paulo, São Paulo, Brazil yoshi@ime.usp.brAbstract. 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