Mastering Algorithms with C

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 <stdlib.h> #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 --------------------------- * * * *****************************************************************************/ ...