Greedy Open Addressing Revisited: Beyond Yao's Lower Bound

In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to 1 − є full, must incur an amortized expected query time of at least Ω(logє−1). To overcome this lower bound, prior work has focused on modifying the setup of the insertion algorithm, by either reordering items or placing items non-greedily. We show that, in fact, no such modifications are necessary: by simply decoupling the greedy query algorithm from the greedy insertion algorithm, it is possible to get an amortized expected query time of O(1). The same relaxation also lets us bypass a barrier for worst-case expected query time, bringing the bound down to O(logє−1). Finally, we show how to achieve both of these query bounds while also achieving near-optimal insertion times, for both solutions that do and solutions that do not know the parameter є beforehand.