Bloom Filter: Introduction, Theory, Construction, Query, and Applications

When a user registers a WeChat account, the system must quickly determine whether the entered phone number has already been registered while using minimal storage. Traditional solutions such as linear scanning (O(n) time and space), hash maps (O(1) time but high memory), or bitmaps (O(max_value) space) become impractical when the dataset reaches billions of entries.

The article introduces the Bloom filter, a probabilistic data structure proposed by Burton H. Bloom in 1970, which combines a long binary vector with multiple independent hash functions. Its goal is to answer the membership query "is element x in set S?" using far less memory than exact structures, at the cost of a controllable false‑positive rate.

1. Construction

The construction process consists of three steps:

Choose k independent hash functions.

Hash each element to k positions in the bit array.

Set the bits at those positions to 1 .

An illustrative example uses three hash functions and two strings "jimboooo" and "luckyyyyy". After hashing, the bits at positions (1,4,8) and (2,4,7) are set to 1 , respectively, resulting in the final bit array shown in the accompanying diagram.

2. Query

To test whether a string is in the set, the same k hash functions are applied and the corresponding bits are checked. If all bits are 1 , the element is considered present; otherwise it is definitely absent. The article demonstrates this with a diagram where the query for "jimbooo" succeeds while the query for "fukuoka" fails.

3. Effectiveness and False‑Positive Rate

The false‑positive probability p depends on the filter length m , the number of inserted elements n , and the number of hash functions k . The optimal values are derived as:

k = (m/n) * ln2

and the minimal false‑positive rate:

p = (0.6185)^{m/n}

Graphs in the article show that with an optimal k and a false‑positive rate of 1%, each element requires only about 9.6 bits. Adding roughly 4.8 bits per element reduces the false‑positive rate by an order of magnitude.

4. Applications

Bloom filters are widely used in scenarios where fast membership tests and low memory consumption are critical, such as:

Web crawler URL deduplication.

Cache breakdown protection (preventing cache and DB overload).

HTTP caching servers to avoid unnecessary upstream requests.

Black/white list implementations for spam filtering.

5. Conclusion

Bloom filters provide a space‑efficient solution for set membership queries with no false negatives and a tunable false‑positive rate. They are especially valuable in big‑data and caching contexts where storage and latency constraints dominate.

References

Several external resources are listed for deeper study, including tutorials on Bloom filter theory, hash function design, and practical implementations in Chromium, Python, Plan9, and Squid.