A space-efficent probabilistic set for membership test, false postives are possible, but false negatives are not. More...

#include <BloomFilter.h>

Public Member Functions
	BasicBloomFilter (size_t items_estimate, float false_positive_prob)
	Constructor. More...

	BasicBloomFilter (size_t items_estimate, float bits_per_item, size_t num_hashes)
	Alternative constructor. More...

	BasicBloomFilter (size_t items_estimate, size_t items_actual, int64_t length, size_t num_hashes)
	Alternative constructor. More...

	~BasicBloomFilter ()
	Destructor; releases resources. More...

void	insert (const void *key, size_t len)
	Inserts a new blob into the hash. More...

void	insert (const String &key)
	Overloaded insert function for Strings. More...

bool	may_contain (const void *key, size_t len) const
	Checks if the data set "may" contain the key. More...

bool	may_contain (const String &key) const
	Overloaded may_contain function for Strings. More...

void	serialize (StaticBuffer &buf)
	Serializes the BloomFilter into a static memory buffer. More...

uint8_t *	ptr ()
	Getter for the bloom filter data. More...

size_t	size ()
	Getter for the bloom filter size. More...

size_t	get_num_hashes ()
	Getter for the number of hash functions. More...

size_t	get_length_bits ()
	Getter for the number of bits. More...

size_t	get_items_estimate ()
	Getter for the estimated number of items. More...

size_t	get_items_actual ()
	Getter for the actual number of items. More...

Private Attributes
HasherT	m_hasher
	The hash function implementation. More...

size_t	m_items_estimate
	Estimated number of items. More...

size_t	m_items_actual
	Actual number of items. More...

float	m_false_positive_prob
	Probability of returning a false positive. More...

size_t	m_num_hash_functions
	Number of hash functions. More...

size_t	m_num_bits
	Number of bits. More...

size_t	m_num_bytes
	Number of bytes (approx. More...

uint8_t *	m_bloom_bits
	The actual bloom filter bit-array. More...

Detailed Description

template<class HasherT = MurmurHash2>
class Hypertable::BasicBloomFilter< HasherT >

A space-efficent probabilistic set for membership test, false postives are possible, but false negatives are not.

Definition at line 50 of file BloomFilter.h.

Constructor & Destructor Documentation

template<class HasherT = MurmurHash2>

Hypertable::BasicBloomFilter< HasherT >::BasicBloomFilter	(	size_t	items_estimate,
		float	false_positive_prob
	)

inline

Constructor.

Parameters

items_estimate	An estimated number of items that will be inserted
false_positive_prob	The probability for false positives

Definition at line 58 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

Hypertable::BasicBloomFilter< HasherT >::BasicBloomFilter	(	size_t	items_estimate,
		float	bits_per_item,
		size_t	num_hashes
	)

inline

Alternative constructor.

Parameters

items_estimate	An estimated number of items that will be inserted
bits_per_item	Average bits per item
num_hashes	Number of hash functions for the filter

Definition at line 88 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

Hypertable::BasicBloomFilter< HasherT >::BasicBloomFilter	(	size_t	items_estimate,
		size_t	items_actual,
		int64_t	length,
		size_t	num_hashes
	)

inline

Alternative constructor.

Parameters

items_estimate	An estimated number of items that will be inserted
items_actual	Actual number of items
length	Number of bits
num_hashes	Number of hash functions for the filter

Definition at line 117 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

Hypertable::BasicBloomFilter< HasherT >::~BasicBloomFilter ( )

inline

Destructor; releases resources.

Definition at line 141 of file BloomFilter.h.

Member Function Documentation

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::get_items_actual ( )

inline

Getter for the actual number of items.

Returns: The actual number of items

Definition at line 256 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::get_items_estimate ( )

inline

Getter for the estimated number of items.

Returns: The estimated number of items

Definition at line 250 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::get_length_bits ( )

inline

Getter for the number of bits.

Returns: The number of bits

Definition at line 244 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::get_num_hashes ( )

inline

Getter for the number of hash functions.

Returns: The number of hash functions

Definition at line 238 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

void Hypertable::BasicBloomFilter< HasherT >::insert	(	const void *	key,
		size_t	len
	)

inline

Inserts a new blob into the hash.

Runs through each hash function and sets the appropriate bit for each hash.

Parameters

key	Pointer to the key's data
len	Size of the data (in bytes)

Definition at line 159 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

void Hypertable::BasicBloomFilter< HasherT >::insert ( const String & key )

inline

Overloaded insert function for Strings.

Parameters

key	Reference to the string.

Definition at line 173 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

bool Hypertable::BasicBloomFilter< HasherT >::may_contain	(	const void *	key,
		size_t	len
	)		const

inline

Checks if the data set "may" contain the key.

This can return false positives.

This function runs through all hash tables and checks if the hashed bit is set. If any of them is not set then the key is definitely not part of the data set. If all bits are set then the key "may" be in the data set.

Parameters

key	Pointer to the key's data
len	Size of the data (in bytes)

Returns: true if the key "may" be contained, otherwise false

Definition at line 188 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

bool Hypertable::BasicBloomFilter< HasherT >::may_contain ( const String & key ) const

inline

Overloaded may_contain function for Strings.

Parameters

key	The String to look for

Returns: true if the key "may" be contained, otherwise false

Definition at line 210 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

uint8_t* Hypertable::BasicBloomFilter< HasherT >::ptr ( )

inline

Getter for the bloom filter data.

Returns: A pointer to the bloom filter data

Definition at line 226 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

void Hypertable::BasicBloomFilter< HasherT >::serialize ( StaticBuffer & buf )

inline

Serializes the BloomFilter into a static memory buffer.

Parameters

buf	The static memory buffer

Definition at line 218 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::size ( )

inline

Getter for the bloom filter size.

Returns: The size of the bloom filter data (in bytes)

Definition at line 232 of file BloomFilter.h.

Member Data Documentation

template<class HasherT = MurmurHash2>

uint8_t* Hypertable::BasicBloomFilter< HasherT >::m_bloom_bits

private

The actual bloom filter bit-array.

Definition at line 281 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

float Hypertable::BasicBloomFilter< HasherT >::m_false_positive_prob

private

Probability of returning a false positive.

Definition at line 269 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

HasherT Hypertable::BasicBloomFilter< HasherT >::m_hasher

private

The hash function implementation.

Definition at line 260 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::m_items_actual

private

Actual number of items.

Definition at line 266 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::m_items_estimate

private

Estimated number of items.

Definition at line 263 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::m_num_bits

private

Number of bits.

Definition at line 275 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::m_num_bytes

private

Number of bytes (approx.

m_num_bits / 8)

Definition at line 278 of file BloomFilter.h.

template<class HasherT = MurmurHash2>

size_t Hypertable::BasicBloomFilter< HasherT >::m_num_hash_functions

private

Number of hash functions.

Definition at line 272 of file BloomFilter.h.

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

/home/doug/src/hypertable/src/cc/Common/BloomFilter.h

Public Member Functions

Private Attributes

Detailed Description

template<class HasherT = MurmurHash2> class Hypertable::BasicBloomFilter< HasherT >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class HasherT = MurmurHash2>
class Hypertable::BasicBloomFilter< HasherT >