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

HashSet Class Reference

#include <HashSet.h>

Inheritance diagram for HashSet:

HashMap< Void > List of all members.

Detailed Description

A hash set stores any kind of object with nearly constant save/lookup time, but with consuming about 20 times the memory of an array.

The main and only difference to the hashtable is that it stores the keys only, not representing a key/value, but a 'key exist?' lookup.

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

Definition at line 26 of file HashSet.h.

Public Member Functions

void Add (void *key)
 Adds a key to the hash set.

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

PointeredListGetAll () const
 Returns a new PointeredList of all keys currently in the hash set.

long GetCount () const
 Returns the number of added elements.

 HashSet (long initSize, int desiredFillRatio)
 Creates a new hash set with customized settings.

 HashSet (long initSize)
 Creates a new hash set with an initial size.

 HashSet ()
 Creates a new hash set.

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

void Remove (void *key)
 Removes a key from the hash set.

void RemoveAll ()
 Removes all keys from the hash set.

virtual ~HashSet ()
 Destroys the hash set.


Protected Member Functions

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

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

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

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

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.

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

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.

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

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

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

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


Protected Attributes

PointeredList ** KeyBuckets
 The array of key buckets.

long Size
 The number of buckets currently used.

PointeredList ** ValueBuckets
 The array of value buckets.


Constructor & Destructor Documentation

HashSet  ) 
 

Creates a new hash set.

HashSet long  initSize  ) 
 

Creates a new hash set with an initial size.

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

HashSet long  initSize,
int  desiredFillRatio
 

Creates a new hash set with customized settings.

Parameters:
initSize The minimum and initial size of the hashtable. This is the minimum and initial number of buckets.
desiredFillRatio The fill ratio after a hashtable 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 ~HashSet  )  [virtual]
 

Destroys the hash set.

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


Member Function Documentation

void Add void *  key  )  [inline]
 

Adds a key to the hash set.

Afterwards, the method checks if the hash set has to be resized.

Parameters:
key The key to be set. Since the memory of the key is not freed after unsetting the key or deleting the hash set, the memory management is still yours after the call. Note that NULL is a valid value among all possible values for keys.

bool Contains void *  key  )  const [inline]
 

Returns, if the hash set 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 set contains the key.

bool ContainsKey void *  key  )  const [inherited]
 

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, inherited]
 

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< Void >.

void Delete void *  key  )  [inherited]
 

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  )  [inherited]
 

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, inherited]
 

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< Void >.

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

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< Void >, and ICStringKeyHashMap< Void >.

Void * Get void *  key  )  const [inherited]
 

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.

PointeredList* GetAll  )  const [inline]
 

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

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

long GetCount  )  const [inline]
 

Returns the number of added elements.

Returns:
The number of added elements.

Reimplemented from HashMap< Void >.

int GetDesiredFillRatio  )  const [inline, inherited]
 

Returns the fill ratio after a hash table resize.

Returns:
The fill ratio after a hash table resize.

int GetFillRatio  )  const [inline, inherited]
 

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 [inherited]
 

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, inherited]
 

Returns the number of buckets currently used.

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

PointeredList* GetValues  )  const [inherited]
 

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, inherited]
 

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< Void >, StringKeyHashMap< Void >, and ICStringKeyHashMap< Void >.

bool IsEmpty  )  const [inline]
 

Returns whether there are no elements in the hash set.

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

Reimplemented from HashMap< Void >.

void Remove void *  key  )  [inline]
 

Removes a key from the hash set.

Afterwards, the method checks if the hash set has to be resized. The memory of the key is not freed.

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

void RemoveAll  )  [inline]
 

Removes all keys from the hash set.

Afterwards, the method checks if the hash set has to be resized. The memory of the key is not freed.

void Set void *  key,
Void Value
[inherited]
 

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 * Unset void *  key  )  [inherited]
 

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  )  [inherited]
 

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

PointeredList** KeyBuckets [protected, inherited]
 

The array of key buckets.

Definition at line 118 of file HashMap.h.

long Size [protected, inherited]
 

The number of buckets currently used.

See also:
Count

Definition at line 124 of file HashMap.h.

PointeredList** ValueBuckets [protected, inherited]
 

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