utils::FilterBloom< T, Counter, Hash1, Hash2 > Class Template Reference

Space-efficient probabilistic data structure. More...

#include <userver/utils/filter_bloom.hpp>

Public Member Functions
	FilterBloom (std::size_t counters_num=256, Hash1 hash_1=Hash1{}, Hash2 hash_2=Hash2{})
	Constructs filter Bloom with the specified number of counters.
void	Increment (const T &item)
	Increments the smallest item counters.
Counter	Estimate (const T &item) const
	Returns the value of the smallest item counter.
bool	Has (const T &item) const
	Checks that all counters of the item have been incremented.
void	Clear ()
	Resets all counters.

Detailed Description

template<typename T, typename Counter = unsigned, typename Hash1 = boost::hash<T>, typename Hash2 = std::hash<T>>
class utils::FilterBloom< T, Counter, Hash1, Hash2 >

Space-efficient probabilistic data structure.

Used to test whether a count number of a given element is smaller than a given threshold when a sequence of elements is given. As a generalized form of Bloom filter, false positive matches are possible, but false negatives are not.

Parameters

T	the type of element that counts
Counter	the type of counter
Hash1	the first callable hash struct
Hash2	the second callable hash struct

Example:

  utils::FilterBloom<int> filter_bloom(16 * 1024);
  for (int i = 0; i < 512; ++i) {
    for (std::size_t j = 0; j < 5; ++j) {
      filter_bloom.Increment(i);
    }
  }
  for (int i = 512; i < 1024; ++i) {
    for (std::size_t j = 0; j < 10; ++j) {
      filter_bloom.Increment(i);
    }
  }
 
  for (int i = 0; i < 512; ++i) {
    EXPECT_GE(7, filter_bloom.Estimate(i));
  }
  for (int i = 512; i < 1024; ++i) {
    EXPECT_LE(10, filter_bloom.Estimate(i));
  }

Definition at line 38 of file filter_bloom.hpp.

Constructor & Destructor Documentation

FilterBloom()

template<typename T , typename Counter = unsigned, typename Hash1 = boost::hash<T>, typename Hash2 = std::hash<T>>

utils::FilterBloom< T, Counter, Hash1, Hash2 >::FilterBloom ( std::size_t  counters_num = 256, Hash1  hash_1 = Hash1{}, Hash2  hash_2 = Hash2{}  )

inlineexplicit

Constructs filter Bloom with the specified number of counters.

Note

If expected to increment n times is recommended to set counters_num to 16 * n

Definition at line 43 of file filter_bloom.hpp.

Member Function Documentation

Clear()

template<typename T , typename Counter , typename Hash1 , typename Hash2 >

void utils::FilterBloom< T, Counter, Hash1, Hash2 >::Clear

(

)

Resets all counters.

Definition at line 141 of file filter_bloom.hpp.

Estimate()

template<typename T , typename Counter , typename Hash1 , typename Hash2 >

Counter utils::FilterBloom< T, Counter, Hash1, Hash2 >::Estimate

(

const T &

item

)

const

Returns the value of the smallest item counter.

Definition at line 129 of file filter_bloom.hpp.

Has()

template<typename T , typename Counter , typename Hash1 , typename Hash2 >

bool utils::FilterBloom< T, Counter, Hash1, Hash2 >::Has

(

const T &

item

)

const

Checks that all counters of the item have been incremented.

Definition at line 136 of file filter_bloom.hpp.

Increment()

template<typename T , typename Counter , typename Hash1 , typename Hash2 >

void utils::FilterBloom< T, Counter, Hash1, Hash2 >::Increment

(

const T &

item

)

Increments the smallest item counters.

Definition at line 113 of file filter_bloom.hpp.

---

The documentation for this class was generated from the following file:

• userver/utils/filter_bloom.hpp