C 中非常简单的地图实现（用于缓存目的）？

Question

我有一个程序可以读取文件中的 url，并在每个 URL 主机上执行 gethostbyname() 操作。 这个调用相当消耗。 我想缓存它们。

C 语言中是否有一个非常简单的基于地图的代码片段，我可以用它来进行缓存？ （我只是不想重新发明轮子）。

它必须具备以下几点：

• 具有宽松许可证的开源（想想 BSD 或公共领域）。
• 非常简单：理想情况下少于 100 个 LOC
• 键是 char* 和值 void*。 无需复制它们。
• 没有真正需要实现 remove()，但需要 contains() 或 put() 应该替换该值。

PS：我给它贴上了作业的标签，因为它可能是。 我只是非常懒惰，并且确实想避免重新实现时可能遇到的所有常见陷阱。

Answer 1

在这里找到了一个实现： c 文件和 h 文件与您所要求的非常接近。 W3C 许可证

Answer 2

Dave Hanson 的 C 接口和实现 包含一个很好的哈希表，以及许多其他内容有用的模块。 哈希表有 150 行，但这包括内存管理、高阶映射函数和数组转换。 该软件是免费的，这本书值得购买。

Answer 3

不是偷懒，而是非常明智地避免写这些东西。

这个 库 怎么样，我自己从未使用过它，但它似乎声称可以满足您的要求。

Answer 4

memcached？

不是代码片段，而是高性能分布式缓存引擎。

Answer 5

您可以尝试使用以下实现

clib

Answer 6

克里斯托弗·克拉克的哈希表的实现非常简单。 虽然有 100 多行，但也不是很多。

Clark 的代码似乎已进入 Google 的并发库作为并行化示例。

Answer 7

C++ 中的 std::map 本质上是一棵红黑树； 使用C 中现有的红黑树实现怎么样？ 我链接的那个更像是 700 LOC，但它的评论非常好，而且从我粗略地看去，它看起来很理智。 你也许可以找到其他人； 这是“C 红黑树”在 Google 上的第一个点击。

如果您对性能不挑剔，您也可以使用不平衡二叉树或最小堆或类似的东西。 使用平衡二叉树，可以保证 O(log n) 查找； 对于不平衡的树，查找的最坏情况是 O(n) （对于节点按顺序插入的病态情况，因此最终会得到一个非常长的分支，其作用类似于链表），但是（如果我生锈了）记忆是正确的）平均情况仍然是 O(log n)。

Answer 8

这是一个非常简单和幼稚的

• 固定存储桶大小
• 无删除操作
• 插入替换键和值，并且可以选择释放它们

：

#include <string.h>
#include <stdlib.h>

#define NR_BUCKETS 1024

struct StrHashNode {
    char *key;
    void *value;
    struct StrHashNode *next;

};

struct StrHashTable {
    struct StrHashNode *buckets[NR_BUCKETS];
    void (*free_key)(char *);
    void (*free_value)(void*);
    unsigned int (*hash)(const char *key);
    int (*cmp)(const char *first,const char *second);
};

void *get(struct StrHashTable *table,const char *key)
{
    unsigned int bucket = table->hash(key)%NR_BUCKETS;
    struct StrHashNode *node;
    node = table->buckets[bucket];
    while(node) {
        if(table->cmp(key,node->key) == 0)
            return node->value;
        node = node->next;
    }
    return NULL;
}
int insert(struct StrHashTable *table,char *key,void *value)
{
    unsigned int bucket = table->hash(key)%NR_BUCKETS;
    struct StrHashNode **tmp;
    struct StrHashNode *node ;

    tmp = &table->buckets[bucket];
    while(*tmp) {
        if(table->cmp(key,(*tmp)->key) == 0)
            break;
        tmp = &(*tmp)->next;
    }
    if(*tmp) {
        if(table->free_key != NULL)
            table->free_key((*tmp)->key);
        if(table->free_value != NULL)
            table->free_value((*tmp)->value);
        node = *tmp;
    } else {
        node = malloc(sizeof *node);
        if(node == NULL)
            return -1;
        node->next = NULL;
        *tmp = node;
    }
    node->key = key;
    node->value = value;

    return 0;
}

unsigned int foo_strhash(const char *str)
{
    unsigned int hash = 0;
    for(; *str; str++)
        hash = 31*hash + *str;
    return hash;
}

#include <stdio.h>
int main(int argc,char *argv[])
{
    struct StrHashTable tbl = {{0},NULL,NULL,foo_strhash,strcmp};

    insert(&tbl,"Test","TestValue");
    insert(&tbl,"Test2","TestValue2");
    puts(get(&tbl,"Test"));
    insert(&tbl,"Test","TestValueReplaced");
    puts(get(&tbl,"Test"));

    return 0;
}