<p>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.  </p>

<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.</p>

CC BY-SA 3.0
2012-04-14T17:45:10.143Z
Welcome to cstheory, Michael :)
Suresh Venkat
CC BY-SA 3.0
2012-04-14T17:28:52.270Z
2012-11-27T21:21:48.300Z
2012-11-27T21:21:48.300Z
Michael Mtizenmacher
<p>In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions.  <a href="http://www.eecs.harvard.edu/~michaelm/postscripts/esa2006a.pdf">Kirsch and Mitzenmacher</a> showed that you actually only need two, and can generate the rest as linear combinations thereof.</p>

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

<p>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<sup>64</sup>.  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<sup>32</sup> 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?</p>

<p>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?</p>

<p>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$....</p>

<ds.data-structures><it.information-theory><hash-function>
Bloom filter hashes: more or bigger?
Jay Hacker
# Bloom filter hashes: more or bigger?

(Asked by: username_0 on 2012-04-13)

In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. [Kirsch and Mitzenmacher](http://www.eecs.harvard.edu/~michaelm/postscripts/esa2006a.pdf) 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$....

**Tags:** ds.data-structures, it.information-theory, hash-function


---

## 1 answers

### Answer by username_1 on 2012-04-14. Score: 16 | Accepted answer

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.

> **Comments:**
> **username_2**: Welcome to cstheory, Michael :)  

---

