在C中寻找一个好的散列表实现

我主要对string键感兴趣。 有人可以指向我的图书馆吗?

我有同样的需要,并做了一些研究,并最终使用libcfu

它简单易读,所以如果我需要修改,我可以做,而不用花太多时间来理解。 这也是BSD许可证。 没有必要改变我的结构(embedded说下一个指针)

由于以下原因,我不得不拒绝其他选项(我个人的理由,YMMV):

  • sglib – >这是一个macros观迷宫,我不习惯使用macros来debugging/修改这样的代码库
  • cbfalconer – >许多redflags,并且网站关于支持/作者网站被closures和太多的不利讨论, 不想冒险
  • 谷歌sparce哈希 – >已经说过,这是C ++,而不是C.
  • glib(gnome hash) – >看起来很有前途; 但我找不到安装开发工具包的简单方法; 我只需要C例程/文件 – 而不是完整的开发环境
  • 朱迪 – >似乎太复杂了一个简单的用途..还没有准备好debugging自己,如果我不得不遇到任何问题
  • npsml(在这里提到) – >找不到源代码
  • 发现strmap非常简单和有用 – 它太简单了,键和值都必须是string; 值是string似乎太限制(应接受无效*)
  • uthash – >似乎很好(已在维基百科上提及hashtable); 发现它需要被修改的结构 – 不想这样做,因为性能不是我真正关心的使用 – 它更多的是开发速度。

总结很简单,使用strmap是好的; uthash如果你担心更多的内存使用。 如果只是开发的速度或易用性的主要目标,libcfu胜[注意libcfu内部做内存分配来维护节点/哈希表]。 令人惊讶的是没有很多简单的C哈希实现可用。

GLib是一个很好的库,可以用作C项目的基础。 他们有一些体面的数据结构产品,包括哈希表: http : //developer.gnome.org/glib/2.28/glib-Hash-Tables.html (链接更新4/6/2011)

对于琴弦, 朱迪arrays可能是好的。

Judy数组是一个复杂但速度非常快的关联数组结构,用于使用整数或string键来存储和查找值。 与普通数组不同,Judy数组可能很稀疏; 也就是说,它们可能有大量的未分配索引。

这里是CJudy图书馆

AC库提供了实现稀疏dynamic数组的最先进的核心技术。 Judy数组被声明为一个空指针。 Judy数组仅在填充时消耗内存,但如果需要,可以增长以充分利用所有可用内存。


其他参考,
这个维基百科哈希实现参考有一些C开源的链接。
而且, cmph – C中的最小完美哈希库支持多种algorithm。

这里有一些很好的答案:
容器类/ C库

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

戴夫汉森的C接口和实现包括一个精细的哈希表和其他几个精心devise的数据结构。 还有一个不错的string处理界面。 这本书很好,如果你能负担得起,但即使没有,我发现这个软件devise得非常好,足够小,可以学习整个,并在几个不同的项目中容易重用。

自从我问这个问题以来,已经有很长一段时间了……现在我可以将我自己的公共领域库添加到列表中:

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

C接口和实现讨论C中的哈希表实现。源代码可在线获取 。 (我的书的副本在工作,所以我不能更具体。)

Apache的APR库有自己的哈希实现 。 它已经被移植到Apache运行的任何东西上,并且Apache许可证也相当自由。

来自samtools / bwa / seqtk / klib的khash.h

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

通过http://www.biostars.org/p/10353/

从来没有使用过,但Google Sparsehash可能工作

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

定义的function

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

使用示例

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

下载tcl并使用经过时间validation的tcl散列函数。 这很容易。 TCL API是有据可查的。

Gperf – 完美的哈希函数发生器

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

stl有map和hash_map(hash_map只是在某些实现中),如果你能够使用C ++的话,它们是价值的关键。

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