<p>Apparently not. <a href="http://fr.arxiv.org/abs/1502.05729" rel="nofollow">"Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by  Mathias Bæk Tejs Knudsen and Morten Stöckel</a> shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$".</p>

CC BY-SA 3.0
2015-03-01T17:42:29.313Z
2015-03-01T17:42:29.313Z
jbapple
<p>If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In <a href="http://arxiv.org/abs/1011.5200">"The Power of Simple Tabulation Hashing"</a>, Pătraşcu and Thorup mention that <a href="http://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf">"Chernoff-Hoeffding bounds for applications with limited independence"</a> (<a href="http://www.cs.nyu.edu/faculty/siegel/Limited.ps">mirror</a>) shows that this bound on the population of the heaviest loaded bin also holds if the balls are distributed by an $\Omega(\lg n/\lg \lg n)$-independent hash function.</p>

<p>In <a href="http://www.stanford.edu/~segev/papers/SmallFamilies.pdf">"Balls and Bins: Smaller Hash Families and Faster Evaluation"</a>, Celis et al. note that it is not known if there is a family of hash functions where </p>

<ol>
<li>Hash functions can be represented with $O(\lg n)$ bits of space</li>
<li>Hash functions can be evaluated in $O(1)$ time</li>
<li>The maximal load is $O(\lg n / \lg \lg n)$ with high probability.</li>
</ol>

<p>If there is a constant $k$ such that any $k$-independent family suffices for #3, then it the polynomial construction of $k$-independent families would meet #1 and #2.</p>

<p>What bound <em>do</em> we have for the heaviest loaded bin with $k$-independent hashing? </p>

<p>Using Theorem 4.III of "Chernoff-Hoeffding bounds ..." and the union bound, I think I can get a bound of $O(n^{2/k})$ on the weight of the heaviest loaded bin w.h.p.</p>

<p>Can this be brought down to $O(\lg ^c n)$ using other techniques?</p>

<ds.data-structures><randomness><hash-function><independence>
How much independence is required for separate chaining?
jbapple
# How much independence is required for separate chaining?

(Asked by: username_0 on 2013-03-28)

If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In ["The Power of Simple Tabulation Hashing"](http://arxiv.org/abs/1011.5200), Pătraşcu and Thorup mention that ["Chernoff-Hoeffding bounds for applications with limited independence"](http://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf) ([mirror](http://www.cs.nyu.edu/faculty/siegel/Limited.ps)) shows that this bound on the population of the heaviest loaded bin also holds if the balls are distributed by an $\Omega(\lg n/\lg \lg n)$-independent hash function.

In ["Balls and Bins: Smaller Hash Families and Faster Evaluation"](http://www.stanford.edu/~segev/papers/SmallFamilies.pdf), Celis et al. note that it is not known if there is a family of hash functions where

1. Hash functions can be represented with $O(\lg n)$ bits of space
2. Hash functions can be evaluated in $O(1)$ time
3. The maximal load is $O(\lg n / \lg \lg n)$ with high probability.

If there is a constant $k$ such that any $k$-independent family suffices for #3, then it the polynomial construction of $k$-independent families would meet #1 and #2.

What bound *do* we have for the heaviest loaded bin with $k$-independent hashing?

Using Theorem 4.III of "Chernoff-Hoeffding bounds ..." and the union bound, I think I can get a bound of $O(n^{2/k})$ on the weight of the heaviest loaded bin w.h.p.

Can this be brought down to $O(\lg ^c n)$ using other techniques?

**Tags:** ds.data-structures, randomness, hash-function, independence

---

## 1 answers

### Answer by username_0 on 2015-03-01. Score: 3 | Accepted answer

Apparently not. ["Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by Mathias Bæk Tejs Knudsen and Morten Stöckel](http://fr.arxiv.org/abs/1502.05729) shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$".


---

