Introduction

Meziantou.Framework.BloomFilters provides Bloom filters: data structures that answer "is this value in the set?" using a small, fixed amount of memory, whatever the size of the values.

The answer is either "no" or "maybe":

• No false negatives. When MayContain returns false, the value was never added.
• Some false positives. When MayContain returns true, the value was probably added, but it may not have been. You choose the probability of this error when you size the filter.

A Bloom filter does not store the values, so it cannot list them. Use it in front of an expensive lookup, to skip the lookup for most of the values that are not there: a database query for a user name, a disk read for a key, a download of a URL already seen.

What you can do with it

• Add values and test them with BloomFilter. See Getting started.
• Size a filter for a number of values and a false positive probability, or set its size yourself. See Sizing a filter.
• Add values of several types, many at once or from several threads. See Adding values.
• Remove values and count them with CountingBloomFilter. See Counting Bloom filters.
• Choose the hash algorithm. See Hash algorithms.
• Merge filters built separately into one. See Combining filters.
• Speed up large filters with BlockedBloomFilter, which keeps the bits of each value in one cache line. See Blocked Bloom filters.
• Save a filter and load it after a restart or in another process. See Saving and loading filters.

Namespace

The types are in the Meziantou.Framework.BloomFilters namespace:

Next steps

• Getting started: install the package and create your first filter.
• Sizing a filter: choose the number of values and the false positive probability.