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