userver: utils::FilterBloom< T, Counter, Hash1, Hash2 > Class Template Reference
Loading...
Searching...
No Matches
utils::FilterBloom< T, Counter, Hash1, Hash2 > Class Template Referencefinal

#include <userver/utils/filter_bloom.hpp>

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
Tthe type of element that counts
Counterthe type of counter
Hash1the first callable hash struct
Hash2the 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 37 of file 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.
 

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 42 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 132 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 120 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 127 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 106 of file filter_bloom.hpp.


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