在C语言中实现字典的快速方法

Question

在使用C语言编写程序时，我错过的一件事情就是字典数据结构。在C语言中，最方便实现字典数据结构的方法是什么？我不是寻求高性能的实现方式，而是希望从零开始轻松编码实现它。我也不希望它具有通用性 - 一个类似于 char*→int 的东西就可以了。但我确实希望它能够存储任意数量的项目。

这只是一种练习。我知道有第三方库可用，但考虑一下，如果它们不存在，你可以以最快的方式实现满足上述要求的字典吗？

- Rohit

---

如果你想念有人为你提供它，那么为什么不使用第三方实现，而要从头开始制作它呢？ - Karl Knechtel

是的，这个选择总是存在的。我提出这个问题更多是作为一种练习。 - Rohit

在C语言中编写哈希表是一项有趣的练习--每个认真的C程序员都应该至少尝试一次。 - Lee

我认为字典是一种数据类型而不是数据结构，因为它可以用许多方式实现——列表、哈希表、树、自平衡树等。你是在询问字典还是哈希表？ - Paul Hankin

相关：如何在C中表示类似Python的字典？ - Gaurang Tandon

Answer 1

《C程序设计语言》第6.6节介绍了一种简单的字典（哈希表）数据结构。我认为没有比这更简单且有用的字典实现了。为了方便起见，我在此处重复代码。

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}

char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
    if (p != NULL)
       strcpy(p, s);
    return p;
}

请注意，如果两个字符串的哈希值发生冲突，可能会导致 O(n) 的查找时间。您可以通过增加 HASHSIZE 的值来减少碰撞的可能性。有关该数据结构的完整讨论，请参阅书籍。

- Vijay Mathew

---

为什么这里的 hashval = *s + 31 * hashval; 中的常数值是31而不是其他任何值？ - Incerteza

31 是质数。在哈希函数中经常使用质数来降低碰撞的概率。这与整数分解有关（即你无法将一个质数分解成其他整数的乘积）。 - jnovacho

@阿列克斯31在测试数据上表现良好。选择一个质数有其优点，但如果哈希表本身的大小是质数，则不是必需的。 - G. Bach

请注意，K&R C哈希算法是一个令人惊愕的哈希算法。请参考以下链接了解有关它真正糟糕程度的详细信息：http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed。停止使用它！！ - carveone

@Overdrivr：在这种情况下不必要。hashtab是静态持续时间的。具有静态持续时间的未初始化变量（即在函数外声明的变量和使用static存储类声明的变量）保证以正确类型的零值开始（即0或NULL或0.0）。 - carveone

Answer 2

最快的方法是使用已经存在的实现，比如uthash。

如果你真的想要自己编码，可以检查和重用uthash的算法。它采用BSD许可证，因此除了需要传达版权声明之外，你在使用上几乎没有限制。

- paxdiablo

Answer 3

为了方便实现，最简单的方法是通过对数组进行朴素搜索。除了一些错误检查外，这就是一个完整的实现（未经测试）。

typedef struct dict_entry_s {
    const char *key;
    int value;
} dict_entry_s;

typedef struct dict_s {
    int len;
    int cap;
    dict_entry_s *entry;
} dict_s, *dict_t;

int dict_find_index(dict_t dict, const char *key) {
    for (int i = 0; i < dict->len; i++) {
        if (!strcmp(dict->entry[i], key)) {
            return i;
        }
    }
    return -1;
}

int dict_find(dict_t dict, const char *key, int def) {
    int idx = dict_find_index(dict, key);
    return idx == -1 ? def : dict->entry[idx].value;
}

void dict_add(dict_t dict, const char *key, int value) {
   int idx = dict_find_index(dict, key);
   if (idx != -1) {
       dict->entry[idx].value = value;
       return;
   }
   if (dict->len == dict->cap) {
       dict->cap *= 2;
       dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s));
   }
   dict->entry[dict->len].key = strdup(key);
   dict->entry[dict->len].value = value;
   dict->len++;
}

dict_t dict_new(void) {
    dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))};
    dict_t d = malloc(sizeof(dict_s));
    *d = proto;
    return d;
}

void dict_free(dict_t dict) {
    for (int i = 0; i < dict->len; i++) {
        free(dict->entry[i].key);
    }
    free(dict->entry);
    free(dict);
}

- Paul Hankin

---

为了方便实现：您说得没错，这是最容易的方法。此外，它还实现了OP的要求“我希望能够存储任意数量的项目”——最高得票的答案没有做到这一点（除非您认为选择一个编译时常量就可以满足“任意”...） - davidbak

这可能是一种有效的方法，具体取决于用例，但OP明确要求一个字典，而这绝对不是一个字典。 - Dan Bechard

Answer 4

我很惊讶没有人提到 hsearch/hcreate 库集，虽然它在Windows上不可用，但是它被POSIX所规定，因此在Linux/GNU系统中可以使用。

该链接有一个简单而完整的基本示例，非常好地解释了它的用法。

它甚至具有线程安全变体，易于使用且性能非常好。

- fkl

---

值得注意的是，这里的人们说它有点不可用，尽管我自己没有尝试过：https://dev59.com/OG025IYBdhLWcg3wQDlb#6118591 - Ciro Santilli OurBigBook.com

