honey::BloomFilter< T, Block, Alloc > Class Template Reference

A space-efficient probabilistic data structure that is used to test set membership. Can be tuned to use less space at the expense of increased false positive probabilty. More...

#include <BloomFilter.h>

Public Types
typedef BitSet_< Block, Alloc >	BitSet

Public Member Functions
	BloomFilter (szt elemCount, Double errorProb=0.01, const Alloc &a=Alloc())
void	insert (const T &obj)
	Insert element into set. More...
bool	contains (const T &obj) const
	Check if element is in the set, may return false positive. More...
void	clear ()
	Remove all elements from the set. More...
Double	errorProb () const
	Get false positive probability. More...
const BitSet &	bits () const
	Get underlying bit array. More...

Detailed Description

template<class T, class Block = uint64, class Alloc = std::allocator<Block>>
class honey::BloomFilter< T, Block, Alloc >

A space-efficient probabilistic data structure that is used to test set membership. Can be tuned to use less space at the expense of increased false positive probabilty.

At 1% false positive chance each element uses about 9.6 bits, a further 4.8 bits decreases the error chance ten-fold. By comparison unordered_set uses about 20 bytes per element.
Note that the elements themselves aren't stored in the bloom filter, and further, elements can't be removed once added.

Member Typedef Documentation

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

typedef BitSet_<Block, Alloc> honey::BloomFilter< T, Block, Alloc >::BitSet

Constructor & Destructor Documentation

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

honey::BloomFilter< T, Block, Alloc >::BloomFilter ( szt  elemCount, Double  errorProb = 0.01, const Alloc &  a = Alloc()  )

inline

Parameters

elemCount	Number of elements expected to be inserted into the set
errorProb	Probability that contains() will return true even though the element hasn't actually been inserted into the set
a

Member Function Documentation

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

const BitSet& honey::BloomFilter< T, Block, Alloc >::bits ( ) const

inline

Get underlying bit array.

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

void honey::BloomFilter< T, Block, Alloc >::clear ( )

inline

Remove all elements from the set.

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

bool honey::BloomFilter< T, Block, Alloc >::contains ( const T &  obj ) const

inline

Check if element is in the set, may return false positive.

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

Double honey::BloomFilter< T, Block, Alloc >::errorProb ( ) const

inline

Get false positive probability.

template<class T , class Block = uint64, class Alloc = std::allocator<Block>>

void honey::BloomFilter< T, Block, Alloc >::insert ( const T &  obj )

inline

Insert element into set.

---

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

• src/common/Honey/Misc/BloomFilter.h