3 ms·
Surely the original 'false positive rate' is only wrong if the hash function is 'bad', and thus Bloom wasn't 'incorrect' as much as assuming a perfect hash func
by NikkiA 6y ago
Surely the original 'false positive rate' is only wrong if the hash function is 'bad', and thus Bloom wasn't 'incorrect' as much as assuming a perfect hash function.
- gopiandcode 6y agoI don't think that would solve this issue - a perfect hash function is guaranteed to not have any collisions for any element in some predefined set. What Bloom's proof requires is that all of the k hash functions should not have any collision for any input that is inserted into the Bloom filter, which is not covered by just having each function alone be perfect. That aside, Bloom does not make any assumptions about the chosen hash functions being perfect or not.
- jesboat 6y agoCorrect. In the extreme case, imagine that your k hash functions are nearly identical: hash function `H_i` differs from `H_1` only in that the outputs for the `1`st and `i`th elements in the input space are swapped. Of the `N` elements in the input space, all but `k` will completely collide.
- Dylan16807 6y agoAssuming a perfect hash function (or similar) out of nowhere is a crazy thing to do, and solidly incorrect in my book. If you could assume a perfect hash function, you could treat 64 or 80 bits as secure in a wide swath of inappropriate contexts.
- a1369209993 6y ago> you could treat 64 or 80 bits as secure You're confusing statistically uniform with cryptanalytically secure. By that logic you can 'debunk' plain old hash tables because someone might feed you keys that all hash to the same slot.
- Dylan16807 6y agoWhat's wrong with saying that? It's a real vulnerability if you don't have a secret seed.