G. Jaeschke
Abstract
A method is presented for building minimal perfect hash functions, i.e., functions which allow single probe retrieval from minimally sized tables of identifier sets. A proof of existence for minimal perfect hash functions of a special type (reciprocal type) is given. Two algorithms for determining hash functions of reciprocal type are presented and their practical limitations are discussed. Further, some application results are given and compared with those of earlier approaches for perfect hashing.
- 1 Cichelli, R.J. Minimal perfect hash functions made simple. Comm. ACM, 23, 1 (Jan. 1980), 17-19. Google Scholar
Digital Library
- 2 Greniewski, M., and Turski, W. The external language KLIPA for the URAL-2 digital computer. Comm. ACM, 6, 6 (June 1963), 322- 324. Google ScholarDigital Library
- 3 Jaeschke, G. Minimal perfect hashing. Tech. Rept. TR 80.02.003, IBM Heidelberg Scientific Center, Niederlassung Heidelberg, Germany.Google Scholar
- 4 Jaeschke, G., Osterburg, G. On Cichelli's minimal perfect hash functions method. Comm. ACM, 23, 12 (Dec. 1980), 728-729.Google Scholar
- 5 Knott, G.D. Hashing functions. Computer J., 18 (Aug. 1975), 265-278.Google ScholarCross Ref
- 6 Leveque, W. J. Topics in Number Theory. Addison-Wesley, Reading, Mass., 1956.Google Scholar
- 7 Sprugnoli, R. Perfect hashing functions: a single probe retrieving method for static sets. Comm. ACM, 20, 11 (Nov. 1977), 841-850. Google ScholarDigital Library
Index Terms
- Reciprocal hashing: a method for generating minimal perfect hashing functions
Recommendations
Perfect hashing functions: a single probe retrieving method for static sets
A refinement of hashing which allows retrieval of an item in a static table with a single probe is considered. Given a set I of identifiers, two methods are presented for building, in a mechanical way, perfect hashing functions, i.e. functions ...
Minimal perfect hash functions made simple
A method is presented for computing machine independent, minimal perfect hash functions of the form: hash value ← key length + the associated value of the key's first character + the associated value of the key's last character. Such functions allow ...
Minimal perfect hashing: A competitive method for indexing internal memory
A perfect hash function (PHF) is an injective function that maps keys from a set S to unique values. Since no collisions occur, each key can be retrieved from a hash table with a single probe. A minimal perfect hash function (MPHF) is a PHF with the ...
Comments