Power of $d$ Choices with Simple Tabulation

Anders Aamand, Mathias Bæk Tejs Knudsen, Mikkel Thorup

Suppose that we are to place $m$ balls into $n$ bins sequentially using the $d$-choice paradigm: For each ball we are given a choice of $d$ bins, according to $d$ hash functions $h…