Class BloomFilter

Class Documentation

class BloomFilter

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.

Public Functions

BloomFilter(count numHashes, count size = 6291469)

Constructor. Space complexity: numHashes * size bytes.

  • numHashes[in] Number of different hash functions that should be used. Actually, the implementation uses numHashes different random salts instead and one hash function only.

  • size[in] Size of each hash array.

virtual ~BloomFilter() = default


void insert(index key)

Inserts key into Bloom filter.


key[in] Key to be inserted.

bool isMember(index key) const

key[in] Key to be queried for set membership.


True if is member, false otherwise.