• Choose a category
• All
• Classic-Fiction

By Root 1369 0

the elements from each bucket and freeing the memory chtbl_init allocated for the table. The function passed as destroy to chtbl_init is called once for each element as it is removed, provided destroy was not set to NULL.

The runtime complexity of chtbl_destroy is O (m), where m is the number of buckets in the table. This is because list_destroy is called once for each bucket. In each bucket, we expect to remove a number of elements equal to the load factor of the hash table, which is treated as a small constant.

chtbl_insert

The chtbl_insert operation inserts an element into a chained hash table (see Example 8.3). Since a key is not allowed to be inserted into the hash table more than once, chtbl_lookup is called to make sure that the table does not already contain the new element. If no element with the same key already exists in the hash table, we hash the key for the new element and insert it into the bucket at the position in the hash table that corresponds to the hash coding. If this is successful, we increment the table size.

Assuming we approximate uniform hashing well, the runtime complexity of chtbl_insert is O (1), since chtbl_lookup, hashing a key, and inserting an element at the head of a linked list all run in a constant amount of time.

chtbl_remove

The chtbl_remove operation removes an element from a chained hash table (see Example 8.3). To remove the element, we hash its key, search the appropriate bucket for an element with a key that matches, and call list_rem_next to remove it. The pointer prev maintains a pointer to the element before the one to be removed since list_rem_next requires this. Recall that list_rem_next sets data to point to the data removed from the table. If a matching key is not found in the bucket, the element is not in the table. If removing the element is successful, we decrease the table size by 1.

Assuming we approximate uniform hashing well, the runtime complexity of chtbl_remove is O (1). This is because we expect to search a number of elements equal to the load factor of the hash table, which is treated as a small constant.

chtbl_lookup

The chtbl_lookup operation searches for an element in a chained hash table and returns a pointer to it (see Example 8.3). This operation works much like chtbl_remove, except that once the element is found, it is not removed from the table.

Assuming we approximate uniform hashing well, the runtime complexity of chtbl_lookup is O (1). This is because we expect to search a number of elements equal to the load factor of the hash table, which is treated as a small constant.

chtbl_size

This macro evaluates to the number of elements in a chained hash table (see Example 8.2). It works by accessing the size member of the CHTbl structure.

The runtime complexity of chtbl_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.3. Implementation of the Chained Hash Table Abstract Datatype

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

* *

* ------------------------------- chtbl.c -------------------------------- *

* *

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

#include

#include

#include "list.h"

#include "chtbl.h"

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

* *

* ------------------------------ chtbl_init ------------------------------ *

* *

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

int chtbl_init(CHTbl *htbl, int buckets, int (*h)(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 = (List *)malloc(buckets * sizeof(List))) == NULL)

return -1;

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