First, a brief description of what Bloom filters are. They’re a
data structure that relies on hash functions for representing a
set. The actual structure is a bunch of bits and a few hash
functions. To add an element to a Bloom filter, compute the
hashes for each hash function, and set each bit high. To test if
an element has been added to the Bloom filter, compute the
hashes and return true if all the bits are already high. A quick
overview of what this means: - You don’t store any elements in
the Bloom filter—just the elements’ hashes. Very compact. -
Lookup and adding to the set are extremely fast. - Union and
intersection of Bloom filter sets are just bitwise operators. -
False positives are possible. (Since we don’t store the actual
elements, we might see all the hashed bits as high when it was
actually one or more previously added elements that made them
high.) - There’s no way to remove an element from the set. (We
don’t know if another element has hashed to the bits we want to
set low.) Without furthe