Looking for a good hash table implementation in C

问题:

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 6 years ago.

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

回答1:

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.

回答2:

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)

回答3:

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.

回答4:

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

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

回答5:

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.

回答6:

A long time has passed since I asked this question... I can now add my own public domain library to the list:

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

回答7:

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.)

回答8:

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.

回答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/

回答10:

Never used it but Google Sparsehash may work

回答11:

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

回答12:

Gperf - Perfect Hash Function Generator

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

回答13:

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

回答14:

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++.

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