Mastering Algorithms With C - Kyle Loudon [67]
Example 8.1 presents a hash function that performs particularly well for strings. It coerces a key into a permuted integer through a series of bit operations. The resulting integer is mapped using the division method. The function was adapted from Compilers: Principles, Techniques, and Tools (Reading, MA: Addison-Wesley, 1986), by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, who attributed it to P. J. Weinberger as a hash function that performed well in hashing strings for his compiler.
Example 8.1. A Hash Function That Performs Well for Strings
/*****************************************************************************
* *
* ------------------------------- hashpjw.c ------------------------------ *
* *
*****************************************************************************/
#include "hashpjw.h"
/*****************************************************************************
* *
* -------------------------------- hashpjw ------------------------------- *
* *
*****************************************************************************/
unsigned int hashpjw(const void *key) {
const char *ptr;
unsigned int val;
/*****************************************************************************
* *
* Hash the key by performing a number of bit operations on it. *
* *
*****************************************************************************/
val = 0;
ptr = key;
while (*ptr != '\0') {
unsigned int tmp;
val = (val << 4) + (*ptr);
if (tmp = (val & 0xf0000000)) {
val = val ^ (tmp >> 24);
val = val ^ tmp;
}
ptr++;
}
/*****************************************************************************
* *
* In practice, replace PRIME_TBLSIZ with the actual table size. *
* *
*****************************************************************************/
return val % PRIME_TBLSIZ
;
}
Interface for Chained Hash Tables
Name
chtbl_init
Synopsis
int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key),
int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data));
Return Value
0if initializing the hash table is successful, or -1 otherwise.
Description
Initializes the chained hash table specified by htbl. This operation must be called for a chained hash table before the hash table can be used with any other operation. The number of buckets allocated in the hash table is specified by buckets. The function pointer h specifies a user-defined hash function for hashing keys. The function pointer match specifies a user-defined function to determine whether two keys match. It should return 1 if key1 is equal to key2, and otherwise. The destroy argument provides a way to free dynamically allocated data when chtbl_destroy is called. For example, if the hash table contains data dynamically allocated using malloc, destroy should be set to free to free the data as the hash table is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a hash table containing data that should not be freed, destroy should be set to NULL.
Complexity
O (m), where m is the number of buckets in the hash table.
Name
chtbl_destroy
Synopsis
void chtbl_destroy(CHTbl *htbl);
Return Value
None.
Description
Destroys the chained hash table specified by htbl. No other operations are permitted after calling chtbl_destroy unless chtbl_init is called again. The chtbl_destroy operation removes all elements from a hash table and calls the function passed as destroy to chtbl_init once for each element as it is removed, provided destroy was not set to NULL.
Complexity
O (m), where m is the number of buckets in the hash table.
Name
chtbl_insert
Synopsis
int chtbl_insert(CHTbl *htbl, const void *data);
Return Value
0if inserting the element is successful, 1 if the element is already in the hash table, or -1 otherwise.
Description
Inserts an element into the