HashTable< Key, Value > Class Template Reference

#include <tDictionary.h>

Inheritance diagram for HashTable< Key, Value >:

Inheritance graph
[legend]
List of all members.

Detailed Description


template<typename Key, typename Value> class HashTable< Key, Value >

A HashTable template class.

The hash table class maps between a key and an associated value. Access using the key is performed using a hash table. The class provides methods for both unique and equal keys. The global hash(Type) function is used for hashing, see util/hash.h


Public Types

typedef Pair ValueType
typedef PairReference
typedef const PairConstReference
typedef _Iterator< Pair, Node,
HashTable
Iterator
typedef _Iterator< const Pair,
const Node, const HashTable
ConstIterator
typedef S32 DifferenceType
typedef U32 SizeType

Public Member Functions

 HashTable ()
 ~HashTable ()
 HashTable (const HashTable &p)
U32 size () const
 Return the number of elements.
U32 tableSize () const
 Return the size of the hash bucket table.
void clear ()
 Empty the HashTable.
void resize (U32 size)
 Resize the bucket table for an estimated number of elements.
bool isEmpty () const
 Returns true if the table is empty.
F32 collisions () const
 Returns the average number of nodes per bucket.
Iterator insertEqual (const Key &key, const Value &)
 Insert the key value pair and allow duplicates.
Iterator insertUnique (const Key &key, const Value &)
 Insert the key value pair but don't insert duplicates.
void erase (Iterator)
 Erase the given entry.
void erase (const Key &key)
 Erase all matching keys from the table.
void erase (const Key &key, const Value &value)
 Erase entry for this key-value pair.
Iterator findOrInsert (const Key &key)
 Find the key, or insert a one if it doesn't exist.
Iterator find (const Key &)
 Find the first entry for the given key.
ConstIterator find (const Key &) const
 Find the first entry for the given key.
bool find (const Key &key, Value &value)
 Find the first entry for the given key.
S32 count (const Key &)
 Count the number of matching keys in the table.
Iterator begin ()
 Iterator to first element.
ConstIterator begin () const
 Iterator to first element.
Iterator end ()
 Iterator to last element + 1.
ConstIterator end () const
 Iterator to last element + 1.
void operator= (const HashTable &p)

Private Member Functions

U32 _hash (const Key &key) const
U32 _index (const Key &key) const
Node_next (U32 index) const
void _resize (U32 size)
void _destroy ()

Private Attributes

Node ** mTable
 Hash table.
S32 mTableSize
 Hash table size.
U32 mSize
 Number of keys in the table.

Classes

class  _Iterator
struct  Node
struct  Pair


Member Typedef Documentation

template<typename Key, typename Value>
typedef Pair HashTable< Key, Value >::ValueType

template<typename Key, typename Value>
typedef Pair& HashTable< Key, Value >::Reference

template<typename Key, typename Value>
typedef const Pair& HashTable< Key, Value >::ConstReference

template<typename Key, typename Value>
typedef _Iterator<Pair,Node,HashTable> HashTable< Key, Value >::Iterator

template<typename Key, typename Value>
typedef _Iterator<const Pair,const Node,const HashTable> HashTable< Key, Value >::ConstIterator

template<typename Key, typename Value>
typedef S32 HashTable< Key, Value >::DifferenceType

template<typename Key, typename Value>
typedef U32 HashTable< Key, Value >::SizeType


Constructor & Destructor Documentation

template<typename Key, typename Value>
HashTable< Key, Value >::HashTable (  ) 

template<typename Key, typename Value>
HashTable< Key, Value >::~HashTable (  ) 

template<typename Key, typename Value>
HashTable< Key, Value >::HashTable ( const HashTable< Key, Value > &  p  ) 


Member Function Documentation

template<typename Key, typename Value>
U32 HashTable< Key, Value >::_hash ( const Key &  key  )  const [inline, private]

template<typename Key, typename Value>
U32 HashTable< Key, Value >::_index ( const Key &  key  )  const [inline, private]

template<typename Key, typename Value>
HashTable< Key, Value >::Node * HashTable< Key, Value >::_next ( U32  index  )  const [private]

template<typename Key, typename Value>
void HashTable< Key, Value >::_resize ( U32  size  )  [private]

