The basic Bloom filter. More...
#include <basic.h>
Public Member Functions  
basic_bloom_filter (hasher h, size_t cells)  
Constructs a basic Bloom filter. More...  
basic_bloom_filter (double fp, size_t capacity, size_t seed=0, bool double_hashing=true)  
Constructs a basic Bloom filter by given a desired falsepositive probability and an expected number of elements. More...  
basic_bloom_filter (basic_bloom_filter &&)  
virtual void  add (object const &o) override 
Adds an element to the Bloom filter. More...  
virtual size_t  lookup (object const &o) const override 
Retrieves the count of an element. More...  
virtual void  clear () override 
Removes all items from the Bloom filter.  
void  remove (object const &o) 
Removes an object from the Bloom filter. More...  
void  swap (basic_bloom_filter &other) 
Swaps two basic Bloom filters. More...  
Public Member Functions inherited from bf::bloom_filter  
template<typename T >  
void  add (T const &x) 
Adds an element to the Bloom filter. More...  
template<typename T >  
size_t  lookup (T const &x) const 
Retrieves the count of an element. More...  
Static Public Member Functions  
static size_t  m (double fp, size_t capacity) 
Computes the number of cells based on a falsepositive rate and capacity. More...  
static size_t  k (size_t cells, size_t capacity) 
Computes \(k^*\), the optimal number of hash functions for a given Bloom filter size (in terms of cells) and capacity. More...  
Private Attributes  
hasher  hasher_ 
bitvector  bits_ 
The basic Bloom filter.
bf::basic_bloom_filter::basic_bloom_filter  (  hasher  h, 
size_t  cells  
) 
bf::basic_bloom_filter::basic_bloom_filter  (  double  fp, 
size_t  capacity,  
size_t  seed = 0 , 

bool  double_hashing = true 

) 
Constructs a basic Bloom filter by given a desired falsepositive probability and an expected number of elements.
The implementation computes the optimal number of hash function and required space.
fp  The desired falsepositive probability. 
capacity  The desired falsepositive probability. 
seed  The initial seed used to construct the hash functions. 
double_hashing  Flag indicating whether to use default or double hashing. 
Definition at line 25 of file basic.cc.
References k(), m(), and bf::bitvector::resize().

overridevirtual 
Adds an element to the Bloom filter.
o  A wrapped object. 
Implements bf::bloom_filter.
Definition at line 40 of file basic.cc.
References bf::bitvector::set(), and bf::bitvector::size().

static 
Computes \(k^*\), the optimal number of hash functions for a given Bloom filter size (in terms of cells) and capacity.
cells  The number of cells in the Bloom filter (aka. m) 
capacity  The maximum number of elements that can guarantee fp. 
Definition at line 13 of file basic.cc.
Referenced by basic_bloom_filter().

overridevirtual 
Retrieves the count of an element.
o  A wrapped object. 
Implements bf::bloom_filter.
Definition at line 46 of file basic.cc.
References bf::bitvector::size().

static 
Computes the number of cells based on a falsepositive rate and capacity.
fp  The desired falsepositive rate 
capacity  The maximum number of items. 
Definition at line 7 of file basic.cc.
Referenced by basic_bloom_filter().
void bf::basic_bloom_filter::remove  (  object const &  o  ) 
Removes an object from the Bloom filter.
May introduce false negatives because the bitvector indices of the object to remove may be shared with other objects.
o  The object to remove. 
Definition at line 59 of file basic.cc.
References bf::bitvector::reset(), and bf::bitvector::size().
void bf::basic_bloom_filter::swap  (  basic_bloom_filter &  other  ) 