Optimal Arrangement of Keys in a Hash Table
Ronald L. Rivest · Journal of the ACM · 1978
When open addressing IS used to resolve collisions in a hash table, a given set of keys may be arranged in many ways, typically this depends on the order in which the keys are inserted It is shown that arrangements minimizing either the average or worst-case number of probes required to retrieve any key in the table can be found using an algorithm for the assignment problem.The worst-case retrieval time can be reduced to O(log2(M)) with probablhty 1 -e(M) when storing Mkeys In a table of size M, where ~(M)~ 0 as M ~ ~ We also examine insertion algorithms to see how to apply these ideas for a dynamically changing set of keys KEY WORDS AND PHRASES hashing, collision resolution, searching, assignment problem, optimal algorithms, database organization CR CATEGORIES 3 74, 5 41 "Spread the table and contention will cease "' Old English proverb [11, #¢272 6] General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyrlght notice is given and that reference is made to the pubhcatlon, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does repubhcation, or systematic or multiple reproduction This research was prepared with the support of the National Science Foundation