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 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. CACM November, 1977 Sprugnoli, R. hashing, hashing methods, hash coding, direct addressing, identifier-to-address transformations, perfect hashing functions, perfect hash coding, reduction, scatter storage 3.7 3.74 4.34 CA771111 JB December 27, 1977 6:45 AM 2905 4 2905 2905 5 2905 2905 5 2905 2905 5 2905 3041 5 2905 3126 5 2905 3176 5 2905 829 5 2905 2846 6 2905 2905 6 2905 2905 6 2905 2905 6 2905