Linear open addressing and Peterson's theorem rehashed (Q1104732)

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.