Linear open addressing and Peterson's theorem rehashed (Q1104732)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear open addressing and Peterson's theorem rehashed |
scientific article |
Statements
Linear open addressing and Peterson's theorem rehashed (English)
0 references
1988
0 references
Linear open addressing is a venerable hashing collision resolution method which exhibits primary clustering when items are stored. Linear open addressing is a 1-successor method as defined herein, but such methods do not exhaust the class of primary clustering methods. Being a primary clustering method does not, therefore, characterize linear open addressing. Linear open addressing is shown here to be characterized, however, by a description due to \textit{W. W. Peterson} [IBM J. Res. Dev. 1, 130-146 (1957)] that the expected retrieval cost is independent of the order in which items arrive to be stored.
0 references
open addressing
0 references
hashing
0 references
clustering
0 references