FastFilter

A C# library of high-performance approximate membership filters. Test whether a key may belong to a set without storing the original keys.

Supports the following algorithms:

Authors refer to the linked papers. Licenses refer to the filter implementations used here, including their underlying adapted code; implementation credits and modifications are recorded in third-party notices. ZOR is an independent MIT implementation of the published algorithm.

All filters accept a required Func<T, ulong> hash. Construction seeds are managed internally.

Other features:

• Configurable bits per key for Bloom and Blocked Bloom filters.
• Construction from ReadOnlySpan<T> for all filters.

Build a Binary Fuse filter from a fixed set of keys:

using System;
using Genbox.FastFilter;

int[] data = [1, 42, 30, 481, 58];
BinaryFuse8Filter<int> filter = new BinaryFuse8Filter<int>(data, key => unchecked((ulong)key.GetHashCode()));

Console.WriteLine("Does it contain 42? " + (filter.Contains(42) ? "Maybe" : "No"));
Console.WriteLine("Does it contain 50? " + (filter.Contains(50) ? "Maybe" : "No"));

Example output:

Does it contain 42? Maybe
Does it contain 50? No

42 always matches because it was included during construction. 50 can also return Maybe due to a false positive.

For a set that grows, create a Bloom filter sized for the expected number of keys:

using Genbox.FastFilter;

BloomFilter<int> filter = new BloomFilter<int>(capacity: 100_000, hash: key => unchecked((ulong)key.GetHashCode()), bitsPerKey: 10);
filter.Add(42);
bool maybePresent = filter.Contains(42); // true

Contains() returns false when a key is definitely absent, or true when it may be present. An inserted key always returns true, provided its hash remains unchanged. An absent key can return true: this is a false positive.

Use a filter to skip expensive lookups, such as disk or database reads, for keys that are definitely absent. Check positive results against the original data when you need an exact answer.

Bloom and Blocked Bloom support Add() after construction. Their capacity determines the allocated storage; adding more keys than planned increases the false-positive rate.

The other filters are immutable. Supply all keys during construction and rebuild the filter when the set changes. These filters implement ImmutableFilter<T> and do not expose Add(). None of the filters supports removing individual keys.

For Bloom and Blocked Bloom, increasing bitsPerKey uses more memory to reduce false positives. Binary Fuse offers 8-bit and 16-bit fingerprints, with nominal false-positive probabilities of approximately 0.39% and 0.0015%, respectively, assuming well-distributed hashes.

The research filters use 8-bit fingerprints, with a nominal false-positive probability of approximately 0.39%. Complete ZOR also checks a 16-bit remainder when present, giving approximately 1/256 + 1/65536. Actual rates depend on hashing and workload.

GetMemoryUsage() estimates retained filter storage in bytes. It is not a measurement of total managed heap usage or peak construction memory. See the static filter guide for the research filters' accounting details.

All filters use the supplied Func<T, ulong> delegate. It must produce well-distributed 64-bit signatures and remain stable for the filter's lifetime. Keys with the same signature are indistinguishable. Casting GetHashCode() to ulong does not remove its 32-bit collision limit.

If the hash function needs a seed, capture that seed in the delegate and keep it unchanged. Filters manage layout seeds and construction retries internally using a deterministic sequence. The same signatures, input order, and options reproduce the same layout within the same implementation version. Immutable filters hash the input once and reuse its distinct signatures during construction retries.

Memory is the filter's GetMemoryUsage() estimate. The efficiency ratio compares the actual bits per entry with the theoretical minimum needed for the observed false-positive rate:

Bits per entry = estimated memory in bytes * 8 / number of inserted keys
Efficiency ratio = bits per entry / log2(1 / p)
Space overhead (%) = (efficiency ratio - 1) * 100

Here, p is the false-positive rate expressed as a fraction, so 0.39% becomes 0.0039. For example, a rate of 1/256 (approximately 0.3906%) requires a theoretical minimum of 8 bits per entry. A filter using 9 bits per entry has a ratio of 9 / 8 = 1.125, or 12.5% space overhead above that minimum.

For example, the Burr8Filter ratio of 1.0349 in the table means approximately 3.49% extra space above the minimum for its observed false-positive rate. It does not mean 3.49% false positives.

A ratio of 1.0 corresponds to the theoretical minimum, 1.1 means 10% extra space, and 2.0 means twice the minimum space. Lower is better for space efficiency. The ratio does not measure lookup or construction speed. Because the example uses estimated memory and a sampled false-positive rate, its reported ratios are approximate and vary between runs.

FastFilter combines MIT-licensed original code with Apache-2.0 and MIT third-party adaptations. The package license expression is MIT AND Apache-2.0. See third-party notices for component attribution and LICENSES for the bundled upstream license texts.