TY - GEN
T1 - Optimal Bounds for Open Addressing Without Reordering
AU - Farach-Colton, Martin
AU - Krapivin, Andrew
AU - Kuszmaul, William
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper 'Uniform Hashing is Optimal'.
AB - In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper 'Uniform Hashing is Optimal'.
UR - http://www.scopus.com/inward/record.url?scp=85213063757&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85213063757&partnerID=8YFLogxK
U2 - 10.1109/FOCS61266.2024.00045
DO - 10.1109/FOCS61266.2024.00045
M3 - Conference contribution
AN - SCOPUS:85213063757
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 594
EP - 605
BT - Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024
PB - IEEE Computer Society
T2 - 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024
Y2 - 27 October 2024 through 30 October 2024
ER -