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?
