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.

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

Constructors

Name	Description
`this` (nentries)	construct a Bloom filter optimized for nentries

Methods

Name	Description
`clear` ()	clear all bits
`insert` (key)	insert a key
`reset` ()	free all bits
`resize` (nentries)	resize to nentries, all bits are cleared
`size` ()	get the reserved number of entries
`test` (key)	test membership of key

Parameters

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