Bloom Filter

template<std::size_t HC, std::size_t MC, template<typename...> class HF = mmh3_hash_factory, typename T = std::string, typename S = uint32_t>
class pdstl::bloom_filter : public pdstl::membership<T>

Standard Bloom Filter.

bloom_filter class implements bloom filter algorithm for solving membership problem.

Template Parameters

  • HC: - Number of hash functions

  • MC: - Number of memory bits

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

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

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

Subclassed by pdstl::counting_bloom_filter< HC, MC, C, HF, T, S >

Public Functions

bloom_filter()

Default constructor.

void insert(const T &item) override

insert an item into bloom filter

Insert item into bloom filter.

Parameters

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

void erase(const T &item) override

erase an item from bloom filter

Erase is not supported in standard bloom filter. Calling this method 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.