This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in the affirmative:

Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the expected max load to be $\Theta(\sqrt{n})$ asymptotically?

Imagine we choose the explicit pairwise independent hash function family $h((ax+b) \bmod p) \bmod n)$. It is a straightforward standard exercise to show an upper bound of the following form:

$$P(\text{max number of values hashed to the same value} \geq 1 + \sqrt{2n}) \leq \frac{1}{2}$$

However, can a matching or near matching lower bound be found for the expected max load for this specific hash function family?


The hash family you give has expected max load $\tilde{O}(n^{1/3})$, as shown in this recent paper:

Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"

| cite | improve this answer | |
  • $\begingroup$ That's a pretty amazing result! $\endgroup$ – Lembik Jan 27 '18 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.