HashTable - Hash Table

The HashTable class provides a means of building simple hash tables and performing hash searches.

Note: Once hash_map() becomes available in the C++ Standard Template Library - it's already in the SGI STL - HashTable should 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 times.

Key-value pairs are added to the table with the Add() method:

    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 Find() method:

    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") ;

Public Methods

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.

Private Methods

HashOf() - computes the hash of a key.

PrimeAbove() - computes the first prime above a number.

Source Files

HashTable.cpp

HashTable.h