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

Question

在C语言中编写程序时我想念的一件事是字典数据结构.在C中实现一个最方便的方法是什么？我不是在寻找性能,而是从头开始编写代码.我也不希望它是通用的 - 像string-> int这样的东西.但我确实希望它能够存储任意数量的项目.

这更像是一项练习.我知道有第三方库可供使用.但考虑一下,他们不存在.在这种情况下,您可以以最快的方式实现满足上述要求的字典.

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.有关数据结构的完整讨论,请参阅本书.

Answer 2

该最快的方法是使用一个已经存在的实现,像uthash.

而且,如果您真的想自己编写代码,uthash可以检查并重复使用算法.它是基于BSD授权的话,比传达版权声明的要求等,你在,你可以用它做什么不错无限.

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

Answer 4

我很惊讶没有人提到hsearch/hcreate一组库，虽然在 Windows 上不可用，但它是 POSIX 强制要求的，因此可在 Linux / GNU 系统中使用。

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

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