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

Question

我主要对字符串键感兴趣。有人可以将我指向图书馆吗？

Answer 1

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

它简单易读，因此，如果我需要修改，则无需花费太多时间来理解就可以做到。它也是BSD许可证。无需更改我的结构（嵌入说一个下一个指针）

由于以下原因（我个人原因，YMMV），我不得不拒绝其他选择：

• sglib->这是一个宏迷宫，我不习惯使用宏在这样的代码库上调试/进行更改

• cbfalconer->大量许可危险信号，并且该网站瘫痪了，并且在网络上有太多关于支持/作者的不利讨论；不想冒险

• google sparce-hash->如前所述，它用于C ++，而不是C

• glib（gnome哈希）->看起来很有希望；但是我找不到任何简单的方法来安装开发人员工具包；我只需要C例程/文件-不需要全面的开发环境

• Judy->看起来太简单了，无法使用..如果我遇到任何问题，也没有准备好调试自己。

• npsml（在这里提到）->找不到源

• strmap发现非常简单和有用-键和值都必须是字符串，这太简单了；字符串形式的值似乎过于严格（应接受void *）

• uthash- >看起来不错（在Wikipedia的hashtable上已经提到过）；发现需要修改结构-不想这样做，因为performance并不是我的使用担心-开发速度更高。

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

Answer 2

对于字符串，Judy Array可能很好。

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

这里是一个朱迪库中Ç。

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

其他参考，

此Wikipedia哈希实现参考具有一些C开源链接。

另外，cmph-中的最小完美哈希库C支持多种算法。