# Bloom filter hashes: more or bigger?

In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as linear combinations thereof.

My question is: what, really, is the difference between two hash functions and one with twice the entropy?

This comes from looking at what you actually do with the output of your hash functions: you're going to take your (say) 64-bit hash value and scale it to the size of your bit vector, which is probably significantly smaller than 264. This is clearly an entropy-losing transformation (except in the rare case your hash size and filter capacity exactly coincide). Assuming my filter has less than 232 entries, what's to stop me from splitting my 64-bit hash value into two 32-bit hashes and taking linear combinations of those? Or using it to seed a PRNG?

In other words, how much information do I actually need to know about each element I insert into a Bloom filter to ensure the standard false positive rate holds? Or more generally, what is the relationship between how well I can distinguish elements (how many bits I use to describe them) and how my Bloom filter performs?

It sure seems like I can get away with $2\lg(m)$ bits for a filter size of $m$, or equivalently $2(\lg(-n\ln{p}) - 2\lg(\ln2))$ bits to store $n$ elements with false positive probability $p$....

For the scheme described above (which should be attributed to Dillinger and Manolios; Kirsch/Mitzenmacher just analyzed it), that means you're correct; if you have a single hash function with $2 \lg(m)$ bits, you should be fine.