What If We Tried Less Power -- Lessons From Studying The Power Of Choices In Hashing-based Data Structures
Walzer Stefan. Arxiv 2023
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
Similar Work