Reducing the retrieval time of scatter storage techniques
13. R. P. Brent, Reducing the retrieval time of scatter storage techniques,
Communications of the ACM 16 (1973), 105-109.
Abstract:
dvi (2K),
pdf (27K),
ps (25K).
Paper:
pdf (407K).
Abstract
A new method for entering and retrieving information in a hash table
is described. The method is intended to be efficient if most entries
are looked up several times. The expected number of probes to look up
an entry, predicted theoretically and verified by Monte Carlo
experiments, is considerably less than for other comparable methods
if the table is nearly full. An example of a possible Fortran
implementation is given.
Erratum
A left parenthesis is missing in the caption to Figure 3.
Comments
The algorithm is described in
Knuth, Volume 3, Sorting and Searching.
There is a
comment,
by Feldman and Low, and a
reply,
in Communications of the ACM 16 (1973), 703.
For further comments see [63].
Go to next publication
Return to Richard Brent's index page