bloom.h File Reference

Declaraction of the BF class. More...

Classes
class	BF
	The BF class implements a int --> int hash function bloom filter (In other words, we will only use "hash functions" that work on integers) More...

Typedefs
typedef int(*	hashFunction) (int)

Functions
float	measureFPR (std::vector< int > inList, uint64_t size, std::vector< hashFunction > hashList, unsigned max)
	Measures the false positive rate for a bloom filter The insert should use every hash function in hashList The calculation should query every value between 0 and max-1 (So not including max) HINT: The FPR is calculated using the counts of True Negatives (TN) and False Positives (FP). More...
bool	getBitFromByte (char in, int index)
	A bitmask-based function to get a boolean value from a character To be clear, the character itself isnt relevant – its an encoding of 8 bits! You should assume the left-most bit is 0-indexed. More...
bool	getBitFromArray (std::vector< char > bv, int index)
	A logic-based function to find the correct byte register given an integer index in bits You should assume that the starting character in our vector are the bits 0-7 In other words, our bit vector is indexed from left to right. More...
std::ostream &	operator<< (std::ostream &out, BF const &b)
	Stream operator that allows BF to be written to standard streams (like cout). More...
std::stringstream &	operator<< (std::stringstream &out, BF const &b)
int	easy (int key)
	A series of provided hashes of various (low) quality Designed more for easy calculations than good hash properties. More...
int	cpp (int key)
int	simple (int key)
int	simple2 (int key)
int	simple3 (int key)

Detailed Description

Declaraction of the BF class.

Function Documentation

easy()

int easy

(

int

key

)

A series of provided hashes of various (low) quality Designed more for easy calculations than good hash properties.

Parameters

key	The integer being hashed

Returns

The hash value for the integer

getBitFromArray()

bool getBitFromArray	(	std::vector< char >	bv,
		int	index
	)

A logic-based function to find the correct byte register given an integer index in bits You should assume that the starting character in our vector are the bits 0-7 In other words, our bit vector is indexed from left to right.

NOTE: That is not a guarantee using some other forms of bit encoding! The use of vectors here is to make our approach system agnostic.

HINT: You will have to use one or more bit operations (and, or, xor) to do this.

Parameters

bv	A vector storing a bit vector as a collection of characters (8 bits each)
index	The register whose value we want to get in the vector ofbytes

Returns

The boolean value of the indexed bit

getBitFromByte()

bool getBitFromByte	(	char	in,
		int	index
	)

A bitmask-based function to get a boolean value from a character To be clear, the character itself isnt relevant – its an encoding of 8 bits! You should assume the left-most bit is 0-indexed.

In other words: Bit Index: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

HINT: You will have to use one or more bit operations (and, or, xor) to do this.

Parameters

in	A character representing an eight-bit (one byte) register in the bloom filter
index	The register whose value we want to get in the byte

Returns

The boolean value of the indexed bit

measureFPR()

float measureFPR	(	std::vector< int >	inList,
		uint64_t	size,
		std::vector< hashFunction >	hashList,
		unsigned	max
	)

Measures the false positive rate for a bloom filter The insert should use every hash function in hashList The calculation should query every value between 0 and max-1 (So not including max) HINT: The FPR is calculated using the counts of True Negatives (TN) and False Positives (FP).

Parameters

inList	A vector of integers to be inserted into the bloom filter
size	The size (in bits) of the bloom filter to create
hashList	A vector containing a list of hash functions to use in the BF
max	The size of the range of numbers being tested (our universe)

Returns

A value between 0 and 1 (inclusive) estimating the FPR for the BF under these conditions

operator<<()

std::ostream & operator<<	(	std::ostream &	out,
		BF const &	b
	)

Stream operator that allows BF to be written to standard streams (like cout).

Parameters

out	Stream to write to.
b	BF to write to the stream.