A Bloom filter consists of:

1. An array of n bits, initially all 0’s.

2. A collection of hash functions h1, h2, . . . , hk. Each hash function maps “key” values to n buckets, corresponding to the n bits of the bit-array.

3. A set S of m key values.

The purpose of the Bloom filter is to allow through all stream elements whose keys are in S, while rejecting most of the stream elements whose keys are not in S.

The model to use is throwing darts at targets. Suppose we have x targets and y darts. Any dart is equally likely to hit any target. After throwing the darts, how many targets can we expect to be hit at least once?

• The probability that a given dart will not hit a given target is (x − 1)/x.

• The probability that none of the y darts will hit a given target is ((x−1)/x)^y.

• We can write this expression as (1 – 1 x )^x( y x ).

• Using the approximation (1−ǫ)1/ǫ = 1/e for small E we conclude that the probability that none of the y darts hit a given target is e−y/x.