On Mon, Apr 19, 2010 at 3:17 PM, Benson Margulies <bimargul...@gmail.com>wrote:
> That doesn't bother my intuition so much, since the two hashes are > *different*. Or maybe I'm not following the implications of the linear > conbination. > Yes, but h_1 + h_2 and h_1 + 2 h_2 are pretty similar. That was the surprise. The win comes from the fact that the linear combo is way faster than hashing from scratch. > > It's the conceptual model I'd like to understand here. In my > 'understanding', bloom filters work because each hash function grabs a > different picture of the total information content of the original key. > A good hash does this if you have different seeds. > > Generally, I am indeed feeling like a bear of rapidly shrinking brain, > since > that page is at pains to insist on two independent has functions. > For a good hash function, different seeds give you essentially independent hashes. Otherwise, it would be easy to recover the seed given the two hashes which contracts "goodness" of a hash.
