• Choose a category
• All
• Classic-Fiction

By Root 1459 0

chained 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

chtbl_remove

Synopsis

int chtbl_remove(CHTbl *htbl, void **data);

Return Value

0if removing the element is successful, or -1 otherwise.

Description

Removes the element matching data from the chained 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

chtbl_lookup

Synopsis

int chtbl_lookup(const CHTbl *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 chained hash table specified by htbl. If a match is found, data points to the matching data in the hash table upon return.

Complexity

O (1)

Name

chtbl_size

Synopsis

int chtbl_size(CHTbl *htbl);

Return Value

Number of elements in the hash table.

Description

Macro that evaluates to the number of elements in the chained hash table specified by htbl.

Complexity

O (1)

Implementation and Analysis of Chained Hash Tables

A chained hash table consists of an array of buckets. Each bucket is a linked list containing the elements that hash to a certain position in the table. The structure CHTbl is the chained hash table data structure (see Example 8.2). This structure consists of six members: buckets is the number of buckets allocated in the table; h, match, and destroy are members used to encapsulate the functions passed to chtbl_init ; size is the number of elements currently in the table; and table is the array of buckets.

Example 8.2. Header for the Chained Hash Table Abstract Datatype

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

* *

* ------------------------------- chtbl.h -------------------------------- *

* *

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

#ifndef CHTBL_H

#define CHTBL_H

#include

#include "list.h"

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

* *

* Define a structure for chained hash tables. *

* *

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

typedef struct CHTbl_ {

int buckets;

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

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

void (*destroy)(void *data);

int size;

List *table;

} CHTbl;

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

* *

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

* *

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

int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int

(*match)(const void *key1, const void *key2), void (*destroy)(void *data));

void chtbl_destroy(CHTbl *htbl);

int chtbl_insert(CHTbl *htbl, const void *data);

int chtbl_remove(CHTbl *htbl, void **data);

int chtbl_lookup(const CHTbl *htbl, void **data);

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

#endif

chtbl_init

The chtbl_init operation initializes a chained hash table so that it can be used in other operations (see Example 8.3). Initializing a chained hash table is a simple operation in which we allocate space for the buckets; initialize each bucket by calling list_init ; encapsulate the h, match, and destroy functions; and set the size member to 0.

The runtime complexity of chtbl_init is O (m), where m is the number of buckets in the table. This is because the O (1) operation list_init must be called once for each of the m buckets. All other parts of the operation run in a constant amount of time.

chtbl_destroy

The chtbl_destroy operation destroys a chained hash table (see Example 8.3). Primarily this means removing