在C中寻找良好的哈希表实现[关闭]

Question

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

Answer 1

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

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

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

sglib->这是一个宏迷宫，我不习惯调试/制作仅使用宏在这样的代码库上进行更改
cbfalconer->大量许可危险信号，并且该站点已关闭，并且网络上有太多有关支持/作者的不利讨论；不想冒险
google sparce-hash->如前所述，它适用于C ++，而不适用于C
glib（gnome hash）->看起来很有希望；但是我找不到任何简单的方法来安装开发人员工具包；我只需要C例程/文件-不需要完整的开发环境
Judy->似乎太简单了，无法使用..如果我遇到任何问题，还不准备调试自己
npsml（在这里提到）->找不到源
strmap发现非常简单和有用-键和值都必须是字符串，这太简单了；字符串中的值似乎过于严格（应该接受void *）
uthash->似乎不错（在Wikipedia的哈希表中已提及）；发现需要修改结构-不想这样做，因为performance并不是我的使用担心-开发速度更高。

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

Answer 2

2
投票

从未使用过，但Google Sparsehash可能起作用

Answer 3

下载tcl，并使用其经过时间验证的tcl哈希函数。这很容易。 TCL API有详细记录。

Answer 4

Gperf-完美的哈希函数生成器

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

Answer 5

https://github.com/dozylynx/C-hashtable

[[已更新的URL现在是原始404：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)" */

Answer 6

stl具有map和hash_map（hash_map仅在某些实现中），如果您能够使用C ++，它们是值的关键。

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

Answer 7

GLib是一个很棒的库，可以用作您C项目的基础。他们提供了一些不错的数据结构产品，包括哈希表：http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html（链接更新4/6/2011）

Answer 8

对于字符串，Judy Array可能不错。

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

这里是Judy library in C。

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

其他参考文献，此Wikipedia hash implementation reference具有一些C开源链接。此外，cmph-C中的最小完美哈希库支持多种算法。

Answer 9

这里有一些很好的答案：Container Class / Library for C

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

Answer 10

Dave Hanson的C Interfaces and Implementations包括一个精细的哈希表和其他一些精心设计的数据结构。还有一个不错的字符串处理接口。如果您负担得起这本书，那是很棒的书，但是即使没有，我也发现该软件设计得很好，足够小，可以全面学习，并且可以在多个不同的项目中轻松使用。