用C语言实现一个非常简单的地图（用于缓存目的）？

Question

我有一个程序，它会读取文件中的URL并对每个URL主机执行gethostbyname()。这个调用非常消耗资源，我想要缓存它们。

是否有一个非常简单的基于映射的C代码片段可以用来进行缓存？（我只是不想重复造轮子）。

它必须具备以下几点：

• 开源且使用许可证宽松（例如BSD或公共领域）。
• 非常简单：理想情况下少于100行代码。
• 键为char*，值为void*。不需要复制它们。
• 没有真正的需要实现remove()，但需要实现contains()或者put()替换值。

PS：我将其标记为“作业”，因为它可能是。我只是很懒，想避免重新实现时可能遇到的所有常见问题。

- Steve Schnepp

---

@Sinan和Meredith：我接受了这段代码片段，因为它恰好是我正在寻找的。 - Steve Schnepp

Answer 1

这是一个非常简单和朴素的实现方式

• 固定桶大小
• 没有删除操作
• 插入会替换键和值，并可以选择是否释放它们

:

#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;
}

- nos

---

+1：正是我正在寻找的。我稍微编辑了一下代码，以应对正确的const-ness（键和值）。现在我的应用程序启动时间不到一秒钟，而不是100％ CPU下的2分钟 :-) - Steve Schnepp

Answer 2

Christopher Clark的哈希表实现非常简单明了。它只有100多行，但并不多。

Clark的代码似乎已经成为Google并发库中的一个并行化示例。

- Sinan Ünür

---

这个仅含链接的回答中的链接已经失效。 - vaultah

@vaultah将链接指向了archive.org。感谢提醒。 - Sinan Ünür

Answer 3

std::map 在 C++ 中是基于红黑树实现的；那么使用 C 语言中现有的红黑树实现 呢？我链接的这个实现大约只有 700 行代码，但是注释很详细，从我粗略的浏览来看也很合理。你可能还能找到其他的实现；这个是在 Google 上搜索 "C red-black tree" 的第一个结果。

如果你对性能不是太挑剔，你还可以使用非平衡二叉树或者最小堆之类的数据结构。使用平衡二叉树，你可以保证 O(log n) 的查找时间复杂度；而在非平衡二叉树中，最坏情况下查找的时间复杂度为 O(n)（当节点按顺序插入时会出现这种病态情况，导致一条非常长的分支就像一个链表一样），但是（如果我的记忆没有出错）平均情况下仍然是 O(log n)。

- Meredith L. Patterson

Answer 4

您可以尝试使用以下实现：

clib

。

- Avinash

---

谢谢，这还在进行中。希望能在另外两周内完成。 - Avinash

Answer 5

memcached？

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

- Justin Niessner

---

-1：我确实想避免系统调用（gethostbyname()），所以我不认为 memcached 是合适的选择。 - Steve Schnepp

Answer 6

不是懒，只是深知避免写这些东西。

这个库怎么样，我自己从未使用过，但它似乎声称能够做到你所要求的。

- djna

---

这个库看起来很有趣，但是网站的最后更新时间是2005年。对于几行代码来说还可以，但对于一个完整的库来说有点太老了。 - Steve Schnepp

良好实现的基础算法不应过时。我不会担心使用这种4年历史的库——假设它们一开始就真正可用。如果您拥有代码，则维护不应成为太大问题。 - djna

Answer 7

Dave Hanson的C接口与实现包含一个不错的哈希表，以及许多其他有用的模块。哈希表的代码量为150行，但这已经包括了内存管理、高阶映射函数和转换为数组等功能。该软件是免费的，而且这本书也值得购买。

- Norman Ramsey

Answer 8

发现一个实现方案在这里: c文件 和h文件，非常接近你要求的。W3C许可证。

- zebrabox