Balanced allocation-Hash table- overflow probability
A more formal statement of the claim is as follows. There is a constant $C &gt; 0$ and for each $k$, a function $\epsilon(n)$ satisfying $\lim_{n\to\infty} \epsilon(n) = 0$, such that if you throw $n$ balls into $k$ bins, then with probability at least $1-\epsilon(n)$ the contents of each bin is at most $ \frac{n}{k} + C(\sqrt{(\frac{n}{k})\log k}+\log k)$.