Cuckoo Filter

template<typename CT, template<typename...> class HF = mmh3_hash_factory, typename T = std::string, typename S = uint32_t>
class pdstl::cuckoo_filter : public pdstl::membership<T>

Cuckoo Filter.

cuckoo_filter class implements cuckoo filter algorithm for solving membership problem.

Template Parameters

  • CT: - cuckoo table

  • HF: - Hash factory method class (default: pdstl::mmh3_hash_factory)

  • T: - Element type which will be inserted into cuckoo filter (default: std::string)

  • S: - Hash output type (default: uint32_t)

Public Functions

cuckoo_filter(size_t num_buckets, size_t max_kicks)

Default constructor.

Parameters

  • num_buckets: - number of buckets in this filter

void insert(const T &item) override

insert an item into quotient filter

Parameters

  • item: - the item to insert into the quotient filter.

void erase(const T &item) override

Erase is not supported in standard quotient filter. will throw an exception.

Parameters

  • item: - the item to erase from filter.

void clear() override

Clear filter and resets its internal memory.

bool contains(const T &item) const override

Check the item and report that it’s in the filter or not.

Return

false if the item is not in the filter, true if item may be in the filter.

Parameters

  • item: - the item to check for existence.