Bloom filter
lastmod 2025-12-17created 2024-12-263 edits
A Bloom filter is a probabilistic data structure used to test whether an element is a member of a set. It was conceived by Burton Howard Bloom in 1970. When a Bloom filter judges that an element belongs to a set, a false positive (the element is actually not in the set) is possible; conversely, a false negative (the element is judged not to be in the set but actually is) never occurs. Elements can be added to the set, but cannot be removed from it. As the number of elements in the set increases, the probability of false positives also increases.