Tight Bounds for Classical Open Addressing

We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to 1 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$-\varepsilon$</tex>, while also supporting <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(1)$</tex> expected-time queries, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O\left({\log \,\log {\varepsilon ^{ - 1}}} \right)$</tex> expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1-\varepsilon$</tex> must incur <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega \left({\log \,log{\varepsilon ^{ - 1}}} \right)$</tex> expected time per operation. Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost-even while maintaining a load factor of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\geq 1-\varepsilon$</tex> at all times, we can support <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(1)$</tex> queries and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O\left({\log \,\log {\varepsilon ^{ - 1}}} \right)$</tex> updates. Prior to our work, achieving any time bounds of the form <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$o(\varepsilon^{-1})$</tex> for all of insertions, deletions, and queries simultaneously remained an open Question.