VIPER REFERENCE MANUAL


NAME
iflHashTable - base class from which hash table implementations may be derived

HEADER FILE
#include <ifl/iflHashTable.h>

PUBLIC METHOD SUMMARY

   Creating and destroying
iflHashTable ( int maxEntries=0);
virtual ~iflHashTable (  );

   Manipulating
void clear (  );
int insert ( iflHashElem* elem);
int remove ( iflHashElem* elem);

   Query
iflHashElem* find ( unsigned int index, const void* key);
iflHashElem* next ( int& index);
int getNumEntries (  ) const;

   Tuning
float getFullFraction (  ) const;
void setFullFraction ( const float fraction);
void clearStats (  );

PUBLIC MEMBER SUMMARY

   Performance Statistics
int lookCount;
int totalLook;
int maxLook;

PROTECTED METHOD SUMMARY

   Key matching
virtual int match ( const void* key, const iflHashElem* elem);

CLASS DESCRIPTION
This class implements an abstract hash-based lookup table. To create a hash table, a derived class must be defined that specifies the pure virtual match() method. In addition, a hash function must be defined and used to fill in the hashIndex field of any hash table elements (derived from iflHashElem) that are to be inserted into the table. The match() method is then used to compare elements when a collision occurs on the hashIndex field.

The hash function used to map a hash element to its hash index must be carefully chosed to minimize collisions (different elements mapping to the same index) to get the best performance from the hash table.

METHOD DESCRIPTIONS

   iflHashTable()
iflHashTable ( int maxEntries=0);

Creates an empty iflHashTable, with initial size large enough to hold maxEntries; the default value of zero will create a table with 131 slots. By default the hash table will automatically grow when it gets more than half full. See setFullFraction() for more details.

   ~iflHashTable()
virtual ~iflHashTable (  );

Frees the memory associated with the hash table itself. The items in the hash table are not freed.

   clear()
void clear (  );

Removes all elements currently in the hash table.

   clearStats()
void clearStats (  );

Resets the lookCount, totalLook, and maxLook member variables to zero.

   find()
iflHashElem* find ( unsigned int index, const void* key);

Finds the element with hash index, index, and key value, key.

   getFullFraction()
float getFullFraction (  ) const;

Returns the current fraction of the table, which when filled will cause the hash table to be expanded. The default value is .5 (50%).

   getNumEntries()
int getNumEntries (  ) const;

Returns the number of entries currently in the hash table.

   insert()
int insert ( iflHashElem* elem);

Inserts the hash element, elem, into the hash table. The hashIndex field must already be filled in.

   match()
virtual int match ( const void* key, const iflHashElem* elem);

This function is used to compare an element key, key, with the key of another element, elem. This function must be defined in any class derived from iflHashTable.

   next()
iflHashElem* next ( int& index);

This function is used to iterate through the filled entries of a hash table. To start iterating, index should be initiliazed to zero. The index should not be altered on subsequent calls, as iflHashTable uses it to keep track of where it is in the table. The returned value is a pointer to the next hash element in the table, or NULL, when there are no more entries left to iterate on in the table.

   remove()
int remove ( iflHashElem* elem);

This function is used to remove the hash table element, elem, from the table.

   setFullFraction()
void setFullFraction ( const float fraction);

Sets the current fraction of the table, which when filled will cause the hash table to be expanded. The default value is .5 (50%). If fraction is 1, the hash table will not grow, and insert() will fail when the table is full.

MEMBER DESCRIPTIONS

   lookCount
int lookCount;

This member holds a running total of the number of lookups (calls to find()).

   maxLook
int maxLook;

This member holds the maximum number of rehashes ever required by a single lookup.

   
totalLook
int totalLook;

This member holds the number of hashes and rehashes accumulated over all lookups.

SEE ALSO
iflHashElem