Membership Testing False Positive Rate: Bloom Filter

Each Bloom filter is of size 4096 bits (i.e., its array has a width of 4096 slots). We vary the number of hash functions used in each Bloom filter, to see how the false positive rate depends on the number of hashes.

As expected, more hashes are better when the cardinality is small, but they saturate the Bloom filter more quickly, so their advantage soon dies off. Here's a zoomed in graph:

Let's also plot the expected false positive rate as a black line on top of the simulated one. As expected, there is little difference.