4 ms·

Here's a helpful calculator, it will even tell you the optimal number of hash functions. All you have to know is the expected cardinality of the set. https://h

• afonsotsukamoto 9y ago
  ah! ok - I just had a "mind bending" moment after looking at the calculator + tekromancr's response. I thought we would want to control the number of hash functions (k) and the number of items (n) but I guess the most common use case will be to set the allowed probability of a false positive for the number of allowed items and let the "system" control the k and m (hash functions and bits in the filter) Enlightening! One question remains though - since the number of bits (m) is a function of the probability of false positives (p) and the number of hash functions (k) is a function of the number of bits and the number of items (n), does it mean that once we start a bloom filter we can't update the number of items or the desired probability of false positives? My assumption is that if we change p, then m will change, which would make the k functions "obsolete" as they're being "mapped" to a new sized m. Same for n, which would change the k functions, making it so that a new item would be hashed differently, making m hits/misses obsolete again. Might be missing something here though. Either way, I still find bloom filters a fascinating data structure.
  • tekromancr 9y ago
    Nope, I think you got it. My understanding is that if you want to change the params, you need to rebuild the filter.