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.

Parameters:

• 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¶

Destructor.

void insert(index key)¶

Inserts key into Bloom filter.

Parameters:

key – [in] Key to be inserted.

bool isMember(index key) const¶

Parameters:

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

Returns:

True if is member, false otherwise.