Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

HashMap Class Template Reference

#include <HashMap.h>

Inheritance diagram for HashMap:

IntKeyHashMap StringKeyHashMap ICStringKeyHashMap List of all members.

Detailed Description

template<class VALUETYPE>
class toolbox::HashMap< VALUETYPE >

A hash table stores any kind of object with nearly constant save/lookup time, but with consuming a lot more memory than an array.

It uses a hash function to distribute all search keys over an array of buckets, and the same hash function to look them up again. Keys may be evaluating to the same bucket. In this case, they are both put into it. If the number of keys gets too high, a larger number of buckets is used, and all keys are distributed again.

See also:
See collections.txt for an overview of the available collection classes.
Author:
Thomas Jacob

Definition at line 48 of file HashMap.h.

Public Member Functions

bool ContainsKey (void *key) const
 Returns, if the hash table contains a given key.

void Delete (void *key)
 Removes a key/value pair from the hash table.

void DeleteAll ()
 Removes all key/value pairs from the hash table.

VALUETYPE * Get (void *key) const
 Returns the value of a key/value pair by its key.

long GetCount () const
 Returns the number of set keys.

int GetDesiredFillRatio () const
 Returns the fill ratio after a hash table resize.

int GetFillRatio () const
 Returns the current fill ratio.

PointeredListGetKeys () const
 Returns a new PointeredList of all keys currently in the hash table.

long GetSize () const
 Returns the number of buckets currently used.

PointeredListGetValues () const
 Returns a new PointeredList of all values currently in the hash table.

 HashMap (long initSize, int desiredFillRatio)
 Creates a new hash table with customized settings.

 HashMap (long initSize)
 Creates a new hash table with an initial size.

 HashMap ()
 Creates a new hash table.

bool IsEmpty () const
 Returns whether there are no elements in the hash table.

void Set (void *key, VALUETYPE *Value)
 Sets a key/value pair into the hash table.

VALUETYPE * Unset (void *key)
 Removes a key/value pair from the hash table.

void UnsetAll ()
 Removes all key/value pairs from the hash table.

virtual ~HashMap ()
 Destroys the hash table.


Protected Member Functions

virtual void * CreateKey (void *key) const
 Creates the key object that shall be stored in the key buckets.

virtual void DestroyKey (void *key) const
 Disposes a key created by the CreateKey method.

virtual bool Equals (void *key1, void *key2) const
 Checks, if to keys equal each other.

virtual unsigned long HashCode (void *key) const
 Returns the hash code of the key.


Protected Attributes

PointeredList ** KeyBuckets
 The array of key buckets.

long Size
 The number of buckets currently used.

PointeredList ** ValueBuckets
 The array of value buckets.


Private Member Functions

void CheckSize ()
 Checks, whether the hash table has to be resized, and resizes it if necessary.

void Init (long initSize, int desiredFillRatio)
 Initializes the hash table.

void Rehash (long newSize)
 Resizes and rehashes the hash table.

void SetWithoutSizeChecking (void *key, VALUETYPE *Value)
 Sets a key/value pair into the hash table without checking the hash table size afterwards.


Private Attributes

long Count
 The number of used hash table cells.

int DesiredFillRatio
 The fill ratio after a hash table resize.

long InitSize
 The minimum and initial size of the hash table.


Constructor & Destructor Documentation

HashMap  ) 
 

Creates a new hash table.

HashMap long  initSize  ) 
 

Creates a new hash table with an initial size.

Parameters:
initSize The minimum and initial size of the hash table. This is the minimum and initial number of buckets.

HashMap long  initSize,
int  desiredFillRatio
 

Creates a new hash table with customized settings.

Parameters:
initSize The minimum and initial size of the hash table. This is the minimum and initial number of buckets.
desiredFillRatio The fill ratio after a hash table resize. This happens, if the fill ratio gets higher than one and a half times the fill ratio or lower than half the fill ratio. The rest of the buckets is reserved for further setting of keys.

