Optimal Bounds for Open Addressing Without Reordering

20^th May 2025, 13:00 Ashton Lecture Theatre
Andrew Krapivin
University of Cambridge

Abstract

In this talk, 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''. All of our results come with matching lower bounds.

Additional Materials

• https://arxiv.org/abs/2501.02305