Looking for a good hash table implementation in C
CStringHashtableHashC Problem Overview
I am primarily interested in string keys. Can someone point me towards a library?
C Solutions
Solution 1 - C
I had the same need and did some research and ended up using libcfu
It's simple and readable so if I have a need to modify, I can do it without spending too much time to understand. It's also of BSD license. No need to change my structs (to embed say a next pointer)
I had to reject the other options for following reasons (my personal reasons, YMMV):
- sglib --> it's a macro maze and I wasn't comfortable debugging/making changes on such a code base using just macros
- cbfalconer --> lot of licensing redflags, and the site was down and too many unfavorable discussions on web about support/author; didn't want to take the risk
- google sparce-hash --> as stated already, it's for C++, not C
- glib (gnome hash) --> looked very promising; but I couldn't find any easy way to install the developer kit; I just needed the C routines/files -- not the full blown developement environment
- Judy --> seems too complex for a simple use.. also was not ready to debug myself if I had to run into any issues
- npsml (mentioned here) --> can't find the source
- strmap found very simple and useful -- it's just too simplistic that both key and value must be strings; value being string seems too restrictive (should accept void *)
- uthash --> seems good (has been mentioned on wikipedia on hashtable); found that it requires struct to be modified -- didn't want to do that as performace is not really a concern for my use --it's more of development velocity.
In summary for very simple use strmap is good; uthash if you are concerned with additional memory use. If just speed of development or ease of use is primary objective, libcfu wins [note libcfu internally does memory allocation to maintain the nodes/hashtables]. It's surprising that there aren't many simple C hash implementations available.
Solution 2 - C
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://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (link updated 4/6/2011)
Solution 3 - C
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.
Solution 4 - C
There are some good answers here:
https://stackoverflow.com/questions/305611/container-class-library-for-c/306461#306461">https://stackoverflow.com/questions/305611/container-class-library-for-c/306461#306461</a>
http://sglib.sourceforge.net.">http://sglib.sourceforge.net.</a>
http://cbfalconer.home.att.net/download/">http://cbfalconer.home.att.net/download/</a>
Solution 5 - C
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.
Solution 6 - C
A long time has passed since I asked this question... I can now add my own public domain library to the list:
Solution 7 - C
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.)
Solution 8 - C
Apache's APR library has its own hash-implementation. It is already ported to anything Apache runs on and the Apache license is rather liberal too.
Solution 9 - C
khash.h from samtools/bwa/seqtk/klib
curl https://raw.github.com/attractivechaos/klib/master/khash.h
Solution 10 - C
Never used it but Google Sparsehash may work
Solution 11 - C
Download tcl and use their time-proven tcl hash function. It's easy. The TCL API is well documented.
Solution 12 - C
https://github.com/dozylynx/C-hashtable
[updated URL as original now 404s: 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)" */
Solution 13 - C
Gperf - Perfect Hash Function Generator
http://www.ibm.com/developerworks/linux/library/l-gperf.html
Solution 14 - C
stl has map and hash_map (hash_map is only in some implementations) that are key to value if you are able to use C++.