Maintains set of (key, value) pairs where key is a 64 bit value and value is an index in a specified range. More...

#include <HashTbl.h>

Inheritance diagram for grafalgo::HashTbl:

Collaboration diagram for grafalgo::HashTbl:

Public Member Functions
	HashTbl (int)
	Constructor for hashTbl, allocates space and initializes table.
	~HashTbl ()
	Destructor for HashTbl.
void	clear ()
	Clear the hashtable contents.
void	resize (int)
	Resize a HashTbl object, discarding old contents.
void	expand (int)
	Expand the space available for this HashTbl.
void	copyFrom (const HashTbl &)
	Copy into this from source.
int	size () const
	Get the number of entries in the table.
index	lookup (uint64_t) const
	Perform a lookup in the hash table.
uint64_t	getKey (index) const
	Get the key associated with a given value.
bool	insert (uint64_t, index)
	Insert a (key,value) pair into hash table.
int	remove (uint64_t)
	Remove a (key, value) pair from the table.
string &	toString (string &) const
	Print out all key,value pairs stored in the hash table, along with their bucket index, offset within the bucket and fingerprint.
Private Types
typedef uint32_t	bkt_t [BKT_SIZ]
	type declaration for buckets
Private Member Functions
void	makeSpace (int)
	Allocate and initialize space for list.
void	freeSpace ()
	Free dynamic storage used by list.
void	hashit (uint64_t, int, uint32_t &, uint32_t &) const
	Compute a bucket index and fingerprint, for a given key.
Private Attributes
int	siz
	number of entries in the table
int	nb
	number of hash buckets per section
int	bktMsk
	mask used to extract bucket index
int	valMsk
	mask used to extract value
int	fpMsk
	mask used to extract fingerprint
bkt_t *	bkt
	vector of hash backets
uint64_t *	keyVec
	vector of keys, indexed by value
Static Private Attributes
static const int	BKT_SIZ = 8
	# of items per bucket
static const int	MAXVAL = (1 << 20)-1
	largest stored value

Detailed Description

Maintains set of (key, value) pairs where key is a 64 bit value and value is an index in a specified range.

All (key,value) pairs must be fully disjoint; that is no two pairs may share the same key and no two pairs may share the same value.

Main methods lookup - returns value for given key insert - adds a (key,value) pair remove - removes the pair for a given key

The implementation uses a 2-left hash table with eight items in each bucket. The hash table is configured for a specified range of values (max of 10^6) with a maximum load factor of 50% to minimize the potential for overloading any bucket.

Definition at line 33 of file HashTbl.h.

Constructor & Destructor Documentation

grafalgo::HashTbl::HashTbl ( int n1 )

Constructor for hashTbl, allocates space and initializes table.

N1 is the limit on the range of values; it must be less than 2^20.

Definition at line 16 of file HashTbl.cpp.

Here is the call graph for this function:

grafalgo::HashTbl::~HashTbl ( )

Destructor for HashTbl.

Definition at line 19 of file HashTbl.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::HashTbl::clear ( ) [virtual]

Clear the hashtable contents.

Implements grafalgo::Adt.

Definition at line 70 of file HashTbl.cpp.

Here is the caller graph for this function:

void grafalgo::HashTbl::copyFrom ( const HashTbl & source )

Copy into this from source.

Definition at line 79 of file HashTbl.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashTbl::expand ( int size ) [virtual]

Expand the space available for this HashTbl.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 63 of file HashTbl.cpp.

Here is the call graph for this function:

void grafalgo::HashTbl::freeSpace ( ) [private]

Free dynamic storage used by list.

Definition at line 46 of file HashTbl.cpp.

Here is the caller graph for this function:

uint64_t grafalgo::HashTbl::getKey ( index i ) const [inline]

Get the key associated with a given value.

Parameters:

i	is the value whose key is being retrieved

Returns:: the corresponding key; assumes that i is the value for some key

Definition at line 80 of file HashTbl.h.

Here is the caller graph for this function:

void grafalgo::HashTbl::hashit	(	uint64_t	key,
		int	hf,
		uint32_t &	b,
		uint32_t &	fp
	)		const `[private]`

Compute a bucket index and fingerprint, for a given key.

Hashit uses multiplicative hashing with one of two different multipliers, after first converting the 64 bit integer into a 32 bit integer.

Parameters:

key	is the key to be hashed
hf	is either 0 or 1 and selects one of two hash functions
b	is a reference; on return its value is equal to the hash bucket for the given key
fp	is a reference; on return its value is equal to the fingerprint for the given key

Definition at line 99 of file HashTbl.cpp.

Here is the caller graph for this function: