In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?

Question

Multiple resources, such as Wikipedia, state that if you have an $m$-bit Bloom filter with $n$ elements inserted, then the optimal number $k$ of hash functions to use is

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

This is very counterintuitive. If $m$ is the number of bits in the filter, then as you increase $m$, why would the optimal number of hashes have to increase to reduce the rate of false positives?

Intuitively, as you increase $m$, the number of collisions goes down. So, as $m \to \infty$, using only one hash function would yield a 0% false positive rate. But this equation would say that as $m \to \infty$, you would need $k \to \infty$ as well. Why?

Is there some way to understand this?

Answer 1

This balances two considerations:

• The more hash functions you have, the more bits will be set in the Bloom filter when you create the filter (because each element you insert causes up to $k$ bits to be set in the filter). The more bits that are set, the higher the risk of false positives.

• The more hash functions you have, the less likely that one of them triggers a false positive (because a false positive will be triggered only if all of the bit positions you inspect are set, and the number of bit positions you inspect is equal to the number of hash functions).

So, increasing the number of hash functions ($k$) has two effects, one of which increases the likelihood of false positives, and the other of which decreases the likelihood of false positives. To figure out how to balance those two, you need to work through the math.

I suspect your intuition was missing the second factor, and once you take that into account the result will feel less absurd.

---

I agree that if you hold $k,n$ fixed and increase $m$, then the false positive probability will decrease. But it would decrease even more if you held $n$ fixed and increased both $m$ and $k$ (due to the way the math works out, and due to the second consideration above).