# Bloom Filters Explained  ## Metadata - Author: [[System Design]] - Full Title: Bloom Filters Explained - Category: #articles - Summary: A Bloom filter is a space-efficient data structure that tests if an item is part of a set, but it can give false positives. It uses a bit array and multiple hash functions to add items and check membership without storing the actual data. Bloom filters are useful in various applications, like reducing database lookups and improving performance in high-ingestion systems. - URL: https://systemdesign.one/bloom-filters-explained/ ## Highlights - Data structures such as HashSet can be used in a small data set to test if an item is a member of the data set. However, the operation to test if an item is a member of a large dataset can be expensive. The time complexity and space complexity can be linear in the worst case. ([View Highlight](https://read.readwise.io/read/01jr3b7mrjv39x67j9penj6twk)) - Probabilistic data structures offer constant time complexity and constant space complexity at the expense of providing an answer that is non-deterministic. ([View Highlight](https://read.readwise.io/read/01jr3b7ss5mc34mn2vxb0xx78t)) - a small amount of memory to test membership ([View Highlight](https://read.readwise.io/read/01jr3f2aw15q6qtp3z5w2x23e7)) - The bloom filter discards the value of the items but stores only a set of bits identified by the execution of hash functions on the item. ([View Highlight](https://read.readwise.io/read/01jr3f2vpd8j1mn5ty1pxgjf9z)) - the item is hashed through *k* hash functions ([View Highlight](https://read.readwise.io/read/01jr3f30yg8xtszwgrfdqpfhpb)) - If any of the identified bits are set to zero, the item is not a member of the bloom filter. If all the bits are set to one, the item **might** be a member of the bloom filter. ([View Highlight](https://read.readwise.io/read/01jr3hj54jqpgm19ed7r3qahyc)) - [](https://systemdesign.one/bloom-filters-explained/false-positive-bloom-filter.webp) Figure 5: Bloom filter yielding a false positive In Figure 5, the bloom filter is queried to check the membership of item *green*, which is not a member of the bloom filter. • h1(*green*) mod 10 = 3 • h2(*green*) mod 10 = 4 • h3(*green*) mod 10 = 5 The bloom filter will say yes although the item *green* is not a member of the bloom filter as the bits were set to one by items *blue* and *red*. ([View Highlight](https://read.readwise.io/read/01jr3hjmw99x18nn4kgjrbwcmt))