Remix.run Logo
jstanley 7 hours ago

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