• Choose a category
• All
• Classic-Fiction

/*****************************************************************************

* *

* ------------------------------- ohtbl.h -------------------------------- *

* *

*****************************************************************************/

#ifndef OHTBL_H

#define OHTBL_H

#include

/*****************************************************************************

* *

* Define a structure for open-addressed hash tables. *

* *

*****************************************************************************/

typedef struct OHTbl_ {

int positions;

void *vacated;

int (*h1)(const void *key);

int (*h2)(const void *key);

int (*match)(const void *key1, const void *key2);

void (*destroy)(void *data);

int size;

void **table;

} OHTbl;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

int ohtbl_init(OHTbl *htbl, int positions, int (*h1)(const void *key), int

(*h2)(const void *key), int (*match)(const void *key1, const void *key2),

void (*destroy)(void *data));

void ohtbl_destroy(OHTbl *htbl);

int ohtbl_insert(OHTbl *htbl, const void *data);

int ohtbl_remove(OHTbl *htbl, void **data);

int ohtbl_lookup(const OHTbl *htbl, void **data);

#define ohtbl_size(htbl) ((htbl)->size)

#endif

ohtbl_init

The ohtbl_init operation initializes an open-addressed hash table so that it can be used in other operations (see Example 8.7). Initializing an open-addressed hash table is a simple operation in which we allocate space for the table; initialize the pointer in each position to NULL; encapsulate the h1, h2, match and destroy functions; initialize vacated to its sentinel address; and set the size member to 0.

The runtime complexity of ohtbl_init is O (m), where m is the number of positions in the table. This is because the data pointer in each of the m positions must be initialized to NULL, and all other parts of the operation run in a constant amount of time.

ohtbl_destroy

The ohtbl_destroy operation destroys an open-addressed hash table (see Example 8.7). Primarily this means freeing the memory ohtbl_init allocated for the table. The function passed as destroy to ohtbl_init is called once for each element as it is removed, provided destroy was not set to NULL.

The runtime complexity of ohtbl_destroy is O (m), where m is the number of positions in the hash table. This is because we must traverse all positions in the hash table to determine which are occupied. If destroy is NULL, ohtbl_destroy runs in O (1) time.

ohtbl_insert

The ohtbl_insert operation inserts an element into an open-addressed hash table (see Example 8.7). Since an open-addressed hash table has a fixed size, we first ensure that there is room for the new element to be inserted. Also, since a key is not allowed to be inserted into the hash table more than once, we call ohtbl_lookup to make sure the table does not already contain the new element.

Once these conditions are met, we use double hashing to probe the table for an unoccupied position. A position in the table is unoccupied if it points either to NULL or the address in vacated, a special member of the hash table data structure that indicates that a position has had an element removed from it. Once we find an unoccupied position in the table, we set the pointer at that position to point to the data we wish to insert. After this, we increment the table size.

Assuming we approximate uniform hashing well and the load factor of the hash table is relatively small, the runtime complexity of ohtbl_insert is O (1). This is because in order to find an unoccupied position at which to insert the element, we expect to probe 1/(1 - α) positions, a number treated as a small constant, where α is the load factor of the hash table.

ohtbl_remove

The ohtbl_remove operation removes an element from an open-addressed hash table (see