C Hash Table

扫码查看

Source code for a hash table data structure in C

This code is made available under the terms of thenew BSD license.

If you use this code, drop me an email. It's nice to feel usefuloccasionally.
I promise not to sell your email address to Nigerian spam bandits. Thanks.
Christopher Clark, January 2005.


Defined functions

  • create_hashtable
  • hashtable_insert
  • hashtable_search
  • hashtable_remove
  • hashtable_count
  • hashtable_destroy

Example of use

      struct hashtable  *h;
struct some_key *k;
struct some_value *v;

static unsigned int hash_from_key_fn( void *k );
static int keys_equal_fn ( void *key1, void *key2 );

h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);

insert_key = (struct some_key *) malloc(sizeof(struct some_key));
retrieve_key = (struct some_key *) malloc(sizeof(struct some_key));

v = (struct some_value *) malloc(sizeof(struct some_value));

(You should initialise insert_key, retrieve_key and v here)

if (! hashtable_insert(h,insert_key,v) )
{ exit(-1); }

if (NULL == (found = hashtable_search(h,retrieve_key) ))
{ printf("not found!"); }

if (NULL == (found = hashtable_remove(h,retrieve_key) ))
{ printf("Not found\n"); }

hashtable_destroy(h,1); /* second arg indicates "free(value)" */

Description

The table will increase in size as elements are added, to keep theratio of elements to table size below a threshold. The table is sizedby selecting a prime number of appropriate magnitude, to ensure bestdistribution of the contents.

For improved type safety, macros have been defined and may be used todefine type-safe(r) hashtable access functions, with methodsspecialized to take known key and value types as parameters. Example:Insert this at the start of your file:

 DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);

This defines the functions 'insert_some', 'search_some' and 'remove_some'.These operate just like hashtable_insert etc., with the same parameters,but their function signatures have 'struct some_key *' rather than'void *', and hence can generate compile time errors if your program issupplying incorrect data as a key (and similarly for value).

Note that the hash and key equality functions passed to create_hashtablestill take 'void *' parameters instead of 'some key *'. This shouldn't bea serious issue as they're only defined and passed once, and the otherfunctions will ensure that only valid keys are supplied to them.

The cost for this checking is increased code size and runtime overhead- if performance is important, it may be worth switching back to theunsafe methods once your program has been debugged with the safe methods.


Iterator

The iterator is a simple one-way iterator over the hashtablecontents, providing accessors for the the key and value at the currentelement.

    /* Iterator constructor only returns a valid iterator if
* the hashtable is not empty */

if (hashtable_count(h) > 0)
{
itr = hashtable_iterator(h);
do {
k = hashtable_iterator_key(itr);
v = hashtable_iterator_value(itr);

/* here (k,v) are a valid (key, value) pair */
/* We could call 'hashtable_remove(h,k)' - and this operation
* 'free's k and returns v.
* However, after the operation, the iterator is broken.
*/

} while (hashtable_iterator_advance(itr));
}
free(itr);


Notes

You may find this (external) page of hashfunctions for stringshelpful.Note that the hashtable includes a small section of code to protectagainst poor hash functions - it may be worthwhile removing this if youare sure you are using a good hash function.

If hashing strings, remember that strcmp is not a boolean comparisonfunction directly suitable for keys_equal_fn.

Archived copy of the original hashtable implementation, where table size is a power of two, rather than prime.[ hashtable_powers.c ]

Credits

Christopher Clark
Updated 11thJanuary, 2005.

C Hash Table-LMLPHP
文件:hashtable.rar
大小:13KB
下载:下载
11-30 02:30
查看更多