REDUCING THE RETRIEVAL TIME OF SCATTER STORAGE TECHNIQUES

RICHARD P. BRENT

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.

Comments

Only the Abstract is given here. The full paper appeared as [1].

References

1. R. P. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM 16 (1973), 105–109. Zbl 251.68019. Also appeared as A modified linear scatter storage technique, Report TR RC 3460, IBM Research, Yorktown Heights, New York (July 1971), 20 pp. See also “Comment on Brent’s scatter storage algorithm”, Communications of the ACM 16 (1973), 703.

IBM Thomas J. Watson Research Center, Yorktown Heights, New York Current address: Computer Centre, Australian National University, Canberra

1991 Mathematics Subject Classification. Primary 68P20; Secondary 68P05, 68P10. Key words and phrases. Address calculation, content addressing, file searching, hash addressing, hash

code, linear probing, linear quotient method, scatter storage, searching, symbol table.

CR Categories. 3.7, 3.73, 3.74, 4.1, 4.9. Received November 1971; revised January 1972. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1973, ACM, Inc. General permission to republish, but not for profit, all or part of this

material is granted, provided that reference is made to this publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb013a typeset using AMS-L^{A}TEX