`hash_util` - Hash Search Utilities

The HASH_UTIL package provides a means of building hash tables and performing hash searches.

The classic representation of hash tables is used for these hash tables. An array of buckets is created by hashCreate(), 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 hashAdd(). 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 (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  "hash_util.h"		-- Hash table definitions.
    #define  NUM_ITEMS  500
    HashTable  table ;
    ...
    hashCreate (NUM_ITEMS, 0, &table) ;

The first argument to hashCreate() 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 hashAdd():

    hashAdd (table, "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 hashSearch():

    void  *value ;
    ...
    if (hashSearch (table, "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.

The keys in a hash table can be retrieved by index:

    char  *key ;
    int  i ;
    void  *value ;
    ...
    for (i = 0 ;  i < hashCount (table) ;  i++) {
        key = hashGet (table, i) ;
        value = hashFind (table, key) ;
        printf ("%s = %p\n", key, value) ;
    }

Key-value pairs can be individually deleted from a hash table:

    hashDelete (table, "key") ;

or the entire table can be destroyed:

    hashDestroy (table) ;

The HASH_UTIL group of hash table functions offer several advantages over the Standard C Library hashing functions (hcreate(3), hdestroy(3), and hsearch(3)). First, the HASH_UTIL functions are easier to use: the multi-purpose functionality of hsearch(3) is broken up into hashAdd() and hashSearch(), etc. Second, the HASH_UTIL functions allow for more than one hash table in a program.