A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.

The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set.

The base data structure of a Bloom filter is a Bit Vector.

Bloom filter 是一個數(shù)據(jù)結(jié)構(gòu)，可以快速查詢一個元素是否在一個集合中。

它是概率性的數(shù)據(jù)結(jié)構(gòu)，每次的結(jié)果會告訴，這個元素一定不再集合中，或者可能在集合中。
實(shí)現(xiàn)它的方法就是用一個bit vector

使用幾個hash方程來hash存入的元素，并且將這些hash值再bit vector里面標(biāo)記。

Bloom Filter 參數(shù)

Bloom filter with k hashes, m bits in the filter, and n elements that have been inserted.

Bloom Filter 時間，空間

Given a Bloom filter with m bits and k hashing functions, both insertion and membership testing are O(k). That is, each time you want to add an element to the set or check set membership, you just need to run the element through the k hash functions and add it to the set or check those bits.

Reference:
https://llimllib.github.io/bloomfilter-tutorial/
https://en.wikipedia.org/wiki/Bloom_filter
https://blog.medium.com/what-are-bloom-filters-1ec2a50c68ff