Mastering Algorithms With C - Kyle Loudon [75]
Complexity
O (m), where m is the number of positions in the hash table.
Name
ohtbl_destroy
Synopsis
void ohtbl_destroy(OHTbl *htbl);
Return Value
None.
Description
Destroys the open-addressed hash table specified by htbl. No other operations are permitted after calling ohtbl_destroy unless ohtbl_init is called again. The ohtbl_destroy operation removes all elements from a hash table and calls the function passed as destroy to ohtbl_init once for each element as it is removed, provided destroy was not set to NULL.
Complexity
O (m), where m is the number of positions in the hash table.
Name
ohtbl_insert
Synopsis
int ohtbl_insert(OHTbl *htbl, const void *data);
Return Value
0if inserting the element is successful, 1 if the element is already in the hash table, or -1 otherwise.
Description
Inserts an element into the open-addressed hash table specified by htbl. The new element contains a pointer to data, so the memory referenced by data should remain valid as long as the element remains in the hash table. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (1)
Name
ohtbl_remove
Synopsis
int ohtbl_remove(OHTbl *htbl, void **data);
Return Value
0if removing the element is successful, or -1 otherwise.
Description
Removes the element matching data from the open-addressed hash table specified by htbl. Upon return, data points to the data stored in the element that was removed. It is the responsibility of the caller to manage the storage associated with the data.
Complexity
O (1)
Name
ohtbl_lookup
Synopsis
int ohtbl_lookup(const OHTbl *htbl, void **data);
Return Value
0if the element is found in the hash table, or -1 otherwise.
Description
Determines whether an element matches data in the open-addressed hash table specified by htbl. If a match is found, upon return data points to the matching data in the hash table.
Complexity
O (1)
Name
ohtbl_size
Synopsis
int ohtbl_size(const OHTbl *htbl);
Return Value
Number of elements in the hash table.
Description
Macro that evaluates to the number of elements in the open-addressed hash table specified by htbl.
Complexity
O (1)
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 up an element, we are assured that a NULL really means to stop probing.
Example 8.6. Header for the Open-Addressed