Hacker News Reader

Comment by natch | Hacker News Reader

I can never understand why some bloom filter (or in this case IBLT) implementations insist on using multiple different independent hash functions.

Just append a new salt to each input. For input ‘abc’ hashed say 8 times you simply construct abc-1, abc-2, abc-3, etc. up to abc-8 and hash each one and there you have 8 hash values that are no more prone to collisions than values produced by 8 independent hash functions.

Concerned that abc-n might appear naturally in the input? Fine, append an odd string that’s unlikely to appear in the input if that really is your genuine concern. Or pass the salt in as a second parameter instead.

And if your one hash function is so bad that abc-n is entangled with abc-n’, find a better hash function.

I admit this is not my field so this may be a naive take. What am I missing?

View on HN

As others have explained, whenever you salt a hash function you're creating a new hash function. "Multiple hash functions" doesn't mean completely different definitions of the function, but usually it is just a parametric family.

But there's more to this. This is a theoretical paper, the algorithm has to work for any N. Even if the N is larger than the number of particles in the known universe. That's how theory works, you need guarantees and theorems.

Then it becomes clear that no "practical" hash function can actually work for this, by a simple pigeonhole argument: you have only 64 bits (or 128 bits, ...) of output, so at some point you'll get too many collisions for anything to work.

Then you can start wondering: if I use "salt" (that is, a parameter), how many bits should that salt have, depending on N? How do you guarantee that the parametric family you have always guarantee sufficient independence, and you don't start seeing weird correlations when you start having enough hash functions and running out of entropy?

In practice, these considerations are not made, because we don't even know why the hash functions we use actually work. There is very little theory behind them: their quality is mostly empirically assessed by enormous batteries of statistical tests.

I've only really read the abstract and then skimmed for:

> Each of the arrays has its own hash function h_i

If that's what you're objecting to, isn't it just that your 'append a new salt and then hash' is a hash function h_i where i is the salt and h the 'original'/underlying hash function?

I don't think it means go looking for an array of well-known named hash functions like [md5, sha1, sha224, sha256, ...].

What you did just now is you constructed a family of independent hash functions. It is a terminology thing about those output collisions, and you provided one possible implementation.

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.

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-0... [2] https://stackoverflow.com/questions/70963247/bloom-filters-w...

https://en.wikipedia.org/wiki/Double_hashing is probably the canonical name for this

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

I think the issue is awareness. The “modern” way to do it is to precompute a table of bit patterns, and use the bottom few bits of the hash to lookup the bit patterns and set them in the Bloom filter. I wrote a blog post about it if you’re curious: https://save-buffer.github.io/bloom_filter.html

When I started reading such papers this also confused me.

Yes, it's about randomness and probability of collisions. Adding two characters might be OK or not, it depends on the hash function and the use case. For example, the Java "String.hashCode" method return "abc-1": 92597638, "abc-2": 92597639; the hash code of the "-2" is (almost) always one greater than the "-1" variant. So the two are not independent. Anyway 32-bit hash functions might not be good and you need 64 bit. Then you should use something like MurmurHash.

But you don't need to compute MurmurHash twice. It is probably enough to compute one MurmurHash, and then hash this hash code using an integer hash function [1]: h1=integerHash(hash + 1), h2=integerHash(hash + 2). This is almost twice as fast for string data.

For certain use cases, for example for Bloom filters, you need more hash "functions". For Bloom filters, it is even simpler: you can split a 64-bit hash code into a 32-bit start, and a 32-bit offset. And then use: h(x)=start+x*offset. That means h(3)=h(2)+offset and so on. It is really fast.

https://stackoverflow.com/questions/664014/what-integer-hash...

Along the same lines, what about using the first `n` outputs from a random number generator? (With "it depends on the PRNG" replacing your "it depends on the hash function".)

I come from cheminformatics, where we've used a form of superimposed coding very similar to a Bloom filter. In one incarnation, developed in the 1980s, enumerate all linear structures of up to length 7, determine a unique order based on atom and bond characteristics, convert that into a PRNG seed, and generate (typically) 4 values, each used to set a bit in a bitstring of size ~1024 bits.

I write similar because (1) in some cases the number of bits is not fixed, eg, it may vary depending on the structure, and (2) it uses a PRNG instead of `n` different independent hash functions.

I'm therefore curious if PRNGs have been examined in a Bloom filter context, or for MinHash, which also has `n` different hash functions. Then I can drop (2) from my list of differences.

You aren’t missing anything. I don’t have the paper handy but I had the same question and found a study showing that a salt worked fine.

I’m just glad im not the only one to wonder this. Perhaps that’s the issue. It feels wrong for some reason despite not being an issue in practice.

Independent hash functions can be as mundane as using different a,b values for ax+b, so as far as the theory is concerned, salting is indeed generating a new hash function.

Several others have said it too, but this comment is a perfect summary of what I was missing. Thank you. I do wish the terminology was used in a way that would induce everyone to reach the same understanding.

Thanks, it’s great to have it clarified now!

1. There might be a misunderstanding with terminology. Asking for a k-independent/k-wise independent family of hash function doesn’t mean “k hash functions.” It is a technical term that means: a set H of functions having the property that, if you pick a random function h: X -> Y from that set, hashing any k items with h results in “no correlation” in the output. (Formally, over the randomness of h in H, for all x1, x2, … xk in X; y1, y2, … yk in Y, P[h(x1) = y1 and h(x2) = y2 and … h(xk) = yk] = 1/(|Y|^k).)

(Although, granted, most Bloom filter papers do draw m functions from a k-wise independent family. That brings me to 2…)

2. The target audience is different. CS theory papers often limit their scope to a smaller result. In a bloom filter context, they don’t want to concern themselves with whether a particular hash function like SHA256 behaves k-wise independently when random characters are appended to the input. They only care that a k-wise independent hash family is needed. A different paper can analyze SHA256 or whatever other hash function.

w.r.t the paper when they say they need k-wise independent hash functions, this is a requirement on the family of hash functions used. It’s not the functions that are independent of each other, it’s the values from any particular function that are independent of each other. Just in case this wasn’t already clear.

I don't think you're missing anything. Years ago, I made the same observation, and ran a test to compare independent hash functions vs salting. It showed no difference. I would be interested if someone here has a different opinion and a rationale to explain what I might have missed.

Seems legit. Good hash function digests should be as independent from each other respecting seed, as they are from digests of other hash functions with the same seed.

You are processing more data if you use salts. I would think this is almost certainly slower than just using hard coded hash functions with different constants. But maybe not, or maybe the difference isn't noticeable.

And so we wonder, are there vectorized versions of a hash function where you can compute n hashes with different salts in the same cpu time as you'd normally do one?

Usually you'd just hash several different elements at once in a vectorized way.

You can typically use some/all of the output of round N-1 as an input to round N.

They don't mean that you should use several different hash algorithms.

> Concerned that abc-n might appear naturally in the input?

I'm not, because that would turn in to "abc-n-1", "abc-n-2", etc.

Exactly, it’s a fake concern.

Reply on news.ycombinator.com