1
$\begingroup$

I show from Wikipedia that the optimal number of hash functions is:

$k =\frac{m}{n}\ln{2}$.

However it's not obvious for me why, even after reading the Wikipedia article (such as the one on false positives). Anyone interested in explaining with simple words? :)

$\endgroup$
3
$\begingroup$

This is explained in Wikipedia. Given $n,m$, the false positive probability is $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ This is the quantity we want to minimize. While the exact expression is hard to minimize exactly, we can use the approximation $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx (1-e^{-kn/m})^k, $$ which is good if $m$ is large. We can optimize the latter expression using calculus, and the result is some expression which is very close to $(m/n) \ln 2$. This is a calculation that I leave to you.

$\endgroup$

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.