Bloom Filter

For a candidate set of n elements, bloom filter creates an array of size of m, and use k hash function:

Steps

1. for each element in n elements: Hash them and use the result as index to set the corresponding bit to 1
2. Given the test element, do the same hash and check if all the result bits are 1. If not false; otherwise, true

Probability

Check Probability of false positives wiki The key idea is:

1. Calculate the probability of a certain bit in the array is 1 after n candidates insertion.
2. Calculate the k power of the above probability