Perfect hashing functions: a single probe retrieving method for static sets

ABSTRACT

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 transforming the elements of I into unique addresses. The first method, the “quotient reduction” method, is shown to be complete in the sense that for every set I the smallest table in which the elements of I can be stored and from which they can be retrieved by using a perfect hashing function constructed by this method can be found. However, for nonuniformly distributed sets, this method can give rather sparse tables. The second method, the “remainder reduction” method, is not complete in the above sense, but it seems to give minimal (or almost minimal) tables for every kind of set. The two techniques are applicable directly to small sets. Some methods to extend these results to larger sets are also presented. A rough comparison with ordinary hashing is given which shows that this method can be used conveniently in several practical applications.

REFERENCES

• 1: Marek Greniewski , Wladyslaw Turski, The external language KLIPA for the URAL-2 digital computer, Communications of the ACM, v.6 n.6, p.321-324, June 1963 [doi>10.1145/366604.366654]
• 2: Knott, G.D. Hashing functions. Computer J. 18 (Aug. 1975), 265-278.
• 3: Knuth, D.E. An empirical study of FORTRAN programs. Software-Practice and Experience 1 (April 1971), 105-133.
• 4: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 5: W. D. Maurer , T. G. Lewis, Hash Table Methods, ACM Computing Surveys (CSUR), v.7 n.1, p.5-19, March 1975 [doi>10.1145/356643.356645]
• 6: Niven, I., and Zuckerman, H.S. An Introduction to the Theory of Numbers. Wiley, New York, 1960.
• 7: Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974 [doi>10.1145/356631.356633]

INDEX TERMS

Keywords:
direct addressing, hash coding, hashing, hashing methods, identifier-to-address transformations, perfect hash coding, perfect hashing functions, reduction, scatter storage, searching