2 ms·

I don't know the answer, so I'm purely speculating for the fun of it. I guess that hash function outputs aren't perfectly uniformly distributed. E.g. if a toy

I don't know the answer, so I'm purely speculating for the fun of it. I guess that hash function outputs aren't perfectly uniformly distributed. E.g. if a toy hash function (a) produces a 2-bit output for a gajillion random inputs, you wouldn't get a quarter of the values in each bucket. Maybe you'd get 30% in 00, 20% in 01, and 25% in both buckets 10 and 11. Salting the inputs wouldn't help with that. It'd only make similar inputs less likely to collide, but collisions would still be more likely in the worst case. By combining different a hash function (b) with different "lumps", I suppose that the lumps would even out so that you'd approach a probability of .25 in each bucket. 00 01 10 11 a .30 .20 .25 .25 b .22 .22 .25 .31 a+b .26 .21 .25 .28 Therefore, if you're going to spend time hashing something more than once, you might as well use different hash functions for each cycle.

tadkar 3y ago
I suspect that for most Bloom filters, the most commonly used hash functions are “good enough”. There’s also some literature to suggest that using just 2 hash functions and recombining the results is plenty. See kirsch-mitzenmacher [1] and [2] [1] https://www.eecs.harvard.edu/%7Emichaelm/postscripts/tr-02-05.pdf https://www.eecs.harvard.edu/%7Emichaelm/postscripts/tr-02-0... [2] https://stackoverflow.com/questions/70963247/bloom-filters-with-the-kirsch-mitzenmacher-optimization https://stackoverflow.com/questions/70963247/bloom-filters-w...
- giveexamples 3y ago
  https://en.wikipedia.org/wiki/Double_hashing https://en.wikipedia.org/wiki/Double_hashing is probably the canonical name for this
- morelisp 3y ago
  Depending on the function you may even be able to use "two for one" hashing, splitting e.g. a single 64 bit hash into two different 32 bit ones and combine those. https://arxiv.org/abs/2008.08654 https://arxiv.org/abs/2008.08654

tadkar 3y ago

I suspect that for most Bloom filters, the most commonly used hash functions are “good enough”. There’s also some literature to suggest that using just 2 hash functions and recombining the results is plenty. See kirsch-mitzenmacher [1] and [2] [1] https://www.eecs.harvard.edu/%7Emichaelm/postscripts/tr-02-05.pdf https://www.eecs.harvard.edu/%7Emichaelm/postscripts/tr-02-0... [2] https://stackoverflow.com/questions/70963247/bloom-filters-with-the-kirsch-mitzenmacher-optimization https://stackoverflow.com/questions/70963247/bloom-filters-w...

giveexamples 3y ago
https://en.wikipedia.org/wiki/Double_hashing https://en.wikipedia.org/wiki/Double_hashing is probably the canonical name for this
morelisp 3y ago
Depending on the function you may even be able to use "two for one" hashing, splitting e.g. a single 64 bit hash into two different 32 bit ones and combine those. https://arxiv.org/abs/2008.08654 https://arxiv.org/abs/2008.08654