Table of Contents

BloomFilter<T> Class

Definition

Namespace
Bodu.Collections.Probabilistic
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
BloomFilter{T}.cs

Represents a space-efficient probabilistic set that tests whether an element might be a member. Membership queries can produce false positives but never false negatives: an element that was added is always reported as present, while an element that was never added is occasionally misreported as present.

public sealed class BloomFilter<T> where T : notnull

Type Parameters

T

The type of elements tracked by the filter. Must not be null.

Inheritance
BloomFilter<T>
Inherited Members
Extension Methods

Examples

// Track ~10,000 visitor ids with a 1% false-positive budget.
var seen = new BloomFilter<int>(expectedItems: 10_000, falsePositiveRate: 0.01);

seen.Add(42);

Console.WriteLine(seen.MightContain(42));   // True  - added items are always found
Console.WriteLine(seen.MightContain(4711)); // False (usually) - may rarely be a false positive

Remarks

The filter is sized from the constructor arguments using the standard Bloom formulas: the bit count is m = ⌈−n·ln(p) / ln(2)²⌉ and the hash count is k = max(1, round(m/n·ln 2)), where n is ExpectedItems and p is DesignFalsePositiveRate. Once more than n elements have been added the observed false-positive rate rises above p; EstimatedFalsePositiveRate reports the rate implied by the current fill.

Elements are hashed via the supplied IEqualityComparer<T> (or Default): the comparer's 32-bit GetHashCode(T) is expanded through a deterministic SplitMix64-style avalanche into two 64-bit values combined by Kirsch-Mitzenmacher double hashing. All entropy therefore derives from the 32-bit comparer hash - standard practice for comparer-based sketches - which bounds the achievable false-positive floor by the collision rate of that hash.

The expansion is platform-stable, but the comparer may not be: GetHashCode() is randomized per process, so exported state for string elements (or any type with a randomized hash) is only meaningful when re-imported within the same process, or when a custom comparer with a stable hash is used.

UnionWith(BloomFilter<T>) merges another filter into this one by bitwise OR. The two filters must be compatible - the same BitCount, the same HashCount, and the same (or equal) comparer - which in practice means they were constructed with the same parameters. After the merge this filter reports an element as possibly present when either source filter would have.

The export format produced by TryExport(Span<byte>, out int) / Export(Span<byte>) and consumed by Import(ReadOnlySpan<byte>, IEqualityComparer<T>?) is an opaque, version-checked snapshot, not a wire contract; its layout may change between library versions with a corresponding version-byte bump.

BloomFilter<T> is not thread-safe. Concurrent reads and writes require external synchronization.

Constructors

BloomFilter(int, double)

Initializes a new instance of the BloomFilter<T> class sized for the expected element count and target false-positive rate, using the default equality comparer.

public BloomFilter(int expectedItems, double falsePositiveRate)

Parameters

expectedItems int

The number of distinct elements the filter is expected to hold.

falsePositiveRate double

The target false-positive probability at the expected fill.

Exceptions

ArgumentOutOfRangeException

expectedItems ≤ 0, falsePositiveRate is outside the exclusive interval (0, 1), or the combination requires more than the maximum supported number of bits.

BloomFilter(int, double, IEqualityComparer<T>?)

Initializes a new instance of the BloomFilter<T> class sized for the expected element count and target false-positive rate, using the specified equality comparer.

public BloomFilter(int expectedItems, double falsePositiveRate, IEqualityComparer<T>? comparer)

Parameters

expectedItems int

The number of distinct elements the filter is expected to hold.

falsePositiveRate double

The target false-positive probability at the expected fill.

comparer IEqualityComparer<T>

The equality comparer whose hash codes drive bit selection. If null, the default equality comparer for T is used.

Exceptions

ArgumentOutOfRangeException

expectedItems ≤ 0, falsePositiveRate is outside the exclusive interval (0, 1), or the combination requires more than the maximum supported number of bits.

Properties

BitCount

Gets the number of addressable bits in the filter (m).

public int BitCount { get; }

Property Value

int

The bit count derived from the constructor arguments; always at least 1.

Comparer

Gets the equality comparer whose hash codes drive bit selection.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The IEqualityComparer<T> instance supplied at construction, or the default comparer.

DesignFalsePositiveRate

Gets the false-positive probability the filter was sized for.

public double DesignFalsePositiveRate { get; }

Property Value

double

The falsePositiveRate constructor argument. The observed rate approaches this value as the element count approaches ExpectedItems and exceeds it beyond that point.

EstimatedFalsePositiveRate

Gets the false-positive probability implied by the current fill of the filter.

