ULHashTable< K, V > Class Template Reference

A simple implementation of a hash table. More...

#include <ulcontainers.h>

Public Member Functions
	ULHashTable ()
	ULHashTable (uluint32 tableSize)
	~ULHashTable ()
void	clear ()
ULHashTable< K, V > &	operator= (const ULHashTable< K, V > &table)
uluint32	getTableSize () const
uluint32	getKeyCount () const
bool	resize (uluint32 tableSize)
void	add (const K &key, const V &value)
void	add (const ULPair< K, V > &keyValuePair)
bool	find (const K &key, V &value) const
bool	find (const K &key) const
ULHashTableIterator< K, V >	end () const
ULHashTableIterator< K, V >	begin () const
void	getStats (double &avgListLength, uluint32 &maxListLength)

Friends
class	ULHashTableIterator< K, V >

Detailed Description

template<class K, class V>
class ULHashTable< K, V >

A simple implementation of a hash table.

Types used as the template parameter K must have a method with signature uluint32 hash(uluint32 tableSize) that returns a hash value between 0 and tableSize - 1.

Each of the slots in this hash table consists of a ULList of (key, value) pairs. That is, the table uses chaining to resolve collisions.

Constructor & Destructor Documentation

template<class K , class V >

ULHashTable< K, V >::ULHashTable

(

)

Default constructor. Sets the table size to zero. Do not try to use a ULHashTable whose table size is 0. Make sure to call resize with a non-zero parameter first.

template<class K , class V >

ULHashTable< K, V >::ULHashTable

(

uluint32

initialTableSize

)

Constructor.

Parameters

[in]

initialTableSize

The desired table size.

template<class K , class V >

ULHashTable< K, V >::~ULHashTable

(

)

Destructor.

Member Function Documentation

template<class K, class V>

void ULHashTable< K, V >::add	(	const K &	key,
		const V &	value
	)

Adds the specified (key, value) pair to this hash table.

Parameters

[in]	key	The key.
[in]	value	The value to associate with the key.

template<class K, class V>

void ULHashTable< K, V >::add

(

const ULPair< K, V > &

keyValuePair

)

Adds a (key, value) pair to this hash table if the specified key is not already present. If the key is already in the table, this method changes its associated value.

Parameters

[in]	key	The key.
[in]	value	The value to associate with the key.

template<class K , class V >

ULHashTableIterator< K, V > ULHashTable< K, V >::begin

(

)

const

Returns

an iterator pointing to the first (key, value) pair stored in this hash table.

template<class K , class V >

void ULHashTable< K, V >::clear

(

)

Removes all items from the hash table, leaving the table the same size as before, but empty.

template<class K , class V >

ULHashTableIterator< K, V > ULHashTable< K, V >::end

(

)

const

Returns

an iterator pointing to the end of the sequence of (key, value) pairs stored in this hash table. The "end" of this sequence is not a (key, value) pair–it's a spot just beyond the final pair in the sequence. Note that an iterator for which isAtEnd returns true must not be dereferenced using operator*.

template<class K, class V>

bool ULHashTable< K, V >::find	(	const K &	key,
		V &	value
	)		const

Searches this table for the value associated with the specified key.

Returns

true if the specified key is in this table.

Parameters

[in]	key	The key.
[out]	value	The value corresponding to the key (if the key is in this table). value is unchanged if the key is not found.

template<class K, class V>

bool ULHashTable< K, V >::find

(

const K &

key

)

const

Returns

true if the specified key is in this hash table.

template<class K , class V >

uluint32 ULHashTable< K, V >::getKeyCount

(

)

const

Returns

the number of (key, value) pairs in this hash table.

template<class K , class V >

void ULHashTable< K, V >::getStats	(	double &	avgChainLength,
		uluint32 &	maxChainLength
	)

Used for program tuning, this function reports statistics about the distribution of keys in this hash table.

Parameters

[out]	avgChainLength	This gets the mean length of the non-empty chains in this hash table.
[out]	maxChainLength	This gets the longest chain length in this table.

template<class K , class V >

uluint32 ULHashTable< K, V >::getTableSize

(

)

const

Returns

the number of slots in this hash table (not the number of (key, value) pairs).

template<class K, class V>

ULHashTable< K, V > & ULHashTable< K, V >::operator=

(

const ULHashTable< K, V > &

otherTable

)

Assignment operator. Note that this makes a complete new copy of the hash table, so it's not normally a good idea to invoke this function.

template<class K , class V >

bool ULHashTable< K, V >::resize

(

uluint32

tableSize

)

Changes the size of this hash table. After the new table is allocated, the (key, value) pairs in the old table are rehashed for insertion into the new table.

Returns

true if the resizing is successful.

Parameters

[in]

tableSize

The desired new table size.

Friends And Related Function Documentation

template<class K, class V>

friend class ULHashTableIterator< K, V >

friend

---

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

• ulcontainers.h