在 C 语言中寻找一个好的哈希表实现

我主要对字符串键感兴趣。有人能告诉我哪里有图书馆吗？

78802 次浏览
小开

对于字符串，朱迪阵列可能比较好。

Judy 数组是一个复杂但非常快速的关联数组，用于存储和查找使用整数或字符串键的值。与普通数组不同，Judy 数组可能是稀疏的; 也就是说，它们可能有大范围的未分配索引。

这是 强大 > 朱迪图书馆 在 < 强大 > C 。

一个 C 库，它提供了实现稀疏动态数组的最先进的核心技术。Judy 数组仅用空指针声明。Judy 数组只有在填充时才会消耗内存，但是如果需要的话，它可以增长以利用所有可用内存。

其他参考文献,
这个 Wikipedia 散列实现引用有一些 C开源链接。
此外，强—— C中最小的完美散列库，支持多种算法。

小开

从未使用过，但 谷歌 Sparsehash可以工作

小开

Https://github.com/dozylynx/c-hashtable

[更新网址为原始404s: http://www.cl.cam.ac.uk/~cwc22/hashtable/]

定义函数

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

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

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

小开

下载 Tcl并使用经过时间验证的 TCL 散列函数。

小开

接口和实现 讨论了 C 中的哈希表实现。源代码是 可在网上查阅。(我的那本书正在上班，所以我不能再具体了。)

小开

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

小开

Gperf-完美散列发生器

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

小开

DaveHanson 的 接口和实现包括一个很好的散列表和其他几个设计良好的数据结构。还有一个很好的字符串处理接口。如果你能负担得起的话，这本书是不错的，但即使负担不起，我也发现这个软件设计得非常好，足够小，可以完整地学习，并且很容易在几个不同的项目中重复使用。

小开

Stl 有 map 和 hash _ map (hash _ map 只在某些实现中有) ，如果您能够使用 C + + ，它们是值的关键。

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

小开

自从我提出这个问题以来，已经过去了很长一段时间... ... 我现在可以把我自己的公共域库添加到这个列表中了:

Http://sourceforge.net/projects/npsml/

小开

我有同样的需要，做了一些研究，最终使用 Libcfu

它简单易读，所以如果我需要修改，我可以不花太多时间去理解它。还有 BSD 许可证。不需要改变我的结构(嵌入说下一个指针)

我不得不拒绝其他的选择，原因如下(我个人的原因，基督教青年会) :

  • 这是一个巨大的迷宫，我不喜欢调试/制作 仅使用宏对这样的代码库进行更改
  • Cbfalconer-> 许多许可的红旗，和网站关闭和太多不利的讨论在网络上的支持/作者; 不想承担风险
  • 如前所述，这是针对 C + + 的，而不是 C
  • Glib (gnome hash)—— > 看起来非常有前途; 但是我找不到任何简单的方法来安装开发工具包; 我只需要 C 例程/文件——而不是完整的开发环境
  • Judy --> seems too complex for a simple use.. also was not ready to debug myself if I had to run into any issues
  • Npsml (在这里提到)—— > 找不到源
  • Strmap 发现非常简单和有用——键和值都必须是字符串实在是太简单了; 值必须是字符串似乎限制太多了(应该接受 void *)
  • Uthash 看起来不错(在维基百科的 hashtable 上已经提到过) ; 发现它需要修改 struct ——不想这么做，因为性能并不是我真正关心的问题——它更多的是开发速度。

总之，对于非常简单的使用来说，strmap 是好的; uthash 如果您关心额外的内存使用。如果只是以开发速度或易用性为主要目标，那么 libcfu 胜出[注意，libcfu 在内部进行内存分配来维护节点/hashtables ]。令人惊讶的是，没有多少简单的 C 散列实现可用。

小开

Apache 的 APR 库有自己的 散列实现。它已经被移植到 Apache 运行的任何东西上，而且 阿帕奇执照也相当开放。

小开

Hfrom samtools/bwa/seqtk/klib 来自 samtools/bwa/seqtk/klib

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

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


提交答案