A Bloom filter for 100 million keys with a 1% false-positive rate needs about 9.6 bits per key. How much memory is that?

Answer

About 120 MB. In review, anything from 80 to 180 counts as right.

The worked estimate

100,000,000 × 9.6 bits = 960,000,000 bits. ÷ 8 = 120,000,000 bytes ≈ 120 MB. Storing the keys themselves (say 20 bytes each) would take 2 GB. Each tenfold drop in the false-positive rate costs about 4.8 more bits per key.

Numbers: Numbers to know.

Review this in your daily deck → All cards in Data structures