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 \(1+\epsilon\) choices.
Similar Work