Bounded Linear Probing

We introduce a new hash table based on linear probing, but with a bounded number of probes during insertion/lookup This can be viewed as a generalization of classical linear probing, recovered in the limit as the probe bound tends to infinity.

In this talk, we first motivate this design by the need to fully utilize the available memory in parallel collision search and long message attack. Next, we provide a brief introduction to analytic combinatorics, sufficient to follow the remainder of the talk. Finally, we demonstrate how tools from this field enable the analysis of the new hash table.