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

<p><a href="https://arxiv.org/pdf/1706.02783.pdf" rel="nofollow noreferrer">Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"</a></p>

CC BY-SA 3.0
2018-01-27T15:09:40.133Z
That's a pretty amazing result!
Simd
CC BY-SA 3.0
2018-01-26T19:23:44.427Z
2018-01-26T19:34:13.883Z
2018-01-26T19:34:13.883Z
SamM
<p>This is an extension to the question about balls into bins: <a href="https://cstheory.stackexchange.com/questions/31090/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn">Example of pairwise independent random process with expected max load $\sqrt{n}$</a> .  There the following question is asked and answered in the affirmative:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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>

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

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

<pr.probability><nt.number-theory><hash-function>
Does this pairwise independent random process have expected max load $\sqrt{n}$?
Simd
# Does this pairwise independent random process have expected max load $\sqrt{n}$?

(Asked by: username_0 on 2018-01-26)

This is an extension to the question about balls into bins: [Example of pairwise independent random process with expected max load $\sqrt{n}$](https://cstheory.stackexchange.com/questions/31090/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn) . 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?

**Tags:** pr.probability, nt.number-theory, hash-function


---

## 1 answers

### Answer by username_1 on 2018-01-26. Score: 2 | Accepted answer

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"](https://arxiv.org/pdf/1706.02783.pdf)

> **Comments:**
> **username_0**: That's a pretty amazing result!  

---

