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.

Asymptotic false-positive rates for different BitsPerEntry settings.

$(TR $(THX BitsPerEntry, False Positive Rate)) $(TR $(TDX 1, 63.2%)) $(TR $(TDX 2, 39.3%)) $(TR $(TDX 3, 23.7%)) $(TR $(TDX 4, 14.7%)) $(TR $(TDX 5, 9.18%)) $(TR $(TDX 6, 5.61%)) $(TR $(TDX 7, 3.47%)) $(TR $(TDX 8, 2.15%)) $(TR $(TDX 9, 1.33%))

struct BloomFilter(size_t BitsPerEntry = 4, CheapHash cheapHash = CheapHash.yes)
struct BloomFilter (
size_t BitsPerEntry = 4
CheapHash cheapHash = CheapHash.yes
) if (
BitsPerEntry > 0
) {
this(this);
this(size_t nentries);
void insert(size_t key);
bool test(size_t key);
~this();
void reset();
void clear();
size_t size();
void resize(size_t nentries);
}
template BloomFilter(size_t BitsPerEntry = 4, bool cheapHash = true)

Constructors

this this(size_t nentries): construct a Bloom filter optimized for nentries

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): no copying

Members

Functions

clear void clear(): clear all bits
insert void insert(size_t key): insert a key
reset void reset(): free all bits
resize void resize(size_t nentries): resize to nentries, all bits are cleared
size size_t size(): get the reserved number of entries
test bool test(size_t key): test membership of key

Parameters

BitsPerEntry: Set the number of bits allocated per entry.
cheapHash: Use a faster but less good hash function.

Examples

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));

Using 6 bits per entry.

auto filter = BloomFilter!6(16);

Using a better but slower hash function.

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