public double EstimatedFalsePositiveRate { get; }

Property Value

double

The probability that MightContain(T) reports a never-added element as present, computed as (setBits / m)^k from the current bit density. Zero for an empty filter.

Remarks

The value is recomputed on each access by counting the set bits, an O(BitCount / 64) scan.

ExpectedItems

Gets the number of distinct elements the filter was sized for (n).

public int ExpectedItems { get; }

Property Value

int

The expectedItems constructor argument.

HashCount

Gets the number of bit positions probed per element (k).

public int HashCount { get; }

Property Value

int

The hash count derived from the constructor arguments; always at least 1.

Methods

Add(T)

Adds an element to the filter. After the call, MightContain(T) is guaranteed to return true for the element.

public void Add(T item)

Parameters

item T

The element to add. Must not be null.

Remarks

Adding the same element again is a no-op on the bit array. Elements cannot be removed; use Clear() to reset the entire filter.

Exceptions

ArgumentNullException

item is null.

Clear()

Removes all elements from the filter by clearing every bit.

public void Clear()

Export(Span<byte>)

Writes the filter state to destination, which must be at least GetExportByteCount() bytes long.

public void Export(Span<byte> destination)

Parameters

destination Span<byte>

The buffer that receives the exported state.

Exceptions

ArgumentException

destination is shorter than GetExportByteCount() bytes.

GetExportByteCount()

Returns the number of bytes required to export the filter state via TryExport(Span<byte>, out int) or Export(Span<byte>).

public int GetExportByteCount()

Returns

int

The exact export size in bytes for this filter's configuration.

Import(ReadOnlySpan<byte>, IEqualityComparer<T>?)

Creates a BloomFilter<T> from state previously produced by TryExport(Span<byte>, out int) or Export(Span<byte>).

public static BloomFilter<T> Import(ReadOnlySpan<byte> source, IEqualityComparer<T>? comparer = null)

Parameters

source ReadOnlySpan<byte>

The exported filter state.

comparer IEqualityComparer<T>

The equality comparer to associate with the imported filter. Must be the comparer (or an equal comparer) the exporting filter used, or membership results are undefined. If null, the default equality comparer for T is used.

Returns

BloomFilter<T>

A new filter whose membership state matches the exported filter.

Remarks

The comparer is not part of the exported state; the caller must re-supply it. For element types with process-randomized hash codes (notably string under the default comparer), an export is only meaningful within the process that produced it.

The snapshot's hash count is bounded at import so a hostile or corrupted snapshot cannot inflate the per-operation cost of Add(T) and MightContain(T) (both are O(HashCount)).

Exceptions

ArgumentException

source is truncated, carries an unsupported format version, or does not describe a valid filter.

ArgumentOutOfRangeException

The snapshot's hash count exceeds the largest value the sizing constructor can produce (1075, the value implied by the smallest representable false-positive rate).

MightContain(T)

Determines whether the element might be a member of the filter.

public bool MightContain(T item)

Parameters

item T

The element to test. Must not be null.

Returns

bool

false when the element was definitely never added; true when the element was added or is a false positive (with probability approximated by EstimatedFalsePositiveRate).

Exceptions

ArgumentNullException

item is null.

TryExport(Span<byte>, out int)

Attempts to write the filter state to destination.

public bool TryExport(Span<byte> destination, out int bytesWritten)

Parameters

destination Span<byte>

The buffer that receives the exported state.

bytesWritten int

When the method returns true, the number of bytes written (always GetExportByteCount()); otherwise 0.

Returns

bool

true when destination is large enough and the state was written; otherwise false.

UnionWith(BloomFilter<T>)

Merges another compatible filter into this one so that this filter subsequently reports an element as possibly present when either source filter would have.

public void UnionWith(BloomFilter<T> other)

Parameters

other BloomFilter<T>

The filter to merge into this one. Must not be null.

Remarks

Compatibility requires identical BitCount and HashCount and the same or an equal comparer instance - in practice, filters constructed with the same parameters. The other filter is not modified. Merging raises this filter's bit density and therefore its EstimatedFalsePositiveRate.

Comparer identity is decided by Equals(object) (after a reference check). Two distinct instances of a custom comparer type that does not override Equals(object) compare unequal even when behaviourally identical, and the merge is rejected. Share a single comparer instance between filters that will be merged, or override Equals (and GetHashCode) on the comparer type.

Exceptions

ArgumentNullException

other is null.

ArgumentException

other is incompatible: its BitCount, HashCount, or comparer differs from this filter's.

Applies to

ProductVersions
.NET8, 10