BlockedBloomFilter Class
A Bloom filter that stores the bits of each value in a single 64-byte block (one cache line).
public closed class BlockedBloomFilterRemarks
A BloomFilter spreads the bits of a value over the whole filter, so adding or finding a value in a filter larger than the CPU caches reads HashCount unrelated cache lines. A blocked filter chooses one block from the hash and sets every bit of the value inside it: one cache line per operation. Blocks do not fill evenly, so a blocked filter needs a little more memory for the same false positive probability; size it with BlockedBloomFilterSize.
Methods
CreateAdler32(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterAdler32 CreateAdler32(BlockedBloomFilterSize size)No documentation is available.
CreateCrc32(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterCrc32 CreateCrc32(BlockedBloomFilterSize size)No documentation is available.
CreateCrc64(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterCrc64 CreateCrc64(BlockedBloomFilterSize size)No documentation is available.
CreateXXHash128(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterXXHash128 CreateXXHash128(BlockedBloomFilterSize size)No documentation is available.
CreateXXHash3(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterXXHash3 CreateXXHash3(BlockedBloomFilterSize size)No documentation is available.
CreateXXHash32(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterXXHash32 CreateXXHash32(BlockedBloomFilterSize size)No documentation is available.
CreateXXHash64(BlockedBloomFilterSize)
BloomFilter.g.cspublic static BlockedBloomFilterXXHash64 CreateXXHash64(BlockedBloomFilterSize size)No documentation is available.
GetEstimateCount()
BlockedBloomFilter.csLoad overloads
Load(Stream)
BlockedBloomFilter.Snapshot.csCreates a filter from a snapshot written by BlockedBloomFilter.Save.
public static BlockedBloomFilter Load(Stream stream)Parameters
streamStream- The stream to read the snapshot from. It is left positioned after the snapshot.
Returns
BlockedBloomFilter A new filter of the hash algorithm, size and content of the snapshot, such as a BlockedBloomFilterXXHash128.
Exceptions
InvalidDataException- The data is not a blocked Bloom filter snapshot, is truncated or corrupted, uses an unsupported version, or was written on a machine with another byte order.
Remarks
The header is validated before the filter is allocated. When the stream is seekable, its length is also checked against the size of the filter first. The snapshot ends with a checksum, verified once it is read.
Load<TFilter>(Stream)
BlockedBloomFilter.Snapshot.csCreates a filter of a given type from a snapshot written by BlockedBloomFilter.Save.
public static TFilter Load<TFilter>(Stream stream) where TFilter : BlockedBloomFilterType parameters
TFilter- The type of the filter, such as
BlockedBloomFilterXXHash128.
Parameters
streamStream- The stream to read the snapshot from. It is left positioned after the snapshot.
Returns
TFilter A new filter of the size and content of the snapshot.
Exceptions
InvalidDataException- The snapshot contains a filter of another type, or is not valid (see
BlockedBloomFilter.Load).
LoadAsync overloads
LoadAsync(Stream, CancellationToken)
BlockedBloomFilter.Snapshot.csCreates a filter from a snapshot written by BlockedBloomFilter.Save or BlockedBloomFilter.SaveAsync.
public static Task<BlockedBloomFilter> LoadAsync(Stream stream, CancellationToken cancellationToken = default)Parameters
streamStream- The stream to read the snapshot from. It is left positioned after the snapshot.
cancellationTokenCancellationToken- A token to cancel the operation.
Returns
Task<BlockedBloomFilter> A new filter of the hash algorithm, size and content of the snapshot.
Exceptions
InvalidDataException- The snapshot is not valid (see
BlockedBloomFilter.Load).
LoadAsync<TFilter>(Stream, CancellationToken)
BlockedBloomFilter.Snapshot.csCreates a filter of a given type from a snapshot written by BlockedBloomFilter.Save or BlockedBloomFilter.SaveAsync.
public static Task<TFilter> LoadAsync<TFilter>(Stream stream, CancellationToken cancellationToken = default) where TFilter : BlockedBloomFilterType parameters
TFilter- The type of the filter, such as
BlockedBloomFilterXXHash128.
Parameters
streamStream- The stream to read the snapshot from. It is left positioned after the snapshot.
cancellationTokenCancellationToken- A token to cancel the operation.
Returns
Task<TFilter> A new filter of the size and content of the snapshot.
Exceptions
InvalidDataException- The snapshot contains a filter of another type, or is not valid (see
BlockedBloomFilter.Load).
Save(Stream)
BlockedBloomFilter.Snapshot.csWrites a snapshot of the filter to a stream: its hash algorithm, its size and its bits.
Parameters
streamStream- The stream to write the snapshot to.
Remarks
The bits are copied through a small buffer, so saving a large filter does not allocate a second copy of it.
Stop adding values while the snapshot is written. Each bit is read atomically, but values added during the write may be partially saved: some of their bits are in the snapshot, others are not, so the restored filter may report them as absent.
Keys are hashed from their in-memory bytes, so the snapshot records the byte order of the machine, and BlockedBloomFilter.Load rejects a snapshot written on a machine with another byte order.
Example
var filter = BlockedBloomFilter.CreateXXHash128(BlockedBloomFilterSize.CreateOptimalSize(expectedItemCount: 1000, falsePositiveProbability: 0.01));
filter.Add("alice@example.com");
using var stream = new MemoryStream();
filter.Save(stream);
stream.Position = 0;
var restored = BlockedBloomFilter.Load<BlockedBloomFilterXXHash128>(stream);
Assert.True(restored.MayContain("alice@example.com"));
Assert.False(restored.MayContain("bob@example.com"));SaveAsync(Stream, CancellationToken)
BlockedBloomFilter.Snapshot.csWrites a snapshot of the filter to a stream: its hash algorithm, its size and its bits.
public Task SaveAsync(Stream stream, CancellationToken cancellationToken = default)Parameters
streamStream- The stream to write the snapshot to.
cancellationTokenCancellationToken- A token to cancel the operation.
Returns
Task A task that completes when the snapshot is written.
Remarks
See BlockedBloomFilter.Save. Stop adding values until the task completes.
UnionWith(BlockedBloomFilter)
BlockedBloomFilter.csAdds to this filter every value represented by other, by combining their bits with a bitwise OR.
public void UnionWith(BlockedBloomFilter other)Parameters
otherBlockedBloomFilter- The filter whose values are added. It must use the same hash algorithm (the same concrete type), the same number of blocks and the same number of hash functions as this filter. It is not modified.
Exceptions
ArgumentNullExceptionotherisnull.ArgumentExceptionotheruses another hash algorithm, number of blocks or number of hash functions.
Remarks
After the call, MayContain returns true for every value added to this filter or to other before the call: the union never introduces a false negative. Calling the method with the filter itself does nothing.
The result holds the values of both filters in the same number of bits. Its false positive probability is higher than the one the filters were sized for when the total number of values exceeds the expected item count. Size each filter for the total number of values when you plan to merge them.
The compatibility checks happen before any bit is written: when they fail, this filter is left unchanged.
The method can run while other threads call Add or MayContain on either filter. The bits of this filter are set with atomic operations, so no value added concurrently to this filter is lost. The source is read one 64-bit word at a time, not as a snapshot: a value added to other during the call may or may not be included. Once the method has returned, every value that was in other when it was called is included.