Remix.run Logo
inigyou a day ago

What's your basis for claiming either of these two things?

Someone 11 hours ago | parent [-]

Logic.

“It would be more effective in avoiding false positives”: consider a single hash function. To get a false positive, a necessary (but not sufficient) condition is that the bit position that it computes is set.

If you use multiple hash functions with a single table, that happens if any of the hash functions produced the same bit position for a different key.

If you use a single hash function for a bit set, your only chance for that to happen is that that same hash function produced the same bit position for a different key. That probability is lower.

“but require more (typically a lot more) space”: if you give each of your k hash function a separate bit-table, memory usage grows by a factor of k.

jstanley 7 hours ago | parent [-]

> giving each hash function it’s own bit table is equivalent to having one bit table with a number of bits equal to that of the sum of the numbers of bits in each hash function.

This is incorrect, although I also initially had the same incorrect intuition, see my (downvoted) comment in the same thread.

By way of illustration: imagine the limit case where you have the same number of bits as hash functions, so there's only 1 bit per hash function. If you have a separate table for each hash function then every input hashes to the same thing so all inputs are indistinguishable.

But if you put all hash functions in the same table that has a number of bits equal to the number of hash functions, then each hash function only sets 1 bit chosen at random based on the input, instead of always setting the same one.