What if we tried Less Power? -- Lessons from studying the power of choices in hashing-based data structures

Abstract

In the first part of this survey, we review how the power of two choices underlies space-efficient data structures like cuckoo hash tables. We'll find that the additional power afforded by more than 2 choices is often outweighed by the additional costs they bring. In the second part, we present a data structure where choices play a role at coarser than per-element granularity. In some sense, we rely on the power of $1+\epsilon$ choices.

arXiv commentThis article appeared in the algorithms column of the bulletin of the EATCS, Issue Number 140, June 2023