• Choose a category
• All
• Classic-Fiction

By Root 1368 0

Example 8.7). To remove the element, we use double hashing as in ohtbl_insert to locate the position at which the element resides. We continue searching until we locate the element or NULL is found. If we find the element, we set data to the data being removed and decrease the table size by 1. Also, we set the position in the table to the vacated member of the hash table data structure.

Assuming we approximate uniform hashing well, the runtime complexity of ohtbl_remove is O (1). This is because we expect to probe 1/(1 - α) positions, a number treated as a small constant, where α is the largest load factor of the hash table since calling ohtbl_init. The reason that the performance of this operation depends on the largest load factor and thus does not improve as elements are removed is that we must still probe past vacated positions. The use of the vacated member only improves the performance of ohtbl_insert.

ohtbl_lookup

The ohtbl_lookup operation searches for an element in an open-addressed hash table and returns a pointer to it (see Example 8.7). This operation works similarly to ohtbl_remove, except that the element is not removed from the table.

Assuming we approximate uniform hashing well, the runtime complexity of ohtbl_lookup is the same as ohtbl_remove, or O (1). This is because we expect to probe 1/(1 - α) positions, a number treated as a small constant, where α is the largest load factor of the hash table since calling ohtbl_init. The reason that performance depends on the largest load factor since calling ohtbl_init is the same as described for ohtbl_remove.

ohtbl_size

This macro evaluates to the number of elements in an open-addressed hash table (see Example 8.6). It works by accessing the size member of the OHTbl structure.

The runtime complexity of ohtbl_size is O (1) because accessing a member of a structure is a simple task that runs in a constant amount of time.

Example 8.7. Implementation of the Open-Addressed Hash Table Abstract Datatype

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

* *

* ------------------------------- ohtbl.c -------------------------------- *

* *

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

#include

#include

#include "ohtbl.h"

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

* *

* Reserve a sentinel memory address for vacated elements. *

* *

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

static char vacated;

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

* *

* ------------------------------ ohtbl_init ------------------------------ *

* *

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

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)) {

int i;

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

* *

* Allocate space for the hash table. *

* *

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

if ((htbl->table = (void **)malloc(positions * sizeof(void *))) == NULL)

return -1;

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

* *

* Initialize each position. *

* *

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

htbl->positions = positions;

for (i = 0; i < htbl->positions; i++)

htbl->table[i] = NULL;

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

* *

* Set the vacated member to the sentinel memory address reserved for this. *

* *

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

htbl->vacated = &vacated;

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

* *

* Encapsulate the functions. *

* *

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