1. 首页
  2. 问答
  3. 在C中寻找一个好的散列表实现

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

2009-07-16 63 views

回答

8

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

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

这里是一个Judy library in C。

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

其他参考资料，
这Wikipedia hash implementation reference有一些C开放源代码的链接。
另外，cmph - 在C最小完美散列库，支持几种算法。

来源

2009-07-16 16:27:46 nik

2

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

来源

2009-07-16 16:29:06 Nick

+2

我认为sparsehase用C++编写。 – 2009-07-16 16:37:16

+0

我认为你是对的 – Nick 2009-07-16 17:14:41

+1

事实上，在这种情况下C是感兴趣的语言 - 而不是C++。 – SetJmp 2009-07-17 00:37:34

0

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

来源

2009-07-16 16:31:05

+5

404错误。你会更新链接吗？ – 2013-01-04 21:12:19

0

下载tcl和使用他们的时间证明TCL散列函数。这很容易。 TCL API是有据可查的。

来源

2009-07-16 16:45:54 xcramps

16

GLib是一个伟大的图书馆，作为您的C项目的基础。他们有一些不错的数据结构产品，包括哈希表：http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html（链接更新2011年4月6日）

来源

2009-07-16 16:56:29

+0

+1：Glib确实是一个很棒的图书馆。 – 2009-07-17 01:24:51

+1

我是否正确地认为你通常动态链接到glib库以使用这些数据结构，如果从linux移到windows，可能会创建移植问题？ – bph 2012-01-23 10:35:05

+0

Glib只支持32位。如果你使用大量数据，glib不会是一个好选择 – Thorn 2013-02-25 19:10:32

5

戴夫·汉森的C Interfaces and Implementations包括罚款哈希表和几个其他精心设计的数据结构。还有一个不错的字符串处理界面。如果你负担得起，这本书是非常棒的，但即使没有，我也发现这个软件设计得非常好，足够小，可以完整地学习，并且可以轻松地在几个不同的项目中重复使用。

来源

2009-07-17 01:16:42

55

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

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

我不得不拒绝理由如下（我个人的原因，情况因人而异）其它选项：

  • sglib - >这是宏迷宫我很不习惯使用宏来调试/制作 这样一个代码库的变化
  • cbfalconer - >很多许可redflags，并且该网站被关闭并且在网上关于支持/作者的讨论太多;不想承担风险
  • google sparce-hash - >如前所述，这是针对C++的，而不是C
  • glib（gnome hash） - >看起来非常有前途;但我找不到安装开发工具包的简单方法;我只需要在C例程/文件 - 而不是完全成熟的研究与开发环境
  • 朱迪 - >似乎是一个简单的使用太复杂..还没有准备调试自己，如果我不得不遇到任何问题
  • npsml（在这里提到） - >找不到源
  • strmap发现非常简单和有用 - 它太简单了，键和值都必须是字符串;价值是字符串似乎太限制（应接受无效*）
  • uthash - >似乎很好（已在维基百科上提到散列表）;发现它需要对结构进行修改 - 不想这样做，因为性能并不是我使用的关注点 - 它更多的是开发速度。

总结为非常简单的使用strmap是好的; uthash如果你关心额外的内存使用。如果只是开发速度或易用性是主要目标，libcfu会胜出[注意libcfu在内部做内存分配以维护节点/散列表]。令人惊讶的是没有很多简单的C哈希实现可用。

来源

2011-12-12 06:39:15

相关问题

 相关问题