Preprint
Sep 2026
The Power of Two-Choice Linear Probing
This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected insertion and query time, as a function of the load factor $1 - \epsilon$? We prove that the \emph{greedy two-choice insertion strategy} ac...
Amir Azarmehr, Michael A. Bender, William Kuszmaul et al.
· 0 citations