All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
Aux::BloomFilter Class Reference

Bloom filter for fast set membership queries for type index with one-sided error (false positives). More...

#include <BloomFilter.h>

Public Member Functions

 BloomFilter (count numHashes, count size=6291469)
 Constructor. More...
 
virtual ~BloomFilter ()=default
 Destructor. More...
 
void insert (index key)
 Inserts key into Bloom filter. More...
 
bool isMember (index key) const
 

Detailed Description

Bloom filter for fast set membership queries for type index with one-sided error (false positives).

Uses one hash function instead of many but different random salts instead.

Constructor & Destructor Documentation

Aux::BloomFilter::BloomFilter ( count  numHashes,
count  size = 6291469 
)

Constructor.

Space complexity: numHashes * size bytes.

Parameters
[in]numHashesNumber of different hash functions that should be used. Actually, the implementation uses numHashes different random salts instead and one hash function only.
[in]sizeSize of each hash array.
virtual Aux::BloomFilter::~BloomFilter ( )
virtualdefault

Destructor.

Member Function Documentation

void Aux::BloomFilter::insert ( index  key)

Inserts key into Bloom filter.

Parameters
[in]keyKey to be inserted.
bool Aux::BloomFilter::isMember ( index  key) const
Parameters
[in]keyKey to be queried for set membership.
Returns
True if is member, false otherwise.

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