virtual ~HashMap  )  [virtual]
 

Destroys the hash table.

The memory of the keys is not freed, since it was not acquired, but the memory of the values is freed.


Member Function Documentation

void CheckSize  )  [private]
 

Checks, whether the hash table has to be resized, and resizes it if necessary.

bool ContainsKey void *  key  )  const
 

Returns, if the hash table contains a given key.

Parameters:
key The key to be looked up. Note that NULL is a valid value among all possible values for keys.
Returns:
if the hash table contains the key.

virtual void* CreateKey void *  key  )  const [protected, virtual]
 

Creates the key object that shall be stored in the key buckets.

The method receives a key and e.g. creates a clone, or uses the key directly, if this is possible. The Equals and HashCode method must return the same values when using the original key and the one returned by this method. The DestroyKey method disposes this key again. In the HashMap class, the key is returned directly.

Parameters:
key The original key provided by the user of this class. Note that NULL is a valid value among all possible values for keys.
Returns:
The key to be used by the key buckets.
Note:
Override this method to implement your own key memory management (for strings etc.).

Reimplemented in StringKeyHashMap, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, and StringKeyHashMap< ConfigParameter >.

void Delete void *  key  ) 
 

Removes a key/value pair from the hash table.

The memory of the key is not freed, since it was not acquired, but the memory of the value is freed.

Parameters:
key The key to be looked up for deletion. Note that NULL is a valid value among all possible values for keys.

void DeleteAll  ) 
 

Removes all key/value pairs from the hash table.

The memory of the keys is not freed, since it was not acquired, but the memory of the values is freed.

virtual void DestroyKey void *  key  )  const [protected, virtual]
 

Disposes a key created by the CreateKey method.

This can be done by freeing the memory, if the key was cloned, or by simply doing nothing, if the user's key was directly used. This method should do the opposite of the CreateKey method. In the HashMap class, this method does nothing, since the key was directly used.

Parameters:
key The key created by the CreateKey method. Note that NULL is a valid value among all possible values for keys.
Note:
Override this method to implement your own key memory management (for strings etc.).

Reimplemented in StringKeyHashMap, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, and StringKeyHashMap< ConfigParameter >.

virtual bool Equals void *  key1,
void *  key2
const [protected, virtual]
 

Checks, if to keys equal each other.

In the HashMap class, this is true, if they point to the same memory.

Parameters:
key1 The first key.
key2 The second key.
Returns:
If both keys equal each other.
Note:
Override this method to implement your own key memory comparison method (for strings etc.).

Reimplemented in StringKeyHashMap, ICStringKeyHashMap, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, StringKeyHashMap< ConfigParameter >, and ICStringKeyHashMap< Void >.

VALUETYPE* Get void *  key  )  const
 

Returns the value of a key/value pair by its key.

Parameters:
key The key to be looked up. Note that NULL is a valid value among all possible values for keys.
Returns:
The value to key, or NULL, if the key cannot be found or its value was NULL.

long GetCount  )  const [inline]
 

Returns the number of set keys.

Returns:
The number of set keys.

Reimplemented in HashSet.

int GetDesiredFillRatio  )  const [inline]
 

Returns the fill ratio after a hash table resize.

Returns:
The fill ratio after a hash table resize.

int GetFillRatio  )  const [inline]
 

Returns the current fill ratio.

This is the ratio between the used hash table cells (Count), and the reserved cells (Size).

Returns:
The current fill ratio.

PointeredList* GetKeys  )  const
 

Returns a new PointeredList of all keys currently in the hash table.

Returns:
The keys as a PointeredList.
Warning:
This method creates a PointeredList and expects that it is deleted by the caller.

long GetSize  )  const [inline]
 

Returns the number of buckets currently used.

Returns:
The number of buckets currently used.
See also:
GetCount()

PointeredList* GetValues  )  const
 

Returns a new PointeredList of all values currently in the hash table.

