实现功能/持久字典数据结构

Question

我正在尝试在C中实现一个功能字典.实现功能列表或b-tree相当容易,但我几乎找不到关于字典/关联数组的任何引用.

我看了一下erlang的dict实现 - 在他们参考本文的源代码中:
Icon中的集合和表的动态哈希的设计和实现.

如果有人可以简单地解释erlang的方法或解决这个问题的另一种解决方案,那就太好了.

Answer 1

C语言中持久性数据结构的实现与函数式语言的实现基本相同.Chris Okasaki的纯功能数据结构是一个很好的参考.

通常,将固定宽度的整数映射到对象就足够了,因为虽然它本身不能为您提供完整的字典,但您可以在顶部构建字典:使用实际键的哈希作为键的关键字.底层映射,并使叶子指向相同散列值的(键,值)对的列表.

棘手的部分是内存管理,因为您通常不知道数据结构的某些部分何时变得无法访问.幸运的是,由于大多数持久性数据结构都基于树,因此引用计数通常很有效.为了能够管理数据结构引用的对象,可以为叶子节点的引用计数变为0时调用的回调提供挂钩.

例如,我的位图Patricia Trees的 C实现提供了以下API:

// Querying
void *bpt_get(bpt_t bpt, bpt_key_t key);
bool bpt_has_key(bpt_t bpt, bpt_key_t key);

// Adding and Removing Entries
bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item);
bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key);

// Managing Memory
void bpt_retain(bpt_t bpt);
void bpt_release(bpt_t bpt);
void bpt_dealloc(bpt_t bpt);
void bpt_set_dealloc_hook(bpt_t bpt,
                          bpt_key_t key,
                          void (*hook)(bpt_key_t key,
                                       void* value));

// Iteration
void bpt_for_mappings(bpt_t bpt,
                      void (*thunk)(bpt_key_t, void*, void*),
                      void *user_data);

// Making a Map Persistent (you can elide this if you don't
// want to support transients)
void bpt_seal(bpt_t bpt);

该实施可能会给你一些想法了.