Balls and Bins- Hash Table: a Concrete Example

714 Views Asked by At

My question is related to this:

https://cs.stackexchange.com/questions/49027/balanced-allocation-hash-table-overflow-probability/49030#49030


In [1,2], it is said that if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$ elements with a high probability.

Question: If we set $n=10^4$ and $k=10$, what the maximum load of a bin would be and with what probability. To be more clear, I want to ensure that with a high (or overwhelming) probability a bin has specific max-load.

Thus, I need to know how to compute maximum load of a bin given number of bins and balls.


[1]. http://www.pinkas.net/PAPERS/FNP04.pdf

[2]. http://www14.in.tum.de/personen/raab/publ/balls.pdf