Peeling Close to the Orientability Threshold: Spatial Coupling in Hashing-Based Data Structures

Stefan Walzer

In multiple-choice data structures each element $x$ in a set $S$ of $m$ keys is associated with a random set $e(x)\subseteq [n]$ of buckets with capacity $\ell \ge 1$ by hash fun…