template<typename Key, typename Value>
void HashTable< Key, Value >::_destroy (  )  [private]

template<typename Key, typename Value>
U32 HashTable< Key, Value >::size (  )  const [inline]

template<typename Key, typename Value>
U32 HashTable< Key, Value >::tableSize (  )  const [inline]

Return the size of the hash bucket table.

template<typename Key, typename Value>
void HashTable< Key, Value >::clear (  )  [inline]

template<typename Key, typename Value>
void HashTable< Key, Value >::resize ( U32  size  )  [inline]

Resize the bucket table for an estimated number of elements.

This method will optimize the hash bucket table size to hold the given number of elements. The size argument is a hint, and will not be the exact size of the table. If the table is sized down below it's optimal size, the next insert will cause it to be resized again. Normally this function is used to avoid resizes when the number of elements that will be inserted is known in advance.

template<typename Key, typename Value>
bool HashTable< Key, Value >::isEmpty (  )  const [inline]

Returns true if the table is empty.

Reimplemented in Map< String, unsigned int >, and Map< GFXShader *, BasicLightManager::LightingShaderConstants >.

template<typename Key, typename Value>
F32 HashTable< Key, Value >::collisions (  )  const [inline]

Returns the average number of nodes per bucket.

template<typename Key, typename Value>
HashTable< Key, Value >::Iterator HashTable< Key, Value >::insertEqual ( const Key &  key,
const Value &  x 
)

Insert the key value pair and allow duplicates.

This insert method allows duplicate keys. Keys are grouped together but are not sorted.

template<typename Key, typename Value>
HashTable< Key, Value >::Iterator HashTable< Key, Value >::insertUnique ( const Key &  key,
const Value &  x 
)

Insert the key value pair but don't insert duplicates.

This insert method does not insert duplicate keys. If the key already exists in the table the function will fail and end() is returned.

template<typename Key, typename Value>
void HashTable< Key, Value >::erase ( Iterator   ) 

Erase the given entry.

template<typename Key, typename Value>
void HashTable< Key, Value >::erase ( const Key &  key  ) 

Erase all matching keys from the table.

template<typename Key, typename Value>
void HashTable< Key, Value >::erase ( const Key &  key,
const Value &  value 
)

Erase entry for this key-value pair.

template<typename Key, typename Value>
HashTable< Key, Value >::Iterator HashTable< Key, Value >::findOrInsert ( const Key &  key  ) 

Find the key, or insert a one if it doesn't exist.

Returns the first key in the table that matches, or inserts one if there are none.

template<typename Key, typename Value>
HashTable< Key, Value >::Iterator HashTable< Key, Value >::find ( const Key &   ) 

Find the first entry for the given key.

template<typename Key, typename Value>
HashTable< Key, Value >::ConstIterator HashTable< Key, Value >::find ( const Key &   )  const

Find the first entry for the given key.

template<typename Key, typename Value>
bool HashTable< Key, Value >::find ( const Key &  key,
Value &  value 
)

Find the first entry for the given key.

template<typename Key, typename Value>
S32 HashTable< Key, Value >::count ( const Key &   ) 

Count the number of matching keys in the table.

template<typename Key, typename Value>
HashTable< Key, Value >::Iterator HashTable< Key, Value >::begin (  )  [inline]

template<typename Key, typename Value>
HashTable< Key, Value >::ConstIterator HashTable< Key, Value >::begin (  )  const [inline]

template<typename Key, typename Value>
HashTable< Key, Value >::Iterator HashTable< Key, Value >::end (  )  [inline]

template<typename Key, typename Value>
HashTable< Key, Value >::ConstIterator HashTable< Key, Value >::end (  )  const [inline]

template<typename Key, typename Value>
void HashTable< Key, Value >::operator= ( const HashTable< Key, Value > &  p  ) 


Member Data Documentation

template<typename Key, typename Value>
Node** HashTable< Key, Value >::mTable [private]

Hash table.

template<typename Key, typename Value>
S32 HashTable< Key, Value >::mTableSize [private]

Hash table size.

template<typename Key, typename Value>
U32 HashTable< Key, Value >::mSize [private]

Number of keys in the table.