Returns:
The values as a PointeredList.
Warning:
This method creates a PointeredList and expects that it is deleted by the caller.

virtual unsigned long HashCode void *  key  )  const [protected, virtual]
 

Returns the hash code of the key.

This is a value that has to be constant for the same key all the time, needs not to be injective, and should distribute the keys quite good.

Parameters:
key The key to determine the hash code of. Note that NULL is a valid value among all possible values for keys.
Returns:
The key's hash code.
Note:
Override this method to implement your own key's hash code.

Reimplemented in IntKeyHashMap, StringKeyHashMap, ICStringKeyHashMap, IntKeyHashMap< Void >, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, StringKeyHashMap< ConfigParameter >, and ICStringKeyHashMap< Void >.

void Init long  initSize,
int  desiredFillRatio
[private]
 

Initializes the hash table.

Parameters:
initSize The initial size of the hash table.
desiredFillRatio The desired fill ratio.

bool IsEmpty  )  const [inline]
 

Returns whether there are no elements in the hash table.

Returns:
Whether there are no elements in the hash table.

Reimplemented in HashSet.

void Rehash long  newSize  )  [private]
 

Resizes and rehashes the hash table.

Parameters:
newSize The new hash table size.

void Set void *  key,
VALUETYPE *  Value
 

Sets a key/value pair into the hash table.

Afterwards, the method checks if the hash table has to be resized. If the key existed, the old value is replaced, and its memory is freed.

Parameters:
key The key to be set. Since the memory of the key is not freed after unsetting the key or deleting the hash table, the memory management is still yours after the call. Note that NULL is a valid value among all possible values for keys.
Value The value to be set. The memory of the value is freed when deleting the key or hash table, and is not freed when unsetting the key. A NULL value is valid. Its key is set anyway. Use Unset to remove the key, too.

void SetWithoutSizeChecking void *  key,
VALUETYPE *  Value
[private]
 

Sets a key/value pair into the hash table without checking the hash table size afterwards.

This is required during the rehashing and setting. If the key already exists, it is destroyed and the old value is replaced by the new one.

Parameters:
key The key to be set. This must be a key that is already transformed by the CreateKey method. Note that NULL is a valid value among all possible values for keys.
Value The value to be set.

VALUETYPE* Unset void *  key  ) 
 

Removes a key/value pair from the hash table.

Afterwards, the method checks if the hash table has to be resized. Both the memory of the key and the memory of the value are not freed, but the value is returned.

Parameters:
key The key to be looked up for removal. Note that NULL is a valid value among all possible values for keys.
Returns:
The value that was stored at the key before.

void UnsetAll  ) 
 

Removes all key/value pairs from the hash table.

Afterwards, the method checks if the hash table has to be resized. Both the memory of the keys and the memory of the values are not freed.

Warning:
No value is freed, so you have to have a pointer to the objects, or the memory is lost.


Member Data Documentation

long Count [private]
 

The number of used hash table cells.

This is the number of set keys.

Definition at line 56 of file HashMap.h.

int DesiredFillRatio [private]
 

The fill ratio after a hash table resize.

This happens, if the fill ratio gets higher than one and a half times the fill ratio or lower than half the fill ratio. The rest of the buckets is reserved for further setting of keys.

Definition at line 66 of file HashMap.h.

long InitSize [private]
 

The minimum and initial size of the hash table.

This is the minimum and initial number of buckets.

Definition at line 72 of file HashMap.h.

PointeredList** KeyBuckets [protected]
 

The array of key buckets.

Definition at line 118 of file HashMap.h.

long Size [protected]
 

The number of buckets currently used.

See also:
Count

Definition at line 124 of file HashMap.h.

PointeredList** ValueBuckets [protected]
 

The array of value buckets.

Definition at line 129 of file HashMap.h.


The documentation for this class was generated from the following file:
Generated on Tue Oct 3 00:23:40 2006 for ToolBox by doxygen 1.3.6