Finding a Good Hash Table Implementation in C

Question

First of all, I am interested in string keys. Can someone point me to the library?

Answer 1

I had the same need and did some research and ended up using libcfu

It is simple and straightforward, so if I need to change, I can do it without spending too much time to understand. It is also a BSD license. No need to change my structures (to insert the words of the next pointer)

I had to decline other options for the following reasons (my personal reasons, YMMV):

• sglib → this is a macro labyrinth, and it was inconvenient for me to debug / make changes on such a code base, using only macros
• cbfalconer → a lot of licensed red flags, and the site was omitted and too many adverse discussions on the Internet about support / author; did not want to take risks
• google sparce-hash → as already said, this is for C ++, not C
• glib (gnome hash) → looked very promising; but I could not find an easy way to install the developer kit; I just needed C routines / files - not a complete bloated development environment
• Judy → seems too complicated for simple use .. also was not ready to debug myself if I had to face any problems.
• npsml (mentioned here) -> cannot find source
• strmap is found very simple and useful - just too simple that both the key and value must be strings; String value is too strict (should take void *)
• uthash → seems good (mentioned on a hash table on wikipedia); found that he requires that the structure be modified - did not want to do this, since performace is not really a problem for my use - it is a high development speed.

In conclusion, for a very simple use, strmap is good; uthash if you are interested in using extra memory. If only development speed or ease of use is the primary goal, libcfu wins [note libcfu internally allocates memory to support nodes / hash tables]. Surprisingly, there are not many simple C hash code implementations.

Answer 2

GLib is a great library to use as the basis for your C projects. They have some decent suggestions for data structure, including Hash tables: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (link updated 4/6/2011)

Answer 3

For strings, Judy Array might be fine.

The Judy array is a complex, but very fast associative array data structure for storing and searching values ​​using integer or string keys. Unlike regular arrays, Judy arrays can be sparse; that is, they can have large ranges of unassigned indices.

Here is the Judy library in C.

The C library, which provides the most advanced core technology that implements a sparse dynamic array. Judy arrays are simply declared with a null pointer. The Judy array only consumes memory when it is populated, but can grow to use all available memory if desired.

---

Other links
This Wikipedia hash link link contains several open source C links.
In addition, cmph is the smallest perfect hash library in C that supports several algorithms.

Answer 4

There are some good answers here:
Container Class / Library for C

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

Answer 5

Dave Hanson C Interfaces and Implementations includes a shallow hash table and several other well-designed data structures. There is also a beautiful string processing interface. The book is great if you can afford it, but even if it isn’t, I found this software very well designed, small enough to learn completely and easily use it in several different projects.

Answer 6

It has been a long time since I asked this question ... Now I can add my own public domain library to the list:

http://sourceforge.net/projects/npsml/

Answer 7

C Interfaces and implementations discusses hash table implementations in C. Source code is available online . (My copy of the book works, so I cannot be more specific.)

Answer 8

APR library APR has its own hash implementation . It has already been ported to all Apache, and the Apache license is also quite liberal.

Answer 9

khash.h from samtools / bwa / seqtk / klib

curl https://raw.github.com/attractivechaos/klib/master/khash.h

via http://www.biostars.org/p/10353/

Answer 10

Never used it, but Google Sparsehash may work

Answer 11

Download tcl and use your time-tested tcl hash function. It is easy. The TCL API is well documented.

Answer 12

Gperf - Perfect Hash Function Generator

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

Answer 13

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

Specific functions

 * create_hashtable * hashtable_insert * hashtable_search * hashtable_remove * hashtable_count * hashtable_destroy 

Usage example

  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 14

stl has a map and hash_map (hash_map only in some implementations), which are the key to value if you can use C ++.

http://www.cplusplus.com/reference/stl/map/