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

Question

我主要对字符串键感兴趣.有人能指点我去图书馆吗？

Answer 1

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

它简单易读,如果我需要修改,我可以不花太多时间去理解.它也是BSD许可证.无需更改我的结构(嵌入说下一个指针)

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

• sglib - >这是一个宏迷宫,我不习惯只使用宏在这样的代码库上调试/进行更改
• cbfalconer - >许多许可红旗,网站关闭以及关于支持/作者的网上太多不利讨论; 不想承担风险
• google sparce-hash - >如前所述,它适用于C++,而不是C语言
• glib(gnome hash) - >看起来非常有前途; 但我找不到任何简单的方法来安装开发人员工具包; 我只需要C例程/文件 - 而不是完整的开发环境
• Judy - >看起来太复杂而不能简单使用..如果我不得不遇到任何问题,也没准备好调试自己
• npsml(这里提到) - >找不到源码
• strmap发现非常简单和有用 - 它太简单了,键和值都必须是字符串; 值是字符串似乎限制太多(应该接受void*)
• uthash - >似乎很好(已在维基百科上提到哈希表); 发现它需要修改结构 - 不想这样做,因为性能并不是我使用的真正问题 - 更多的是开发速度.

总结为非常简单的使用strmap是好的; uthash如果您担心额外的内存使用.如果只是开发速度或易用性是主要目标,libcfu获胜[注意libcfu内部进行内存分配以维护节点/哈希表].令人惊讶的是,没有很多简单的C哈希实现可用.

Answer 2

GLib是一个很棒的库,可以作为C项目的基础.他们有一些不错的数据结构产品,包括Hash Tables:http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html(link updated 4/6/2011)

Answer 3

对于字符串,Judy Array可能很好.

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

这里是一个朱迪库中Ç.

AC库,提供实现稀疏动态阵列的最先进的核心技术.Judy数组只用空指针声明.Judy数组仅在填充时消耗内存,但如果需要,可以增长以利用所有可用内存.

其他参考资料,
这个维基百科哈希实现参考有一些C开源链接.
此外,cmph - 最小完美哈希库C,支持几种算法.

Answer 4

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

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

Answer 5

Dave Hanson的C接口和实现 包括一个精细的哈希表和其他几个精心设计的数据结构.还有一个很好的字符串处理接口.如果你负担得起,这本书很棒,但即便没有,我发现这个软件设计得非常好,小到足以完全学习,并且易于在几个不同的项目中重复使用.

Answer 6

自从我提出这个问题以来已经很久了...我现在可以将自己的公共域库添加到列表中:

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