The Nebula Device 3: Util::HashTable< KEYTYPE, VALUETYPE > Class Template Reference

The Nebula Device 3

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)