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