Template Class PrefixFilter

Nested Relationships

Nested Types

Class Documentation

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

an incremental filter of at most n keys of type T: bins of 25 fingerprints of 8 bits over 25 quotients, the overflow in a spare

Public Functions

explicit PrefixFilter(std::size_t n, H h = H())

the empty filter for n keys, its bins at the load 0.95 when they are in, at least one bin

Pre:

n < 2^32

bool insert(const T &x)

inserts x, false (and nothing changed) if n keys are in

Post:

maybe( x ) if true

bool maybe(const T &x) const

false only if x is not in the set

bool 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 is not in the set

void clear(void)

removes all the keys

std::size_t size(void) const

the keys in, with their repetitions

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

the keys that fit, the n of the constructor

double load(void) const

size() / ( 25 bins() ), at most about 0.95

std::size_t bits(void) const

the bits of the bins and of the spare

std::size_t bins(void) const

the bins, of 256 bits each

std::size_t spareSize(void) const

the fingerprints sent to the spare

double expectedSpareSize(void) const

the expected fingerprints sent to the spare when capacity() keys are in, E[ X ] = n - m E[ min( B , 25 ) ]

double falsePositiveRate(void) const

the expected false positives at the current load