Template Class BlockedBloomFilter

Nested Relationships

Nested Types

Class Documentation

template<class T, class H = DefaultHash<T>>
class BlockedBloomFilter

a filter of Bloom in blocks of 256 bits, 8 bits per item

Public Functions

explicit BlockedBloomFilter(std::size_t n, double bitsPerItem = 10, H h = H())

the empty filter of about bitsPerItem bits for each of n items, in at least one block

Pre:

bitsPerItem > 0

void insert(const T &x)
Post:

maybe( x )

bool maybe(const T &x) const

false only if x was never inserted

void insertHash(std::uint64_t h)

inserts the hash h of 64 bits, which must be random

bool maybeHash(std::uint64_t h) const

false only if the hash h was never inserted

void unite(const BlockedBloomFilter &o)

adds the items of o, as if they had been inserted here

Pre:

o has the blocks of this filter

void clear(void)

removes all the items

std::size_t size(void) const

the insertions made

bool empty(void) const
std::size_t bits(void) const

the bits, 256 per block

std::size_t blocks(void) const
double falsePositiveRate(void) const

the expected false positives after the insertions made, the mean over the Poisson loads of the blocks