A Bloom filter is a space-efficient probabilistic data structure used to test whether an item may be in a set. This cheat sheet helps students understand how Bloom filters trade exactness for speed and memory savings. It is useful for studying databases, networking, caching, cybersecurity, and large-scale systems.
Students need it because Bloom filters appear whenever software must check membership quickly without storing every item directly.
The core idea is to use a bit array and several hash functions to mark positions for each inserted item. To query an item, the same hash functions are used, and the filter checks whether all matching bit positions are 1. A Bloom filter can return false positives, meaning it says an item may be present when it is not.
It never returns false negatives if the filter has not been modified incorrectly.
Key Facts
- A Bloom filter uses a bit array of size m and k independent hash functions to represent a set of n inserted items.
- To insert an item x, compute k hash values h1(x), h2(x), ..., hk(x), and set each matching bit position to 1.
- To query an item x, compute the same k hash positions, and report possibly present only if all those bits are 1.
- A standard Bloom filter has no false negatives, so if any queried bit is 0, the item is definitely not in the set.
- A Bloom filter can have false positives because different items may set overlapping bit positions.
- The approximate false positive probability is p = (1 - e^(-kn/m))^k.
- The optimal number of hash functions is approximately k = (m/n) ln 2.
- For a target false positive rate p and expected item count n, the needed bit array size is approximately m = -(n ln p) / (ln 2)^2.
Vocabulary
- Bloom filter
- A probabilistic data structure that tests set membership using a bit array and multiple hash functions.
- Bit array
- A fixed-size sequence of bits, usually initialized to 0, that stores the marks made by inserted items.
- Hash function
- A function that maps an input item to a predictable array position, ideally spreading values evenly.
- False positive
- A result where the Bloom filter says an item may be present even though it was never inserted.
- False negative
- A result where the filter says an inserted item is absent, which should not happen in a standard Bloom filter.
- Load factor
- A measure of how full the bit array is, often related to the number of inserted items compared with the array size.
Common Mistakes to Avoid
- Assuming a Bloom filter gives exact answers is wrong because a positive result only means the item may be present.
- Forgetting that Bloom filters can have false positives is wrong because overlapping hash positions can make a missing item appear present.
- Using too few bits for many inserted items is wrong because the array fills up and the false positive rate increases quickly.
- Choosing too many hash functions is wrong because it slows insertion and lookup and can also set too many bits to 1.
- Deleting items from a standard Bloom filter by clearing bits is wrong because those bits may also belong to other inserted items.
Practice Questions
- 1 A Bloom filter has m = 1000 bits, n = 100 inserted items, and k = 7 hash functions. Estimate the false positive probability using p = (1 - e^(-kn/m))^k.
- 2 A system expects n = 5000 items and wants a false positive rate of p = 0.01. Estimate the required bit array size using m = -(n ln p) / (ln 2)^2.
- 3 If a query checks k = 4 hash positions and one of the corresponding bits is 0, what should the Bloom filter report and why?
- 4 Explain why a Bloom filter is useful for checking whether a web address is probably in a large blacklist before doing a slower database lookup.