Bloom filter hashes: more or bigger?

Question

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 2⁶⁴. 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 2³² 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$....

Answer 1

You're right to think of hash functions in terms of "random bits produced". So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on.

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.