Struct BloomFilter

A bloom filter is a fast and space-efficient probabilistic data structure to test whether an element is member of a set. False positive matches are possible, false negative matches are not. Elements can only be added not removed.

struct BloomFilter(ulong BitsPerEntry = 4, std.typecons.Flag!("cheapHash") cheapHash = CheapHash.yes)
  
if (BitsPerEntry > 0);

Asymptotic false-positive rates for different BitsPerEntry settings.

BitsPerEntryFalse Positive Rate
163.2%
239.3%
323.7%
414.7% (default)
59.18%
65.61%
73.47%
82.15%
91.33%

Constructors

NameDescription
this construct a Bloom filter optimized for nentries

Methods

NameDescription
clear clear all bits
insert insert a key
reset free all bits
resize resize to nentries, all bits are cleared
size get the reserved number of entries
test test membership of key

Parameters

NameDescription
BitsPerEntry Set the number of bits allocated per entry (default 4).
cheapHash Use a faster but less good hash function.

Example

Default BloomFilter for 16 entries.

auto filter = BloomFilter!()(16);
filter.insert(1);
assert(filter.test(1));
assert(!filter.test(2));
filter.insert(2);
assert(filter.test(2));

Example

Using 6 bits per entry.

auto filter = BloomFilter!6(16);

Example

Using a better but slower hash function.

auto filter = BloomFilter!(4, CheapHash.no)(16);