4 ms·

You are correct. The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what th

You are correct. The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what the ideal size is, it depends on the desired probability of false positives, but an optimally large filter for the data you are using will have some empty bits.

bane 9y ago
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://hur.st/bloomfilter https://hur.st/bloomfilter
- 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.

bane 9y ago

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://hur.st/bloomfilter https://hur.st/bloomfilter

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.