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
    0 references
    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

    Identifiers