Stable hash tables---hash tables that never move existing elements---are among the simplest and most widely used hashing schemes. Two canonical examples are stable uniform probing and stable linear probing. Both are commonly believed to support constant expected-time operations. However, formal proofs have long been obstructed by a subtle dependency issue known as reappearance dependency. While this dependency is widely conjectured to be essentially harmless, it has so far defeated all known analysis techniques.

 

In this talk, I show that this belief is only partially correct, in a surprising way. Stable uniform probing---despite provably outperforming linear probing in the insertion-only setting---can be severely affected by reappearance dependencies: there exists an oblivious update sequence under which the expected insertion time grows polynomially in the stable setting. In contrast, stable linear probing can be "rescued" from reappearance dependencies and still guarantees constant expected insertion time. Somewhat counterintuitively, the same locality that makes linear probing slower than uniform probing in the insertion-only setting turns out to be the key ingredient that allows it to overcome reappearance dependencies.

Jingxun Liang is a second-year PhD student in Computer Science at Carnegie Mellon University, coadvised by William Kuszmaul and Ryan O'Donnell. His research focuses on proving upper and lower bounds for classical data structures. He received his undergraduate degree from the Yao Class at Tsinghua University.