Looking for a good hash table implementation in C

Question

I am primarily interested in string keys. Can someone point me towards a library?

-A

Answer 1

For strings, the Judy Array might be good.

A Judy array is a complex but very fast associative array data structure for storing and looking up values using integer or string keys. Unlike normal arrays, Judy arrays may be sparse; that is, they may have large ranges of unassigned indices.

Here is a Judy library in C.

A C library that provides a state-of-the-art core technology that implements a sparse dynamic array. Judy arrays are declared simply with a null pointer. A Judy array consumes memory only when it is populated, yet can grow to take advantage of all available memory if desired.

---

Other references,
This Wikipedia hash implementation reference has some C open source links.
Also, cmph -- A Minimal Perfect Hashing Library in C, supports several algorithms.

Answer 2

Never used it but Google Sparsehash may work

Answer 3

http://www.cl.cam.ac.uk/~cwc22/hashtable/

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)" */

Answer 4

There are some good answers here:
http://stackoverflow.com/questions/305611/container-class-library-for-c/306461#306461

http://sglib.sourceforge.net.
http://cbfalconer.home.att.net/download/

Answer 5

Download tcl and use their time-proven tcl hash function. It's easy. The TCL API is well documented.

Answer 6

C Interfaces and Implementations discusses hash table implementations in C. The source code is available online. (My copy of the book is at work so I can't be more specific.)

Answer 7

GLib is a great library to use as a foundation in your C projects. They have some decent data structure offerings including Hash Tables: http://library.gnome.org/devel/glib/2.21/glib-Hash-Tables.html

Answer 8

Gperf - Perfect Hash Function Generator

http://www.ibm.com/developerworks/linux/library/l-gperf.html

Answer 9

Dave Hanson's C Interfaces and Implementations includes a fine hash table and several other well-engineered data structures. There is also a nice string-processing interface. The book is great if you can afford it, but even if not, I have found this software very well designed, small enough to learn in its entirety, and easy to reuse in several different projects.