NAME

Hash − overview of routines to manipulate hash tables
 

The Hash_ routines provide mechanisms for manipulating hash tables.  A hash table is a data structure that stores any number of entries, each of which is a <key, value> pair.  Given the key for a particular entry, the Hash_ routines can very quickly find the entry (and hence the associated value).  There can be at most one entry with a given key in a hash table at a time, but many entries may have the same value. 

This library provides two unusual features.  First, hash tables can grow gracefully.  In most hash table implementations the  number of buckets in the table is fixed;  if the number of entries in the table becomes substantially larger than the number of buckets, the performance of the table degrades.  In contrast, this implementation automatically re-allocates the bucket memory as the table grows.  As a result, hash tables can become arbitrarily large without overloading the buckets.  An initial number of buckets may be provided when tables are initialized, but it will change later (automatically) if necessary to guarantee efficient operation. 

The second unusual feature of the Hash_ routines is that they allow keys to be expressed in several forms.  Keys may either be variable-length NULL-terminated strings, or single-word values, or multi-word records of any length (in the latter case, all keys in the table must be the same length).  See Hash_InitTable for deatils on the different key types. 

Hash tables are initialized by calling Hash_InitTable.  New entries are added with Hash_CreateEntry, and existing entries may be located with either Hash_CreateEntry or Hash_FindEntry.  The values stored in entries are manipulated with Hash_GetValue and Hash_SetValue (values may be arbitrary one-word values; they are stored in entries and retrieved from them using the type “ClientData”).  An entry can be deleted from the table by calling Hash_DeleteEntry;  the entire table can be released by calling Hash_DeleteTable.  Hash_EnumFirst and Hash_EnumNext provide a facility for stepping through all the entries in a table.  Finally, Hash_PrintStats can be invoked to print out some usage information about a hash table. 
 

KEYWORDS

hash table, key, value

Sprite version 1.0  —  December 30, 1988