Name
Abstract | ||
|---|---|---|
A perfect hash function (PHF) h : U → [0,m - 1] for a key set S is a function that maps the keys of S to unique values. The minimum amount of space to represent a PHF for a given set S is known to be approximately 1.44n2/m bits, where n = |S|. In this paper we present new algorithms for construction and evaluation of PHFs of a given set (for m = n and m = 1.23n), with the following properties: Evaluation of a PHF requires constant time. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73951-7_13 | WADS |
Keywords | Field | DocType |
minimum amount,following property,m bit,unique value,constant time,perfect hash function,new algorithm,space-efficient minimal perfect hash,linear time,hash function | Hash filter,Discrete mathematics,Combinatorics,Computer science,Rolling hash,Universal hashing,Perfect hash function,Hash function | Conference |
Volume | ISSN | ISBN |
4619 | 0302-9743 | 3-540-73948-3 |
Citations | PageRank | References |
47 | 1.80 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabiano C. Botelho | 1 | 174 | 11.06 |
| Rasmus Pagh | 2 | 1344 | 86.08 |
| Nivio Ziviani | 3 | 1598 | 154.65 |