Re:Bloom Filters by Example
by asdfaoeu on Tuesday July 11, 2017 @03:01AM
(#14742125)
The only problem is this assumes that the hash unpredictably changes on input modification. Which is true for cryptographic hashes but not others.
[ Parent
| on HN ]
It assumes nothing of the sort. [Edit: well I mean it RELIES on it yes but it's not an assumption; it's verified by knowing the properties of the hash function used.] But it perhaps hinges on your definition of "unpredictably."
If you're taking the modulus of a large integer with respect to a very much smaller bit array with a length that is a prime number, there is plenty of unpredictability with most decent hash functions (note I did have "good quality" as a caveat above) even non-cryptographic ones. That being said, I do use cryptographic hashes.
basically, ideally you would want all of your hash functions to belong to the same universal hash family[1].