Maintains set of (key, value) pairs where key is a 64 bit value and value is a positive 32 bit integer. More...

#include <HashMap.h>

Inheritance diagram for grafalgo::HashMap:

Collaboration diagram for grafalgo::HashMap:

Public Member Functions
	HashMap (int)
	Constructor for HashMap, allocates space and initializes table.
	~HashMap ()
	Destructor for HashMap.
void	clear ()
	Clear the hashtable contents.
void	resize (int)
	Resize a HashMap object.
void	expand (int)
	Expand the space available for this map.
void	copyFrom (const HashMap &)
	Copy into map from src.
index	firstPair () const
	Get the index of the first (key,value) pair in the map.
index	nextPair (index) const
	Get the index of the next (key,value) pair in the map.
uint64_t	key (index) const
	Get the key of the (key,value) pair with a given index.
int	val (index) const
	Get the value of the (key,value) pair with a given index.
int	get (uint64_t) const
	Retrieve value for a given key.
bool	put (uint64_t, int)
	Add a pair to the map.
void	remove (uint64_t)
	Remove an element from the set.
string &	toString (string &) const
Private Member Functions
void	makeSpace (int)
	Allocate and initialize space for map.
void	freeSpace ()
	Free dynamic storage used by map.
Private Attributes
int *	values
	array of values
HashTbl *	ht
	underlying hash table
SetPair *	kvx
	in-use and free key-val indexes

Detailed Description

Maintains set of (key, value) pairs where key is a 64 bit value and value is a positive 32 bit integer.

All keys must be distinct.

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

Each pair is also assigned an index that can be used for iterating through the pairs.

The implementation uses a 2-left hash table with eight items in each bucket. The number of pairs is limited to 2^20 - 1. This ensures ensures a maximum load factor of 50% x to minimize the potential for overloading any bucket.

Definition at line 35 of file HashMap.h.

Constructor & Destructor Documentation

grafalgo::HashMap::HashMap ( int n1 )

Constructor for HashMap, 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 HashMap.cpp.

Here is the call graph for this function:

grafalgo::HashMap::~HashMap ( )

Destructor for HashMap.

Definition at line 19 of file HashMap.cpp.

Here is the call graph for this function:

Member Function Documentation

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

Clear the hashtable contents.

Implements grafalgo::Adt.

Definition at line 64 of file HashMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashMap::copyFrom ( const HashMap & src )

Copy into map from src.

Definition at line 69 of file HashMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Expand the space available for this map.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 57 of file HashMap.cpp.

Here is the call graph for this function:

index grafalgo::HashMap::firstPair ( ) const [inline]

Get the index of the first (key,value) pair in the map.

Returns:: the index of the first pair; the order or pairs is arbitrary

Definition at line 70 of file HashMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Free dynamic storage used by map.

Definition at line 39 of file HashMap.cpp.

Here is the caller graph for this function:

int grafalgo::HashMap::get ( uint64_t key ) const [inline]

Retrieve value for a given key.

Parameters:

key	is the key of a pair in the map

Returns:: true on success, false on failure.

Definition at line 94 of file HashMap.h.

Here is the call graph for this function:

uint64_t grafalgo::HashMap::key ( index x ) const [inline]

Get the key of the (key,value) pair with a given index.

Parameters:

x	is the index of some pair in the map

Returns:: the key value part the pair with index x

Definition at line 82 of file HashMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashMap::makeSpace ( int size ) [private]

Allocate and initialize space for map.

Parameters:

size	is number of index values to provide space for

Definition at line 24 of file HashMap.cpp.

Here is the caller graph for this function:

index grafalgo::HashMap::nextPair ( index x ) const [inline]

Get the index of the next (key,value) pair in the map.

Parameters:

x	is the index of some pair in the map

Returns:: the index of the next pair; the order or pairs is arbitrary

Definition at line 76 of file HashMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::HashMap::put	(	uint64_t	key,
		int	value
	)		`[inline]`

Add a pair to the map.

Parameters:

key	is the key of the pair to be added/modified
value	is the value of the pair to be added/modified

Returns:: true on success, false on failure.

Definition at line 103 of file HashMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashMap::remove ( uint64_t key ) [inline]

Remove an element from the set.

Parameters:

key	is the key of the pair to be removed

Definition at line 115 of file HashMap.h.

Here is the call graph for this function:

void grafalgo::HashMap::resize ( int size ) [virtual]

Resize a HashMap object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 45 of file HashMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::HashMap::val ( index x ) const [inline]

Get the value of the (key,value) pair with a given index.

Parameters:

x	is the index of some pair in the map

Returns:: the value part of the pair with index x

Definition at line 88 of file HashMap.h.

Here is the caller graph for this function:

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

/Users/jst/src/grafalgo/cpp/include/HashMap.h
/Users/jst/src/grafalgo/cpp/dataStructures/hash/HashMap.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation