Mastering Algorithms with C

Implementation and Analysisof Open Addressed Hash Tables

An open-addressed hash table fundamentally consists of a single array. The structure OHTbl is the open-addressed hash table data structure (see Example 8.6). This structure consists of eight members: positions is the number of positions allocated in the hash table; vacated is a pointer that will be initialized to a special storage location to indicate that a particular position in the table has had an element removed from it; h1, h2, match, and destroy are members used to encapsulate the functions passed to ohtbl_init ; size is the number of elements currently in the table; and table is the array in which the elements are stored.

The vacated member requires a bit of discussion. Its purpose is to support the removal of elements. An unoccupied position in an open-addressed hash table usually contains a NULL pointer. However, when we remove an element, we cannot set its data pointer back to NULL because when probing to look up a subsequent element, NULL would indicate that the position is unoccupied and no more probes should be performed. In actuality, one or more elements may have been inserted by probing past the removed element while it was still in the table.

Considering this, we set the data pointer to the vacated member of the hash table data structure when we remove an element. The address of vacated serves as a special sentinel to indicate that a new element may be inserted at the position. This way, when probing to look ...