Hash Tables Like Onions

Greedy open addressing is an extremely popular template for building hash tables, but it suffers from a fundamental drawback: performance degrades as the table fills up. In particular, if a table is filled to a 1-1/x fraction full, the expected amortized query time, or the time to query a random element, is Omega(log x), proven by Yao in his seminal paper "Uniform Hashing is Optimal." Not to fret, though! In this talk, we present a very simple tweak to bypass this lower bound and achieve an amortized expected query time of O(1). In addition, we survey several related results in open addressing that all share a curious theme: the hash table is partitioned into layers of geometrically decreasing size.