c - 在 C 中实现字典的快速方法

Question

在用 C 语言编写程序时，我最怀念的一件事是字典数据结构。在 C 中实现一个最方便的方法是什么？我不是在寻找性能，而是从头开始编写代码的简便性。我也不希望它是通用的——像 char*→int 这样的东西就可以了。但我确实希望它能够存储任意数量的项目。

这更像是一个练习。我知道可以使用第 3 方库。但是想一想，它们并不存在。在这种情况下，实现满足上述要求的字典的最快方法是什么。

Answer 1

The C Programming Language 的第 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 的值来降低发生冲突的可能性。有关数据结构的完整讨论，请参阅本书。