Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11427186_42 | WEA |
Keywords | Field | DocType |
expected time,memory access,novel algorithm,algorithm outputs h,space requirement,n key,large scale,time complexity,minimal perfect hash function,random graph,hash function | Discrete mathematics,Algorithmics,Computer science,Algorithm,Hash function,Perfect hash function,Time complexity,Consistent hashing,2-choice hashing,Dynamic perfect hashing,Hash table | Conference |
Volume | ISSN | ISBN |
3503 | 0302-9743 | 3-540-25920-1 |
Citations | PageRank | References |
14 | 1.47 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabiano C. Botelho | 1 | 174 | 11.06 |
| Yoshiharu Kohayakawa | 2 | 477 | 64.87 |
| Nivio Ziviani | 3 | 1598 | 154.65 |