@Article{Riv78b, author = { Ronald L. Rivest }, title = { Optimal arrangement of keys in a hash table }, url = { http://doi.acm.org/10.1145/322063.322065 }, doi = { 10.1145/322063.322065 }, acmid = { 322065 }, pages = { 200--209 }, acm = { 2412 }, journal = { JACM }, OPTyear = { 1978 }, OPTmonth = { April }, date = { 1978-04 }, volume = { 25 }, number = { 2 }, issn = { 0004-5411 }, publisher = { ACM }, keywords = { hashing, collision resolution, searching, assignment problem, optimal algorithms, database organization }, abstract = { 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(\log_2(M))$ with probability $1=\epsilon(M)$ when storing $M$ keys in a table of size $M$, where $\epsilon(M)\rightarrow 0$ as $M\rightarrow\infty$. We also examine insertion algorithms to see how to apply these ideas for a dynamically changing set of keys. }, }