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", Pătraşcu and Thorup mention that "Chernoff-Hoeffding bounds for applications with limited independence" (mirror) 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", 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?


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

| cite | improve this answer | |

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.