Hashing upper bound? I am hashing $n^2$ objects into $n$ slots and all slots have equal probabilities of taking in the values, and I am trying to find an upper bound on the expected maximum number of objects in any slot. If we let $X$ be the number of objects in some slot, then $E(X) = \frac{n^2}{n} = n$. Could someone give me hints/help as to how to solve this question? 
 A: This is not a full answer but a potential start.
For $n=1$ its clear the $E(X)=1$
For $n=2$ consider all possible permutations of $4$ objects in the $2$ slots - 
$$((1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 2, 2), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 2, 2), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 2, 2), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 1), (2, 2, 2, 2))$$
This gives the following probability distributions:
$Pr(X=2)=6$, $Pr(X=3)=8$, $Pr(X=4)=2$ and hence $E(X)=\frac{11}{4}$.
For $n=3$ a similar analysis gives $E(X)=\frac{1467}{256}$.
For $n=4$ it gives $E(X)=\frac{39203}{4096}$.
Higher cases tax my ability to quickly code it efficiently so I haven't yet examined them but I highly suspect a pattern should emerge.
A: Assume that one drops randomly uniformly $nm$ objects into $n$ slots and that $n\to\infty$, $m\to\infty$. For every $1\leqslant k\leqslant n$, the distribution of the number of objects $X_k^{(n)}$ in the slot $k$ is binomial $(nm,1/n)$, thus $X_k^{(n)}=m+\sqrt{m}Z_k^{(n)}$ where $Z_k^{(n)}$ converges in distribution to some standard normal random variable $Z_k$. Considering $Z^*_n=\max\{Z_k^{(n)}\mid 1\leqslant k\leqslant n\}$, one sees that $X^*_n=\max\{X_k^{(n)}\mid 1\leqslant k\leqslant n\}$ is $X^*_n=m+\sqrt{m}Z^*_n$.
If one can interchange a maximum and a limit in distribution, then $Z^*_n\approx\max\{Z_k\mid 1\leqslant k\leqslant n\}$ conditioned on $Z_1+\cdots+Z_{n}=0$, for some i.i.d. standard normal random variables $(Z_1,\ldots,Z_n)$. Let $M_n=\frac1n(Z_1+\cdots+Z_{n})$. This would yield $E(X^*_n)\approx m+\sqrt{m}E(Z^*_n\mid M_{n}=0)$.
The distribution of $(Z_k)_{1\leqslant k\leqslant n}$ conditionally on $M_n=0$ coincides with the distribution of $(Z_k-M_n)_{1\leqslant k\leqslant n}$ hence $E(Z^*_n\mid M_{n}=0)=E(Z^*_n-M_n)=E(Z_n^*)$. Now, $E(Z^*_n)=\Theta(\sqrt{\log n})$, hence all this would yield $E(X^*_n)=\Theta(m+\sqrt{m\log n})$, in particular, for $m=n$, $E(X^*_n)=\Theta(n)$.