还不错，但是我已经在至少一个应用程序中尝试过hcreate_r（适用于多个哈希表）版本，并运行了足够长的时间以考虑它为真实世界。同意它是GNU扩展，但对于许多其他库也是如此。虽然我仍然会争论您可能仍然能够将其用于在某些真实世界应用程序中操作的一个大键值对。 - fkl

Answer 5

GLib和gnulib

如果您没有更具体的要求，那么这些可能是您最好的选择，因为它们广泛可用、可移植且可能高效。

• GLib: GNOME项目的https://developer.gnome.org/glib/。在https://developer.gnome.org/glib/stable/glib-data-types.html文档中记录了几个容器，包括"哈希表"和"平衡二叉树"。许可证：LGPL。

• gnulib: GNU项目的https://www.gnu.org/software/gnulib/。您应该将源代码复制粘贴到您的代码中。在https://www.gnu.org/software/gnulib/MODULES.html#ansic_ext_container文档中记录了几个容器，包括"rbtree-list"、"linkedhash-list"和"rbtreehash-list"。GPL许可证。

参见：有没有常用数据结构的开源C库？ Zephyr项目实现 这个广为人知的主要使用C语言的嵌入式操作系统在某个时候添加了一个。

• https://github.com/zephyrproject-rtos/zephyr/blob/54155df0c866649139b694bb21bf7c593d8e166b/include/zephyr/sys/hash_map_api.h
• https://github.com/zephyrproject-rtos/zephyr/blob/54155df0c866649139b694bb21bf7c593d8e166b/samples/basic/hash_map/src/main.c
• https://github.com/zephyrproject-rtos/zephyr/blob/54155df0c866649139b694bb21bf7c593d8e166b/lib/hash/hash_map_sc.c
• https://docs.zephyrproject.org/apidoc/latest/hash__map__api_8h.html

- Ciro Santilli OurBigBook.com

Answer 6

创建一个简单的哈希函数和一些结构体的链表，根据哈希值，将要插入的值分配到哪个链表中。同样使用哈希来检索它。

我之前做过一个简单的实现：

... #define K 16 // 链接系数

struct dict { char *name; /* 键名 */ int val; /* 值 */ struct dict *next; /* 链接字段 */ };

typedef struct dict dict; dict *table[K]; int initialized = 0;

void putval ( char *,int);

void init_dict() { initialized = 1; int i; for(i=0;i

int hash ( char *s ) { int h = 0; for(;*s;s++) h = ((h<<1)+*s); return h % K; }

void putval ( char *key_name,int sval ) { dict *ptr; int hsh = hash(key_name); ptr = (dict *) malloc (sizeof *ptr); ptr->name = (char *) malloc (strlen(key_name)+1); ptr->val = sval; strcpy (ptr->name,key_name);

ptr->next = (struct dict *)table[hsh]; table[hsh] = ptr;

}

int getval ( char *key_name ) { int hsh = hash(key_name); dict *ptr; for (ptr = table[hsh]; ptr != (dict *) 0; ptr = (dict *)ptr->next) if (strcmp (ptr->name,key_name) == 0) return ptr->val; return -1; }

- abc def foo bar

---

你不是漏掉了一半的代码吗？"hash()"和"putval()"在哪里？ - swdev

Answer 7

这里是一个快速的实现，我用它从字符串中获取了一个'Matrix'(结构体)。你也可以有一个更大的数组，并在运行时更改其值：

typedef struct  { int** lines; int isDefined; }mat;
mat matA, matB, matC, matD, matE, matF;

/* an auxilary struct to be used in a dictionary */
typedef struct  { char* str; mat *matrix; }stringToMat;

/* creating a 'dictionary' for a mat name to its mat. lower case only! */
stringToMat matCases [] =
{
    { "mat_a", &matA },
    { "mat_b", &matB },
    { "mat_c", &matC },
    { "mat_d", &matD },
    { "mat_e", &matE },
    { "mat_f", &matF },
};

mat* getMat(char * str)
{
    stringToMat* pCase;
    mat * selected = NULL;
    if (str != NULL)
    {
        /* runing on the dictionary to get the mat selected */
        for(pCase = matCases; pCase != matCases + sizeof(matCases) / sizeof(matCases[0]); pCase++ )
        {
            if(!strcmp( pCase->str, str))
                selected = (pCase->matrix);
        }
        if (selected == NULL)
            printf("%s is not a valid matrix name\n", str);
    }
    else
        printf("expected matrix name, got NULL\n");
    return selected;
}

- dagoltz

Answer 8

哈希表是简单“字典”的传统实现。如果您不关心速度或大小，只需搜索它。有许多免费可用的实现。

这是我看到的第一个--乍一看，它看起来还不错。(它相当基础。如果您真的想让它容纳无限量的数据，那么您需要添加一些逻辑来“重新分配”表内存随着其增长。)

- Lee

Answer 9

哈希是关键。我认为可以使用查找表和哈希密钥来实现。你可以在网上找到许多哈希函数。

- ashmish2

Answer 10

Redis 是一个很好的参考，因为它是一个键值系统，它的哈希表是一个很好的例子。

- Michael Lee

---

你的答案可以通过提供额外的支持性信息来改进。请[编辑]添加更多细节，例如引用或文献资料，以便他人可以确认您的答案是正确的。您可以在帮助中心找到有关如何编写良好答案的更多信息。 - Community