[Autodesk] Play With Bloom Filter
What Is a Bloom Filter? A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. When an element is added, it is hashed by K independent hash functions, each mapping the element to a position in a bit array, which is then set to 1. To query membership, the same K positions are checked: If any bit is 0 → the element is definitely not in the set. If all bits are 1 → the element is probably in the set (false positives are possible). The key difference from a single-hash bitmap: using K hash functions spreads the load and significantly reduces collision probability. ...