Linear open addressing and Peterson's theorem rehashed
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.
- A Note on the Efficiency of Hashing Functions
- An Occupancy Discipline and Applications
- Computer Science and Its Relation to Mathematics
- Direct-chaining with coalescing lists
- Hashing functions
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- Optimal Arrangement of Keys in a Hash Table
- Ordered hash tables
- Reducing the retrieval time of scatter storage techniques
- Some properties of the scatter storage technique with linear probing
This page was built for publication: Linear open addressing and Peterson's theorem rehashed
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104732)
