Util::HashTable< KEYTYPE, VALUETYPE > Class Template Reference

#include <hashtable.h>

---

Detailed Description

template<class KEYTYPE, class VALUETYPE>
class Util::HashTable< KEYTYPE, VALUETYPE >

Organizes key/value pairs by a hash code. Looks very similar to a Dictionary, but may provide better search times (up to O(1)) by computing a (ideally unique) hash code on the key and using that as an index into an array. The flipside is that the key class must provide a hash code and the memory footprint may be larger then Dictionary.

The default capacity is 128. Matching the capacity against the number of expected elements in the hash table is one key to get optimal insertion and search times, the other is to provide a good (and fast) hash code computation which produces as few collissions as possible for the key type.

The key class must implement the following method in order to work with the HashTable: IndexT HashCode() const;

The Util::String class implements this method as an example. Internally the hash table is implemented as a fixed array of sorted arrays. The fixed array is indexed by the hash code of the key, the sorted arrays contain all values with identical keys.

(C) 2006 Radon Labs GmbH

Public Member Functions
	HashTable ()
	default constructor
	HashTable (SizeT capacity)
	constructor with capacity
	HashTable (const HashTable< KEYTYPE, VALUETYPE > &rhs)
	copy constructor
void	operator= (const HashTable< KEYTYPE, VALUETYPE > &rhs)
	assignment operator
VALUETYPE &	operator[] (const KEYTYPE &key) const
	read/write [] operator, assertion if key not found
SizeT	Size () const
	return current number of values in the hashtable
SizeT	Capacity () const
	return fixed-size capacity of the hash table
void	Clear ()
	clear the hashtable
bool	IsEmpty () const
	return true if empty
void	Add (const KeyValuePair< KEYTYPE, VALUETYPE > &kvp)
	add a key/value pair object to the hash table
void	Add (const KEYTYPE &key, const VALUETYPE &value)
	add a key and associated value
void	Erase (const KEYTYPE &key)
	erase an entry
bool	Contains (const KEYTYPE &key) const
	return true if key exists in the array
Array< KeyValuePair< KEYTYPE, VALUETYPE > >	Content () const
	return array of all key/value pairs in the table (slow)