Template Class CuckooFilter
Defined in File CuckooFilter.h
Class Documentation
-
template<class T, class F = std::uint8_t, class H = DefaultHash<T>>
class CuckooFilter a dynamic filter of the keys of type T with fingerprints of type F (8 or 16 bits), 2 buckets of 4 places per key
Public Functions
-
explicit CuckooFilter(std::size_t n, H h = H())
the empty filter for n keys, at the load 0.94 when they are in, in at least one bucket
- Pre:
n < 2^32
-
bool insert(const T &x)
inserts x, false (and nothing changed) if the filter is full
- Post:
maybe( x ) if true
-
bool remove(const T &x)
removes one insertion of x, false if x is not there
- Pre:
x was inserted (otherwise another key may be lost)
-
bool insertHash(std::uint64_t h)
inserts the hash h of 64 bits, which must be random
-
bool removeHash(std::uint64_t h)
removes one insertion of the hash h
-
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 places, 4 per bucket
-
double load(void) const
-
std::size_t bits(void) const
the bits of the buckets
-
explicit CuckooFilter(std::size_t n, H h = H())