HashTable- Hash Table
HashTable class provides a means of building simple hash
tables and performing hash searches.
hash_map()becomes available in the C++ Standard Template Library - it's already in the SGI STL -
HashTableshould be phased out.
The classic representation of hash tables is used for these hash tables. An
array of buckets is created by the
HashTable() constructor, sized
to the first prime number M that is larger than the expected maximum number of
elements in the table. Key-value pairs are then added to the table by the
Add() method. A character string key is "folded" into an integer
and divided by the prime number M to produce an index into the array of buckets;
the key-value pair is then stored in the indicated bucket. If multiple
key-value pairs map into the same bucket (AKA a collision), they are chained
together by a linked list attached to the bucket.
Building a hash table using these functions is very simple. First, create an empty hash table:
#include "HashTable.h" // Hash table definitions. #define NUM_ITEMS 500 ... HashTable table (NUM_ITEMS) ;
The argument to the
HashTable() constructor is the expected number
of items in the table; the table will handle more, albeit with slower lookup
Key-value pairs are added to the table with the
table.Add ("key", (void *) value) ;
Keys are null-terminated characters strings and values must be cast as
void * pointers. If the key is already in the table, its
old value is replaced with the new value.
Looking up the value of a key is done with the
void *value ; ... if (table.Find ("key", &value)) ... found ... else ... not found ...
The value is returned as a
void * pointer, which the caller must
then cast back to the original type.
Key-value pairs can be individually deleted from a hash table:
table.Delete ("key") ;
HashTable()- creates an empty hash table.
~HashTable()- destroys a hash table.
Add()- adds a key-data item to the table.
Delete()- deletes a key-data item from the table.
Find()- looks up a key in the table.
HashOf()- computes the hash of a key.
PrimeAbove()- computes the first prime above a number.